栈和队列的概念

栈、队列和双端队列

栈和队列是常见的数据结构。栈的特点是后进先出&＃xff0c;添加元素、删除元素和查看元素都在栈顶操作。队列的特点是先进先出&＃xff0c;添加元素在队尾操作&＃xff0c;删除元素和查看元素在队首操作。

双端队列比栈和队列更加灵活&＃xff0c;可以在双端队列的两端添加元素、删除元素和查看元素。

栈、队列和双端队列都满足每次添加元素、删除元素和查看元素的时间复杂度是 $O(1)$。

栈、队列和双端队列都可以基于数组或链表实现。

栈

栈是一种特殊的线性表&＃xff0c;特点是后进先出&＃xff0c;最先加入的元素最后取出&＃xff0c;最后加入的元素最先取出。

栈的常见操作包括判断栈是否为空和获得栈内元素个数&＃xff0c;以及对元素的操作。对元素的操作都位于栈顶&＃xff0c;包括以下三种操作&＃xff1a;

• 添加元素&＃xff1a;将元素加入栈顶&＃xff0c;该操作称为入栈&＃xff1b;
• 删除元素&＃xff1a;将栈顶元素删除&＃xff0c;该操作称为出栈&＃xff1b;
• 查看元素&＃xff1a;获得栈顶元素&＃xff0c;不删除元素。

下图为栈的示意&＃xff0c;左边为栈底&＃xff0c;右边为栈顶。将数字 $1$ 到 $5$ 依次入栈之后&＃xff0c;栈的状态如下图所示&＃xff0c;此时栈顶元素是 $5$&＃xff0c;第一个出栈的元素是 $5$。

队列

队列是一种特殊的线性表&＃xff0c;特点是先进先出&＃xff0c;最先加入的元素最先取出&＃xff0c;最后加入的元素最后取出。队列有头部和尾部&＃xff0c;队列头部称为队首&＃xff0c;队列尾部称为队尾&＃xff0c;队列内的元素从队首到队尾的顺序符合加入队列的顺序。

队列的常见操作包括判断队列是否为空和获得队列内元素个数&＃xff0c;以及对元素的操作。对元素的操作包括以下三种操作&＃xff1a;

• 添加元素&＃xff1a;将元素加入队尾&＃xff0c;该操作称为入队&＃xff1b;
• 删除元素&＃xff1a;将队首元素删除&＃xff0c;该操作称为出队&＃xff1b;
• 查看元素&＃xff1a;获得队首元素&＃xff0c;不删除元素。

需要注意的是&＃xff0c;队列的三种对元素的操作所在的位置不同&＃xff0c;查看元素和删除元素位于队首&＃xff0c;添加元素位于队尾。

下图为队列的示意&＃xff0c;左边为队首&＃xff0c;右边为队尾。将数字 $1$ 到 $5$ 依次入队之后&＃xff0c;队列的状态如下图所示&＃xff0c;此时队首元素是 $1$&＃xff0c;队尾元素是 $5$&＃xff0c;第一个出队的元素是 $1$。

双端队列

双端队列是一种特殊的线性表&＃xff0c;同时具有栈和队列的性质&＃xff0c;特点是在队首和队尾都可以加入和取出元素。栈和队列都可以基于双端队列实现。

Java 中的栈、队列和双端队列

Java 提供了多种类和接口支持栈、队列和双端队列的实现。

$\text{Stack}$ 类是早期版本的栈的实现类&＃xff0c;继承自 $\text{Vector}$ 类。在后续版本中&＃xff0c;JDK 的官方文档不建议使用 $\text{Stack}$ 类实现栈的功能&＃xff0c;而是建议使用 $\text{Deque}$ 接口及其实现类实现栈的功能。

$\text{Queue}$ 接口是队列的接口&＃xff0c;需要通过实现类完成实例化&＃xff0c;常见的实现类包括 $\text{ArrayDeque}$ 类和 $\text{LinkedList}$ 类。

$\text{Deque}$ 接口是双端队列的接口&＃xff0c;需要通过实现类完成实例化&＃xff0c;常见的实现类包括 $\text{ArrayDeque}$ 类和 $\text{LinkedList}$ 类。

$\text{ArrayDeque}$ 类和 $\text{LinkedList}$ 类都可以作为栈和队列的实现类&＃xff0c;区别在于&＃xff0c;$\text{ArrayDeque}$ 类的底层实现是循环数组&＃xff0c;$\text{LinkedList}$ 类的底层实现是双向链表。根据 JDK 的官方文档&＃xff0c;$\text{ArrayDeque}$ 类作为栈使用时效率高于 $\text{Stack}$ 类&＃xff0c;$\text{ArrayDeque}$ 类作为队列使用时效率高于 $\text{LinkedList}$ 类。无论是栈的实现还是队列的实现&＃xff0c;都推荐使用 $\text{ArrayDeque}$ 类。

单调栈和单调队列

单调栈和单调队列是栈和队列的高级应用&＃xff0c;可以解决一些复杂的问题。

