数据结构之栈和队列

阅读文本大概需要 9 分钟。

数据结构有许多种，上篇文章分享的是可以存储简单数据的列表，例如待办事项，购物清单等。今天要跟大家分享的是两种非常常见的也必须了解的数据结构——栈与队列。

栈的定义

什么是栈呢？它是一种“后入先出”的数据结构，它跟列表一样，都是可以用来存储数据，但是却要比列表严格的多，栈的数据只能在栈顶添加或删除。举个例子，在麦当劳用餐时的那些盘子，捡餐员在拿盘子时，总是从一摞盘子的最上端拿（栈顶），然后放上食品在端给客人，而那些擦餐盘的人，也总是在最上面拿起餐盘擦拭后不断地叠放成一摞餐盘，这里的餐盘就可看成是栈，数据的添加或删除总是在最上端进行。下图展示了栈的构成以及简单的入栈与出栈过程。

图片来自网络栈的主要操作方法

栈的常用操作就是入栈和出栈，入栈用的是 push() 方法，出栈用的是 pop() 方法，还有一个方法是 peek() ，该方法可以返回栈顶的元素而不删除它，相应的 pop() 方法虽然也可以得到栈顶的元素，但会将它删除。

栈的实现

在 JavaScript 中，通常使用数组来实现栈。下面我们定义一个名为 Stack 的构造函数用来表示栈。

dataStore 是一个数组，用来存储栈中的元素，而变量 top 记录栈顶的位置，初始位置为 0，push 、pop 和 peek 分别对应三个方法，下面来实现这些方法。

首先是 push() ,入栈。

这里 top++ 很有意思，要知道 + 号在变量后和变量前是不同的，这里的逻辑是，当元素入栈后，变量 top 的值就对应当前入栈元素的位置，然后 top++ ，自增后的值就是下一个元素入栈时的位置了。

接下来是出栈方法 pop() 。

前面说了，栈只能在最顶端添加、删除数据，所以我们必须要知道栈顶现在存放的是哪个数值才能将它删除，于是我们使用 top 来标记它的位置，现在出栈，只需要把指向栈顶的位置的节点数据拿掉就行了。

最后一个方法是取栈顶元素的 peek() 方法,相信也不难理解，就把栈顶元素直接返回就行，注意栈顶元素的位置是第 top - 1 个位置。

除了上述的基本操作方法外，还有其它方法可以有作用。来看下面这两个方法

上面的方法一个是可以获取栈内存储了多少个元素的 length() 方法， 另一个是 clear() ,听名字就知道是把一个栈清空，通过将 top 的值归零。

栈的完整代码

栈的完整代码以及测试如下

运行结果为：

栈的长度为： 3

Mike

当前长度为： 0

队列的定义

队列是一种与栈截然不同的数据结构，栈的特点是后入先出，最后入栈的元素会优先处理而弹出，而队列的特点则是先入先出，最先进栈的也会最终先出栈，这有点类似于银行窗口前排队办业务的人群，排在最前面的先办理业务，后面来的就依次排队。

队列的主要操作方法

与栈一样，队列也是用数组来实现，它的主要操作方法同样是入队（enqueue）,出队（dequeue）和读取队头的元素（peek）,读取队头元素同样不会删除元素，只返回。此外还有清空队列元素（clear）和获取队列元素个数（length）。

队列的实现

首先定义一个 Queue 类用来表示队列。

接下来实现入队方法 enqueue() ：

可以看到，用数组来实现队列非常简单，入队只需一个 push() 方法即可向队尾添加元素。

shift 是数组的一个操作方法，可以将数组的第一个元素删除。

这两个分别是读取队列的第一个元素和最后一个元素，很简单，直接返回数组的第一个元素和最后一个元素即可。

这个方法显示队列元素，类似控制台 console 输出元素。

这是一个判空方法，每次使用队列前要判断是否为空才可进行下一步的操作。

队列完整代码及测试

运行结果如下：

Mike

Hello

hhhh

Hello

hhhh

队列的第一个元素是: Hello

队列的最后一个元素是: hhhh