Question

栈和队列属于线性结构 对吗?

Answer 1

栈和队列属于线性结构是对的。

1、什么是栈：

 栈（Stack）是一个后进先出（Last in first out,LIFO）的线性表，它要求只在表尾进行删除和插入操作。

栈的结构示意图，按箭头方向操作：

2、什么是队列：

 队列是限定只能在表的一端进行插入，在表的另一端进行删除的特殊的线性表。

Answer 2

栈和队列属于线性结构是对的。

一、什么是栈： 栈（Stack）是一个后进先出（Last in first out,LIFO）的线性表，它要求只在表尾进行删除和插入操作。栈的结构示意图，按箭头方向操作：

二、什么是队列： 队列是限定只能在表的一端进行插入，在表的另一端进行删除的特殊的线性表。

Answer 3

说到栈和队列这两种数据结构，理解起来应该不难。队列就是进行排队的数据结构，一个队列肯定是线性结构了，之所以称之为队列，是因为有着先入先出（FIFO ----first in first out）的特性。
就像你去银行办业务排队时，你先排的队当然是你先办理业务，那些后排队的要在你后边办业务。而栈就与队列相反了，栈具有先入后出（FILO -- first in last out）的特性。在现实生活中手枪的子弹夹就是栈的结构，最先进去的子弹会最后才射出。
当然在我们做iOS开发时，会经常使用到导航栈，而导航栈中存储的就是你之前Push进的页面，也是先入后出的特性。关于栈和队列，下方会给出详细的介绍。

一、栈与队列的综述
栈与队列毫无疑问都是线性结构的，分别适用于不同的场景。博客的本部分会给出栈与队列的总体介绍，然后分别给出其实现方案。
当然下方在栈与队列的实现中，我们依然采用“面向接口”编程的思想，会先定义栈与队列的相关接口，然后给出栈与队列的不同实现方案。
下方这个就是一个典型的队列的结构。需要加入队列中的元素是往队尾添加的，而需要出队的元素从队头出。这样出队列的顺序与进入队列的顺序是一致的。这也就是队列的特性，先入先出。
之前我们在聊GCD的中的队列的时候也同样适应这个特性。在GCD中无论是串行队列还是并行队列，其都遵循队列“先入先出”的规则。
　　
上面我们简单的聊了一下队列，接下来我们来简单的聊一下栈。
在博客的开头也提到了，弹构就是栈结构。弹夹中的子弹就是栈中的元素，遵循着先入后出的原则。下方这个示例图就是一个典型的栈型结构。在栈中有一个指针Top，永远指向栈顶元素，如果栈为空，那么Top就为nil。
在栈结构中无论是入栈还是出栈，都是操作栈顶元素。所以入栈顺序与出栈顺序是相反的。
　　

二、线性队列和链式队列的实现
聊完原理，接下来我们就要来进行代码实现了。
下方将会给出具体的队列的实现代码，并给出相应的测试用例。当然我们依然是采用面向对象的思想来实现的队列的。
在看具体代码之前，我们先来看一下我们本篇博客所涉及Demo的具体目录。最上面的框是两个协议，StackProtocol中声明了栈结构所涉及的操作，所有栈都要遵循该协议。
QueueProtocol声明了队列中所涉及的所有操作，队列的实现都要遵循该队列协议。
　　
这样做的好处就是所有类型的栈可以共用栈的测试用例，而队列也是如此。
下方就是我们测试用例的调用方式，需要测栈时，就给栈的测试用例传入相应栈的对象，队列也是一样。也就能明显看出面向接口编程的好处。
　　

1.队列协议：QueueType
在具体实现队列之前，我们先定义队列的接口。此处我们要定义的就是QueueType协议，在QueueType中声明的是队列的全部操作。
无论是栈队列，还是顺序队列都必须要遵循该接口，而在外部声明队列类型时，我们一般会使用QueueType来声明队列类型。类型为QueueType的队列可以被赋值为遵循QueueType协议的类的任何对象。下方就是QueueType协议中的内容。
从下方的代码段中，我们显然可以看出QueueType协议就是赋值为我们的队列实现定制大纲的。有了这个大纲，具体队列的实现要按照下方这个大纲来。
至于队列的具体实现细节，QueueType协议并不关心，QueueType关系的是队列对外的使用方式。
　　

2.顺序队列
接下来我们就依据上述的队列的协议，给出顺序队列的具体实现代码。顺序队列我们就以Swift中的数组类型来代替了。
enQueue--入队列所对应的操作就是往数组的尾部添加数据，而deQeueu--出队列操作就是将数组第一个元素进行移除并返回移除的值即可。下方就是入队列和出队列的操作，如下所示。
队列的其他操作在此就不做过多赘述了，请参考github上分享的代码。
　　