单调栈和单调队列满足元素的单调性。具体而言&＃xff0c;单调栈内从栈底到栈顶的元素依次递增或递减&＃xff0c;单调队列内从队首到队尾的元素依次递增或递减。在单调栈和单调队列中添加元素时&＃xff0c;必须维护元素的单调性。

向单调栈添加元素时&＃xff0c;首先需要检查栈顶元素和待添加元素是否满足单调性&＃xff0c;如果不满足单调性则将栈顶元素出栈&＃xff0c;直到栈为空或者栈顶元素和待添加元素满足单调性&＃xff0c;然后将待添加元素入栈。

向单调队列添加元素时&＃xff0c;首先需要检查队尾元素和待添加元素是否满足单调性&＃xff0c;如果不满足单调性则将队尾元素出队&＃xff0c;直到队列为空或者队尾元素和待添加元素满足单调性&＃xff0c;然后将待添加元素入队。

由于普通的队列不支持在队尾将元素出队&＃xff0c;因此需要使用双端队列实现单调队列的功能。

单调栈和单调队列的应用需要考虑具体情况。有时需要维护下标信息&＃xff0c;因此在单调栈和单调队列中存储的不是元素本身&＃xff0c;而是元素下标&＃xff0c;下标对应的元素满足单调性。

使用单调栈和单调队列实现通常需要两层循环&＃xff0c;但是由于每个元素最多只会在单调栈或单调队列中被添加一次和删除一次&＃xff0c;因此时间复杂度是线性复杂度&＃xff0c;而不是平方复杂度。

二叉堆和优先队列

优先队列是一种不同于栈、队列和双端队列的数据结构。栈、队列和双端队列的实现原理是线性表&＃xff0c;而优先队列的实现原理是二叉堆。

二叉堆

在介绍二叉堆之前&＃xff0c;首先需要介绍二叉树和完全二叉树。

二叉树是一个树的结构&＃xff0c;每个结点最多有两个子结点&＃xff0c;称为左子结点和右子结点。

完全二叉树的性质是&＃xff0c;除了层数最大的层以外&＃xff0c;其余各层的结点数都达到最大值&＃xff0c;且层数最大的层的所有结点都连续集中在最左边。假设完全二叉树有 $l$ 层&＃xff0c;其中根结点位于第 $0$ 层&＃xff0c;则对于 $0\le i<l-1$&＃xff0c;第 $i$ 层有 2i2^i2i 个结点。

二叉堆是一棵完全二叉树&＃xff0c;其中的元素按照特定规则排列。常见的例子有小根堆和大根堆。

• 小根堆的性质是&＃xff0c;每个结点的值都小于其子结点的值&＃xff0c;根结点的值是堆中最小的&＃xff1b;
• 大根堆的性质是&＃xff0c;每个结点的值都大于其子结点的值&＃xff0c;根结点的值是堆中最大的。

在二叉堆中添加元素和删除元素时&＃xff0c;必须维护二叉堆的性质。以小根堆为例&＃xff0c;添加元素和删除元素的操作如下&＃xff1a;

• 添加元素时&＃xff0c;假设添加的元素是 $x$&＃xff0c;首先将 $x$ 添加到末尾&＃xff0c;然后比较 $x$ 和父结点元素的大小&＃xff0c;如果 $x$ 小于父结点元素&＃xff0c;则将 $x$ 和父结点交换&＃xff0c;直到 $x$ 到达根结点或者大于等于父结点元素&＃xff1b;
• 删除元素时&＃xff0c;假设堆中的最后一个元素是 $x$&＃xff0c;首先将 $x$ 放置到根结点处&＃xff0c;然后比较 $x$ 和子结点元素的大小&＃xff0c;如果 $x$ 大于至少一个子结点元素&＃xff0c;则将 $x$ 和较小的子结点交换&＃xff0c;直到 $x$ 到达叶结点&＃xff08;没有子结点&＃xff09;或者小于等于全部子结点元素。

考虑以下小根堆。

将 $8$ 添加到小根堆中&＃xff0c;首先将 $8$ 添加到末尾。

由于 $8$ 比父结点 $15$ 小&＃xff0c;因此交换&＃xff0c;交换后 $8$ 比父结点 $10$ 小&＃xff0c;因此再次交换&＃xff0c;此时 $8$ 不再比父结点 $5$ 小&＃xff0c;因此停止交换。添加元素操作结束。

在添加 $8$ 之后&＃xff0c;删除元素。删除堆顶元素 $5$&＃xff0c;将最后一个元素 $15$ 放置到根结点处。

由于 $15$ 比两个子结点元素都大&＃xff0c;因此和较小的子结点 $8$ 交换&＃xff0c;交换后 $15$ 比较小的子结点 $10$ 大&＃xff0c;因此和较小的子结点 $10$ 交换&＃xff0c;此时 $15$ 不再比子结点 $30$ 大&＃xff0c;因此停止交换。删除元素操作结束。

