【软考】数据结构 线性表结构 - 栈与队列
2023-09-14 09:14:14 时间
一、队列(Queue)
1.1 队列的定义
是限定只能在表的一端进行插入和在另一端进行删除操作的线性表
1.2 队列的使用场景
递归算法一般需要利用队列实现。
二、栈(Stack)
2.1 栈的定义
是限定只能在表的一端进行插入和删除操作的线性表
2.2 特征
- 后进先出,先进后出的线性表
- 按先进后出原则组织数据
- 具有记忆功能
2.3 两种存储结构
线性存储结构
链表存储结构
2.4 基本运算
入栈
退栈(出栈)
读栈顶元素
2.5 由两个栈共享一个存储空间的好处
[x]节省存储空间
[x]降低上溢发生的机率
三、队列和栈有什么区别
共同特点:只允许在端点处插入和删除元素
队列和栈是两种不同的数据结构。它们有以下区别:
3.1 操作的规则不同
队列:先进先出(First In First Out)FIFO
队列是先进先出(FIFO),即队列的修改是依先进先出的原则进行的。
新来的成员总是加入队尾(不能从中间插入),每次离开的成员总是队列头上(不允许中途离队)。
栈:先进后出(First In Last Out )FILO
栈为后进先出(LIFO),即每次删除(出栈)的总是当前栈中最新的元素,
即最后插入(进栈)的元素,而最先插入的被放在栈的底部,要到最后才能删除。
3.2 对插入和删除操作的限定不同
队列:只能在表的一端进行插入,并在表的另一端进行删除;
队列是在队尾入队,队头出队,即两边都可操作。
栈:只能在表的一端插入和删除。
而栈的进栈和出栈都是在栈顶进行的,无法对栈底直接进行操作。
3.3 遍历数据速度不同
队列:基于地址指针进行遍历,而且可以从头部或者尾部进行遍历,但不能同时遍历,无需开辟空间,因为在遍历的过程中不影响数据结构,所以遍历速度要快
栈:只能从顶部取数据,也就是说最先进入栈底的,需要遍历整个栈才能取出来,而且在遍历数据的同时需要为数据开辟临时空间,保持数据在遍历前的一致性。
3.4 操作的名称不同
队列的插入称为入队,队列的删除称为出队。
栈的插入称为进栈,栈的删除称为出栈。
相关文章
- 野生前端的数据结构基础练习(2)——队列
- ASP.NET Core基于RabbitMQ实现海量消息队列分发实战演练
- 【python cookbook】【数据结构与算法】5.实现优先级队列
- 数据结构——队列
- 并发无锁队列学习之二【单生产者单消费者】
- EasyDarwin开源流媒体服务器高性能设计之无锁队列
- 算法导论第十章 栈队列和链表
- C#实战Microsoft Messaging Queue(MSMQ)消息队列(干货)
- 数据结构之栈和队列
- 232. 用栈实现队列
- 分布式系统一致性问题解决实战(阿里) 异步解耦+消息队列可作为分布式系统满足最终一致性的优秀方案
- 鸿蒙轻内核M核源码分析:数据结构之任务就绪队列
- 【数据结构】测试3 栈和队列
- CoreJava_线程并发(堵塞队列):在某个目录下搜索含有某keyword的文件
- POJ 3013 Big Christmas Tree(最短Dijkstra+优先级队列优化,SPFA)
- 分布式之消息队列复习精讲
- 004-数据结构-线性结构-ADT-栈与队列【数组方式实现】
- 基于Python语言使用RabbitMQ消息队列(六)
- 1470. 水桶传递队列(bfs最短路径)
- 【AcWing】829. 模拟队列
- 【数据结构】队列的基本概念 | 从零开始实现队列 | 利用思路草图将思路转变为代码