数据结构之栈和队列
2023-09-27 14:22:51 时间
我们知道,在数组中,若知道数据项的下标,便可立即访问该数据项,或者通过顺序搜索数据项,访问到数组中的各个数据项。但是栈和队列不同,它们的访问是受限制的,即在特定时刻只有一个数据项可以被读取或者被删除。众所周知,栈是先进后出,只能访问栈顶的数据,队列是先进先出,只能访问头部数据。这里不再赘述。
栈的主要机制可以用数组来实现,也可以用链表来实现,下面用数组来实现栈的基本操作:
数据项入栈和出栈的时间复杂度均为O(1)。这也就是说,栈操作所消耗的时间不依赖于栈中数据项的个数,因此操作时间很短。栈不需要比较和移动操作。
队列也可以用数组来实现,不过这里有个问题,当数组下标满了后就不能再添加了,但是数组前面由于已经删除队列头的数据了,导致空。所以队列我们可以用循环数组来实现,见下面的代码:
和栈一样,队列中插入数据项和删除数据项的时间复杂度均为O(1)。
还有个优先级队列,优先级队列是比栈和队列更专用的数据结构。优先级队列与上面普通的队列相比,主要区别在于队列中的元素是有序的,关键字最小(或者最大)的数据项总在队头。数据项插入的时候会按照顺序插入到合适的位置以确保队列的顺序。优先级队列的内部实现可以用数组或者一种特别的树——堆来实现。堆可参考第8节内容。这里用数组实现优先级队列。这里实现的优先级队列中,插入操作需要O(N)的时间,而删除操作则需要O(1)的时间。在第8节里将介绍堆来改进插入操作的时间。
相关文章
- 【转】linux内核数据结构之kfifo环形队列
- 请你用栈实现队列,即用数据结构【栈】来设计数据结构【队列】
- js 数据结构-栈与队列
- 【数据结构初阶】一个队列怎么实现栈~~OJ
- 【数据结构初阶】一文详解顺序栈和链队列的基本操作
- HDU 3706 Second My Problem First (单调队列)
- js数据结构与算法:队列
- 数据结构之栈和队列
- [数据结构]简单数据结构总结及链接{栈|队列|树|链表}
- 数据结构队列的代码实现
- Java集合基础知识笔记:List集合(为什么需编写equals方法)、Map集合(equals与hashCode方法)、EnumMap好处、有顺序的TreeMap、读写配置文件Properties、Set集合(不重复的key值)与有顺序的Set、队列、优先队列、双端队列、栈、迭代器
- 数据结构队列、双端队列、队列系算法题解析
- 35、【栈和队列】二叉树的中序遍历(C++版)
- 算法基础复盘笔记Day03【数据结构】—— 单链表、双链表、栈、队列、单调栈、单调队列
- 数据结构与算法——优先队列类的C++实现(二叉堆)
- java 数据结构——堆栈和队列
- 延时队列
- 数据结构_队列(普通队列和双端队列)
- ActiveMQ_Topic队列(三)
- ACM向:关于优先队列priority_queue自定义比较函数用法整理
- 16数据结构与算法分析之---链式队列
- 15数据结构与算法分析之---顺序队列