假设二叉堆中的元素个数是 $n$&＃xff0c;二叉堆的层数是 $l$。根据上述例子可知&＃xff0c;在二叉堆中添加元素和删除元素时&＃xff0c;需要维护二叉堆的性质&＃xff0c;时间复杂度是 $O(l)$&＃xff0c;由于 $O(l)\&＃61;O(\log n)$&＃xff0c;因此二叉堆的添加元素和删除元素的时间复杂度是 $O(\log n)$。

优先队列

不同于栈的后进先出和队列的先进先出&＃xff0c;优先队列中的每个元素都有优先级&＃xff0c;优先级最高的元素位于队首&＃xff0c;也是最先取出的元素。

Java 的 $\text{PriorityQueue}$ 类是优先队列类&＃xff0c;继承自 $\text{AbstractQueue}$ 抽象类。$\text{PriorityQueue}$ 类的实现原理是二叉堆&＃xff0c;底层实现是数组&＃xff0c;二叉堆满足堆顶元素为优先级最高的元素。创建优先队列的时候可以自定义优先队列中的元素的比较方法&＃xff0c;从而自定义优先级。

由于 Java 的优先队列的实现原理是二叉堆&＃xff0c;因此优先队列的添加元素和删除元素的时间复杂度是 $O(\log n)$&＃xff0c;查看元素的时间复杂度是 $O(1)$&＃xff0c;其中 $n$ 是优先队列中的元素个数。

目录

1. 栈题目&＃xff1a;文件夹操作日志搜集器
2. 栈题目&＃xff1a;括号的最大嵌套深度
3. 栈题目&＃xff1a;有效的括号
4. 栈题目&＃xff1a;棒球比赛
5. 栈题目&＃xff1a;删除最外层的括号
6. 栈题目&＃xff1a;删除字符串中的所有相邻重复项
7. 栈题目&＃xff1a;用栈操作构建数组
8. 栈题目&＃xff1a;两数相加 II
9. 栈题目&＃xff1a;逆波兰表达式求值
10. 栈题目&＃xff1a;使括号有效的最少添加
11. 栈题目&＃xff1a;平衡括号字符串的最少插入次数
12. 栈题目&＃xff1a;最小栈
13. 栈题目&＃xff1a;行星碰撞
14. 栈题目&＃xff1a;验证栈序列
15. 栈题目&＃xff1a;检查替换后的词是否有效
16. 栈题目&＃xff1a;反转每对括号间的子串
17. 栈题目&＃xff1a;移除无效的括号
18. 栈题目&＃xff1a;简化路径
19. 栈题目&＃xff1a;括号的分数
20. 栈题目&＃xff1a;函数的独占时间
21. 栈题目&＃xff1a;字符串解码
22. 栈题目&＃xff1a;解析布尔表达式
23. 栈题目&＃xff1a;有效括号的嵌套深度
24. 栈题目&＃xff1a;删除字符串中的所有相邻重复项 II
25. 栈题目&＃xff1a;迷你语法分析器
26. 栈题目&＃xff1a;设计浏览器历史记录
27. 栈题目&＃xff1a;基本计算器
28. 栈题目&＃xff1a;基本计算器 II
29. 栈题目&＃xff1a;文件的最长绝对路径
30. 栈题目&＃xff1a;标签验证器
31. 队列题目&＃xff1a;无法吃午餐的学生数量
32. 队列题目&＃xff1a;最近的请求次数
33. 队列题目&＃xff1a;用队列实现栈
34. 队列题目&＃xff1a;用栈实现队列
35. 队列题目&＃xff1a;按递增顺序显示卡牌
36. 队列题目&＃xff1a;设计循环队列
37. 队列题目&＃xff1a;设计循环双端队列
38. 单调栈题目&＃xff1a;去除重复字母
39. 单调栈题目&＃xff1a;移掉 K 位数字
40. 单调栈题目&＃xff1a;找出最具竞争力的子序列
41. 单调栈题目&＃xff1a;132 模式
42. 单调栈题目&＃xff1a;每日温度
43. 单调栈题目&＃xff1a;接雨水
44. 单调栈题目&＃xff1a;股票价格跨度
45. 单调栈题目&＃xff1a;最大宽度坡
46. 单调栈题目&＃xff1a;子数组的最小值之和
47. 单调栈题目&＃xff1a;柱状图中最大的矩形
48. 单调栈题目&＃xff1a;最大矩形
49. 单调队列题目&＃xff1a;绝对差不超过限制的最长连续子数组
50. 单调队列题目&＃xff1a;满足不等式的最大值
51. 单调队列题目&＃xff1a;和至少为 K 的最短子数组
52. 优先队列题目&＃xff1a;最后一块石头的重量
53. 优先队列题目&＃xff1a;数据流中的第 K 大元素
54. 优先队列题目&＃xff1a;拼车
55. 优先队列题目&＃xff1a;合并K个升序链表
56. 优先队列题目&＃xff1a;滑动窗口最大值
57. 优先队列题目&＃xff1a;数据流的中位数
58. 优先队列题目&＃xff1a;多次求和构造目标数组
59. 优先队列题目&＃xff1a;数组的最小偏移量