栈和队列 - Hero · 算法 · Hello 算法

栈

「栈」 stack 是一种遵循先入后出逻辑的线性数据结构

栈的常用操作

方法	描述	时间复杂度
push()	元素入栈(添加到栈顶)	O(1)
pop()	栈顶元素出栈	O(1)
peek()	访问栈顶元素	O(1)

栈的实现

• 基于链表的实现
• 基于数组的实现

栈的典型应用

• 浏览器中的后退与前进、软件中的撤销与反撤销
• 程序内存管理(栈帧)

队列

「队列 queue」是一种遵循先入先出规则的线性数据结构

队列的常用操作

方法	描述	时间复杂度
push()	元素入列(添加到末尾)	O(1)
pop()	队首元素出队	O(1)
peek()	访问队首元素	O(1)

队列的实现

• 基于链表的实现(反向或空指针)
• 基于列表的实现

队列典型应用

• 淘宝订单
• 各类待办事项

双向队列

双向列表的实现

• 基于双向链表
• 基于数组

双向队列的应用

双向队列兼具栈与队列的逻辑，因此它可以实现这两者的所有应用场景，同时提供更高的自由度。

当栈的长度超过一定数量时，软件需要在栈底（队首）执行删除操作。但栈无法实现该功能，此时就需要使用双向队列来替代栈