3.链式队列
链式队列其实就是链表的一种使用方式。链式队列就是讲队列元素以链表的形式进行存储，并且规定只能从链表的尾部添加元素，从链表的头部移除元素。
关于链表的各种操作请参考上篇博客《数据结构之线性表的顺序存储于链式存储（Swift面向对象版）》中介绍的内容。
该部分就是链表在队列中的应用。与上面的内容类似，下方是链式队列的核心操作，下方截图中的代码段是链式队列中出队列和入队列的操作了。
如下所示：
　　

4.队列的测试用例
上面我们分别实现了链式队列和顺序队列，接下来我们将会对上面这两种队列进行测试。
由于上面这两种队列有种统一的对外调用接口，也就是这两种队列都遵循QeueuType这个队列协议。所以在测试队列时我们可以使用同一个测试用例，这也就是“面向接口编程”的好处。
当我们再引入其他队列的具体实现方案时，只需要将新引入的队列解决方案遵循我们之前定义的QueueType接口即可，我们的测试用例仍然好用。
从这一点我们就能看出“面向接口”编程的可维护性和高扩展性。
下方就是我们队列的测试用例, 函数的参数是QueueType的类型。也就是只要遵循QueueType协议的所有类的对象都可以作为该函数的参数。
最下方的两行代码是该函数的调用方式。第一个传入的是顺序队列的对象，所有测试的就是顺序队列相关代码。而第二个传入的是栈队列的对象，那么测试的就是栈队列的相关代码。
　　
下方就是测试用例的运行结果，先将a, b出队列，然后将x,y,x如队列。
　　

三、栈的顺序存储与链式存储
上面已经聊完队列的相关内容了，接下来我们在按照上面的方式来聊一下栈的内容。
再重复一遍栈的规则：
先入后出。先入后出是栈的特定，当然栈也属于逻辑结构中线性结构，基于线性结构的特定，所以栈也是有这链式和顺序存储的结构的。下方将会给出栈的这两种实现。在具体实现不同类型的栈时，我们还是依照“面向接口”编程的思想，先定义出栈的协议StackType。
StackType协议中定义了栈的所有相关操作，栈的具体实现要遵循该协议。这样做的好处就不做过多赘述了。

1.栈协议StackType的定义
首先我们还是来定义栈的接口StackType。下方截图中的代码段就是我们定义好的栈的接口，也就是Swift语言中的协议。从下方协议中我们不难看出，只声明了方法，而没有具体实现。
具体实现我们放在不同类型的栈中去做。因为具体实现的栈要对外统一调用接口，所以必须遵循StackType协议。
　　

2.栈的顺序存储实现
定义完栈的协议后，我们就该遵循该协议给出具体的实现了，接下来我们要给出顺序栈的实现方式。此处为了简单期间，我们就使用Swift的数组（Array）变量来实现。
当然入栈和出栈操作都是借助Array自带的操作来实现的。下方截图中就是顺序栈中入栈（push）和出栈（pop）的操作。因为我们借助了Array本身的操作，也就是Array为我们做了许多事情，所以实现起来就比较简单了。
下方就是顺数栈的主要操作，push()方法就是将该函数的参数进行入栈操作。其实就是调用的Array的append()方法，将该参数存入到数组的最后一个位置。
而pop()方法负责移除并返回栈顶元素，此处我们借用了Swift语言中的Array的removeLast()方法，来移除数组的最后一个元素，然后将这个元素进行返回。从上述操作步骤来看，栈的特点就是对栈顶元素进行操作。
　　

3. 栈的链式存储实现
上面的顺序存储，我们使用的是顺序存储，借助了Array来实现的，所以操作起来比较简单。
栈的链式存储操作起来会相对麻烦一些，不过这些操作在上篇博客中已经进行了详细的介绍，所以对本篇博客来说并非难事。
下方这段代码就是链式存储的栈的核心操作。push()方法赋值的就是往栈中添加新的元素，首先会创建一个新的结点，然后添加到栈顶元素中。
栈顶元素我们用top指针来进行标记。入栈后我们还要将栈的长度进行加一操作。然后就是pop()出栈操作了，首先会判断栈是否为空，如果不为空就返回栈顶元素，并将栈顶元素进行移除。
移除栈顶元素后需要将top指针指向新的栈顶并将栈中的元素进行减一操作。具体代码如下所示。
　　

4.栈的测试用例
因为上述我们栈的实现都遵循了我们事先定义好的StackType协议，所以上述两种类型的栈可以使用一个测试用例。
这一点与上述队列的测试用例是一致的，接下来我们将要来测试我们的栈。下方testStack()函数就是我们栈的测试函数，函数的参数类型是StackType。
所有遵循StackType协议的栈的对象都可以作为该函数的参数。最后两行是函数的调用方式，第一个传入的是顺序栈的对象，第二个传入的参数是链栈的对象。
　　
由上面这段代码可看出，该测试用例是适用于StackType系列的栈。下方就是测试用例的输出结果，输出结果还算是直观形象，所以在此就不做过多的赘述了。
　　

至此呢，我们的栈与队列的顺序存储和链式存储就聊完了。

Answer 4

栈、队列属于线性结构，二叉树是非线性结构。