栈和队列
907字约3分钟
2025-11-15
栈(stack)
在第一节有介绍过,栈是一种后进先出(LIFO)策略的集合类型。想象一个薯片桶,最后一块放进去的薯片,总是被最先取出来。栈就是这样的一个容器。放进去叫“入栈”,取出来叫“出栈”。
在 Java 语言中内置了 Stack 数据类型,我们可以直接拿来用。
Stack<String> chips = new Stack<>();
// 入栈
chips.push("hello");
chips.push("world");
// 出栈
chips.pop();
// 访问栈顶元素(不会出栈)
chips.peek();用链表实现栈
- 将链表的头节点作为栈顶
- 入栈时,将新的节点作为新的栈顶(头插法)
- 出栈时,先获取链表头节点(栈顶)的值,再把下一个节点置为栈顶,返回原来的栈顶值(即把头节点从链表中删除)
用数组实现栈
- 将数组的尾部作为栈顶
- 入栈时,将新的节点添加到数组尾部
- 出栈时,先获取数组尾部元素的值,再把尾部元素从数组中删除,最后返回(即删除数组尾部)
栈的典型应用
- 逆序输出(十进制转其他进制)
- 括号匹配
- undo操作
- Dijkstra双栈算式表达式求值法。将操作数和运算符分别放入两个栈中,遇到左括号“(” 则忽略,遇到操作数则将操作数压入栈1中,遇到运算符将它压入栈2中,遇到右括号,则弹出运算符和操作数,计算结果后重新压入栈中。
队列(queue)
队列是一种先进先出(FIFO)策略的集合类型。就像排队队伍,先到的先得。
在 Java 中,LinkedList 和 ArrayList 就是队列的实现,可以直接使用。
Queue<String> list = new LinkedList<>();
list.add("hello");
list.add("world");
// 访问队首元素
list.peek();
// 取出队首元素
list.poll();用链表实现队列
- 将链表的头节点和尾节点分别作为队头和队尾
- 出队时,取走头节点
- 入队时,添加到尾节点
声明数据类型时,最好是在类里面声明好头、尾的引用,这样访问尾节点就不需要遍历整个链表
/* 基于链表实现的队列 */
class LinkedListQueue {
private ListNode head,
private ListNode tail,
private int size = 0;
...
}用数组实现队列
- 将数组索引从小到达依次作为队头到队尾
- 入队时,只需要在数组末尾添加元素
- 出队时,删除索引最小的元素,同时,需要有一个变量来指示当前的队头(因为数组是不可变的,前面的元素如果出队过,数组则存在脏位置)
- 为了避免多次入队出队后数组空间不够了,可以在空间用完后,把队尾重置到 index 0 的位置,就像是一个“环形数组”一样(前提是不要头尾撞车)。或者直接一点,用“数组扩容机制”搬运到一个更大的数组中去
队列的典型应用
- 餐厅排位
- 打印机的任务队列
- 当然,在工程实践中,大多数队列只是拿来当一堆数据的集合
扩展:如何用两个栈实现一个队列?
- 添加元素时往A栈添加
- 删除元素时,先判断B栈是否为空,如果非空,直接从B栈取出最顶元素删除,如果为空,先把A栈里的元素全部倒入B栈中,然后删除最顶元素。
