常用算法及数据结构之Stacks/Queues

【导读:数据是二十一世纪的石油,蕴含巨大价值,这是·情报通·大数据技术系列第[148]篇文章,欢迎阅读收藏】

1 基本概念

栈 (Stack) 是一种后进先出 (last in first off , LIFO) 的数据结构,而队列 (Queue) 则是一种先进先出 (fisrt in first out , FIFO) 的结构。

2 术语解释

对于栈而言,允许进行插入,删除操作的一端被称为栈顶( top ), 另一端则被称为栈底( bottom )。

如果一个栈不包含任何元素,那么这个栈就被称为空栈。

从栈顶插入一个元素被称为入栈( push ),将一个元素从栈顶删除被称为出栈( pop )

对于队列而言,只允许在表的前端 (front)进行删除操作,只允许在表的后端( rear )进行插入操作,进行插入操作的端称为队尾,进行删除的端称为对头。

如果队列中不包含任何元素,该队列就被称为空队列。

对于一个队列来说,每个元素总是从队列的 rear 端进入队列,然后等待该与元素之前的所有元素出对之后,当前元素才能出对。

3 详细说明

3.1 栈的顺序存储结构及实现

顺序存储结构的栈简称为顺序栈,它利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。栈底位置固定不变,它的栈顶可以直接通过顺序栈底层数组的数组元素 arr[size-1] 来访问。

顺序栈中数据元素的物理关系和逻辑关系是一致的,先进栈的元素位于栈底,栈底元素的存储位置相对也比较小。

进栈

对于顺序栈的进栈操作而言,只需将新的数据元素存入栈内,然后让记录栈内元素个数的变量加 1 ,程序即可再次通过 arr[size-1] 重新访问新的栈顶元素。进栈操作示意图如下:

由于顺序栈底层通常会采用数组来保存数据元素,因此可能出现的情况是:当程序试图让一个数据元素进栈时,底层数据已满,那么就必须扩充底层数组的长度来容纳新进栈的数据元素。

出栈

对于顺序栈的出栈操作而言,需要将栈顶元素弹出栈,程序要做两件事。

让记录栈内元素个数的变量减 1.

释放数组对栈顶元素的引用。

出栈操作示意图如下图 :

对于删除操作来说,只要让记录栈内元素个数的 size 减 1 ,程序即可通过 arr[size-1] 访问到新的栈顶元素。但不要忘记释放原来栈顶的数组引用,否则会引起内存泄漏。

栈比普通线性表的功能更弱,栈时一种被限制过的线性表,只能从栈顶插入,删除数据元素。

3.2 栈的链式存储结构及实现

程序可以采用单链表来保存栈中所有元素,这种链式结构的栈也被称为栈链。对于栈链而言,栈顶元素不断地改变,程序只要使用一个 top 引用来记录当前的栈顶元素即可。top 引用变量永远引用栈顶元素,再使用一个 size 变量记录当前栈中包含多少个元素即可。

3.3 队列的顺序存储结构及实现

系统采用一组地址连续的存储单元依次存放队列从 rear 端到 front 端的所有数据元素,程序只需 (front 和 rear 两个整型变量来记录队列 front 端的元素索引、 rear 端的元素索引。

3.4 队列的链式存储结构及实现

使用链式结构保存线性表,也可以采用链式结构来存储队列的各元素,采用链式存储结构的队列也被称为链队列。

对于链队列而言,由于程序需要从 rear 端添加元素,然后从 front 端移除元素,因此考虑对链队列增加 front,rear 两个引用变量,使他们分别执行链队列的头,尾两个节点。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20200425A05S2F00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券