数据结构之栈和队列

阅读文本大概需要 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

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180724G1KYU300?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励