一、栈和队列属于线性结构***对吗

说到栈和队列这两种数据结构，理解起来应该不难。队列就是进行排队的数据结构，一个队列肯定是线性结构了，之所以称之为队列，是因为有着先入先出（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系列的栈。下方就是测试用例的输出结果，输出结果还算是直观形象，所以在此就不做过多的赘述了。

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

二、为什么栈和队列都是线性结构

1.队列先进先出，栈先进后出。

2.对插入和删除*作的"限定"。

栈是限定只能在表的一端进行插入和删除*作的线性表。队列是限定只能在表的一端进行插入和在另一端进行删除*作的线性表。

从"数据结构"的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本*作集不同外，主要区别是对插入和删除*作的"限定"。

栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本*作的特殊性，栈必须按"后进先出"的规则进行*作，而队列必须按"先进先出"的规则进行*作。和线性表相比，它们的插入和删除*作受更多的约束和限定，故又称为限定性的线性表结构。

3.遍历数据速度不同。栈只能从头部取数据

也就先放入的需要遍历整个栈后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性队列怎不同，他基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多

栈（Stack）是限定只能在表的一端进行插入和删除*作的线性表。

队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除*作的线性表。

从"数据结构"的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本*作集不同外，主要区别是对插入和删除*作的"限定"。

栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本*作的特殊性，栈必须按"后进先出"的规则进行*作，而队列必须按"先进先出"的规则进行*作。和线性表相比，它们的插入和删除*作受更多的约束和限定，故又称为限定性的线性表结构。可将线性表和栈及队列的插入和删除*作对比如下：

栈

Insert(L,n+1,x)

Delete(L,n)

而栈只允许在表尾一端进行插入和删除

队列

Insert(L,n+1,x)

Delete(L,1)

队列只允许在表尾一端进行插入，在表头一端进行删除

三、栈和队列是线性结构吗

栈和队列是线性结构。

栈（Stack）和队列（Queue）是两种常见的线性数据结构。

栈是一种具有后进先出（Last-In-First-Out，LIFO）特性的数据结构。它的特点是只允许在一端进行插入和删除*作，该端被称为栈顶。新元素插入的位置就成为了新的栈顶，删除元素的位置也是栈顶。类似于现实生活中的堆叠物体，只能在上面放置新元素或者从上面取出元素。常见的栈*作包括入栈（push）向栈顶插入元素，出栈（pop）从栈顶删除元素，以及获取栈顶元素的*作。

队列是一种具有先进先出（First-In-First-Out，FIFO）特性的数据结构。它的特点是允许在一端进行插入*作，在另一端进行删除*作。插入*作在队尾进行，而删除*作在队头进行。类似于现实生活中的排队，先来的人先离开。常见的队列*作包括入队（enqueue）将元素插入到队尾，出队（dequeue）从队头删除元素，以及获取队头元素的*作。

栈和队列都是非常常见且重要的数据结构，它们在计算机科学中的应用非常广泛。

计算机在现当**展历史

1、 20世纪初：电子管的发明使得计算机的发展进入一个新时代。1936年，图灵提出了图灵机的概念，这被认为是通用计算机的理论基础。

2、第二次世界大战期间：计算机在军事和科学研究中的应用迅速增加。1944年，哈佛大学建造了世界上第一台电子计算机，名为马克一号。

3、1950年代：威尔士曼、冯·诺伊曼和艾兰·图灵等人对计算机的结构和编程概念进行了重要的贡献。冯·诺伊曼计算机结构成为了计算机设计的基础。

4、1960年代：集成电路的发明使得计算机变得更小、更快、更便宜。这一时期诞生了许多具有里程碑意义的计算机，包括IBM System/360系列。

5、1970年代：个人计算机的出现使得计算机普及化。苹果公司和微软公司成立并推出了个人计算机产品。

6、1980年代：个人计算机的性能不断提升，图形用户界面的出现使得*作更加直观。这一时期还出现了许多重要的计算机公司和技术，如IBM PC和微软Windows*作系统。

7、1990年代：互联网的普及使得计算机连接起来，人们可以通过网络共享信息和资源。这一时期还见证了个人计算机的进一步发展，如笔记本电脑和智能手机的出现。