7.Java栈与队列：从生活场景到源码实现的完整解读

目录一、为什么需要栈和队列二、栈后进先出的世界2.1 什么是栈2.2 栈的基本操作2.3 栈的使用示例2.4 栈的模拟实现2.5 栈的经典应用场景场景一括号匹配场景二逆波兰表达式求值场景三最小栈三、队列先进先出的世界3.1 什么是队列3.2 队列的基本操作3.3 队列的使用示例3.4 队列的模拟实现3.5 循环队列四、双端队列既能当栈又能当队列4.1 什么是双端队列4.2 Deque的使用五、栈与队列的相互实现5.1 用两个栈实现队列5.2 用两个队列实现栈六、栈与队列的对比总结七、常见面试题八、总结与学习建议8.1 核心要点回顾8.2 学习建议写在前面本文基于课程《栈和队列》的学习内容整理结合个人理解与代码实践编写。所有示例代码均为独立编写旨在帮助读者建立对栈和队列这两种基础数据结构的系统认知。如需深入学习建议配合官方文档和JDK源码阅读。一、为什么需要栈和队列在前面的文章中我们学习了ArrayList和LinkedList这两种通用的线性表。但在实际开发中有些场景对数据的存取顺序有特殊要求浏览器的后退功能你访问了页面A→B→C点击后退时应该回到B而不是A。这就是“后进先出”。打印机的任务队列先提交的任务先打印后提交的后打印。这就是“先进先出”。这两种场景分别对应了两种特殊的线性表——栈Stack​ 和队列Queue。它们是对通用线性表的“功能裁剪”只暴露特定的操作接口从而保证数据的有序处理。二、栈后进先出的世界2.1 什么是栈栈是一种只允许在固定一端进行插入和删除操作的线性表。这个固定端称为栈顶另一端称为栈底。栈的核心规则是后进先出LIFOLast In First Out——最后放入栈中的元素最先被取出。生活中的例子一摞盘子你总是先拿最上面的盘子后放上去的羽毛球筒你从筒口拿到的总是最后一个放进去的球撤销操作CtrlZ最后一次操作被最先撤销2.2 栈的基本操作方法功能时间复杂度push(E e)将元素e压入栈顶O(1)pop()弹出栈顶元素并返回O(1)peek()获取栈顶元素但不弹出O(1)empty()判断栈是否为空O(1)size()获取栈中元素个数O(1)2.3 栈的使用示例import java.util.Stack; public class StackDemo { public static void main(String[] args) { StackInteger stack new Stack(); // 入栈 stack.push(1); stack.push(2); stack.push(3); stack.push(4); System.out.println(栈的大小 stack.size()); // 4 // 查看栈顶元素不弹出 System.out.println(栈顶元素 stack.peek()); // 4 // 出栈 int top stack.pop(); System.out.println(弹出的元素 top); // 4 System.out.println(现在栈顶 stack.peek()); // 3 // 判断是否为空 while (!stack.empty()) { System.out.print(stack.pop() ); // 3 2 1 } System.out.println(\n栈是否为空 stack.empty()); // true } }2.4 栈的模拟实现Java中的Stack类继承自Vector底层是动态数组。我们也可以自己实现一个栈帮助理解其工作原理。public class MyStackT { private Object[] elements; // 存储元素的数组 private int size; // 当前元素个数 private static final int DEFAULT_CAPACITY 10; public MyStack() { elements new Object[DEFAULT_CAPACITY]; size 0; } // 入栈 public T push(T item) { ensureCapacity(); elements[size] item; return item; } // 出栈 SuppressWarnings(unchecked) public T pop() { if (empty()) { throw new RuntimeException(栈为空无法出栈); } T item (T) elements[--size]; elements[size] null; // 帮助GC回收 return item; } // 查看栈顶 SuppressWarnings(unchecked) public T peek() { if (empty()) { throw new RuntimeException(栈为空); } return (T) elements[size - 1]; } // 判空 public boolean empty() { return size 0; } // 获取大小 public int size() { return size; } // 扩容 private void ensureCapacity() { if (size elements.length) { int newCapacity elements.length * 2; elements Arrays.copyOf(elements, newCapacity); } } }2.5 栈的经典应用场景场景一括号匹配这是栈最经典的应用之一。给定一个只包含(){}[]的字符串判断括号是否正确闭合。public boolean isValid(String s) { StackCharacter stack new Stack(); for (char c : s.toCharArray()) { if (c ( || c { || c [) { // 左括号入栈 stack.push(c); } else { // 右括号检查栈顶是否匹配 if (stack.empty()) { return false; // 没有左括号与之匹配 } char top stack.pop(); if (c ) top ! () return false; if (c } top ! {) return false; if (c ] top ! [) return false; } } return stack.empty(); // 所有左括号都被匹配 }思路遇到左括号入栈遇到右括号检查栈顶是否是对应的左括号。场景二逆波兰表达式求值逆波兰表达式后缀表达式是栈应用的另一个经典案例。public int evalRPN(String[] tokens) { StackInteger stack new Stack(); for (String token : tokens) { switch (token) { case : stack.push(stack.pop() stack.pop()); break; case -: int b stack.pop(); int a stack.pop(); stack.push(a - b); break; case *: stack.push(stack.pop() * stack.pop()); break; case /: int divisor stack.pop(); int dividend stack.pop(); stack.push(dividend / divisor); break; default: stack.push(Integer.parseInt(token)); } } return stack.pop(); }思路遇到数字入栈遇到运算符则弹出两个数字计算结果入栈。场景三最小栈设计一个栈支持在常数时间内获取栈中的最小值。class MinStack { private StackInteger dataStack; // 数据栈 private StackInteger minStack; // 辅助栈存储最小值 public MinStack() { dataStack new Stack(); minStack new Stack(); } public void push(int val) { dataStack.push(val); // 如果minStack为空或者val比当前最小值还小则入minStack if (minStack.empty() || val minStack.peek()) { minStack.push(val); } } public void pop() { int val dataStack.pop(); // 如果弹出的值是当前最小值minStack也要弹出 if (val minStack.peek()) { minStack.pop(); } } public int top() { return dataStack.peek(); } public int getMin() { return minStack.peek(); } }思路用一个辅助栈同步记录当前的最小值。三、队列先进先出的世界3.1 什么是队列队列是一种只允许在一端插入、在另一端删除的线性表。插入的一端称为队尾删除的一端称为队头。队列的核心规则是先进先出FIFOFirst In First Out——最早进入队列的元素最先被取出。生活中的例子超市收银台排队先排队的顾客先结账打印机任务队列先提交的文档先打印消息队列先发送的消息先被消费3.2 队列的基本操作在Java中Queue是一个接口需要通过实现类来实例化。最常用的实现类是LinkedList。方法功能失败时的行为offer(E e)入队将元素添加到队尾返回falsepoll()出队移除并返回队头元素返回nullpeek()获取队头元素但不移除返回null3.3 队列的使用示例import java.util.LinkedList; import java.util.Queue; public class QueueDemo { public static void main(String[] args) { // Queue是接口需要用LinkedList实例化 QueueInteger queue new LinkedList(); // 入队 queue.offer(1); queue.offer(2); queue.offer(3); queue.offer(4); System.out.println(队列大小 queue.size()); // 4 // 查看队头不删除 System.out.println(队头元素 queue.peek()); // 1 // 出队 int front queue.poll(); System.out.println(出队元素 front); // 1 System.out.println(新的队头 queue.peek()); // 2 // 遍历队列 while (!queue.isEmpty()) { System.out.print(queue.poll() ); // 2 3 4 } System.out.println(\n队列是否为空 queue.isEmpty()); // true } }3.4 队列的模拟实现队列底层可以使用链表实现因为链表的头部删除和尾部插入都是O(1)操作。public class MyQueueT { // 双向链表节点 private static class NodeT { T value; NodeT prev; NodeT next; Node(T value) { this.value value; } } private NodeT head; // 队头 private NodeT tail; // 队尾 private int size; // 入队 public boolean offer(T value) { NodeT newNode new Node(value); if (tail null) { // 队列为空 head tail newNode; } else { tail.next newNode; newNode.prev tail; tail newNode; } size; return true; } // 出队 public T poll() { if (head null) { return null; } T value head.value; head head.next; if (head null) { tail null; // 队列变为空 } else { head.prev null; } size--; return value; } // 查看队头 public T peek() { return head null ? null : head.value; } // 判空 public boolean isEmpty() { return size 0; } // 获取大小 public int size() { return size; } }3.5 循环队列在实际应用中我们还经常使用循环队列。它底层使用数组实现通过取模运算让数组逻辑上形成一个环。为什么需要循环队列如果用普通的数组实现队列出队后队头前的空间就被浪费了。循环队列可以让这些空间被复用。如何区分空和满循环队列面临一个问题当front rear时队列既可能是空的也可能是满的。有三种解决方案记录size用一个变量记录元素个数牺牲一个位置(rear 1) % capacity front表示队列满使用标记用一个布尔变量标记是否已满下面是使用牺牲一个位置方式的实现class CircularQueue { private int[] data; private int front; // 队头指针 private int rear; // 队尾指针 private int capacity; public CircularQueue(int k) { // 多分配一个位置用于区分空和满 capacity k 1; data new int[capacity]; front 0; rear 0; } // 入队 public boolean enQueue(int value) { if (isFull()) { return false; } data[rear] value; rear (rear 1) % capacity; return true; } // 出队 public boolean deQueue() { if (isEmpty()) { return false; } front (front 1) % capacity; return true; } // 获取队头 public int Front() { if (isEmpty()) { return -1; } return data[front]; } // 获取队尾 public int Rear() { if (isEmpty()) { return -1; } // 队尾指针指向的是下一个插入位置所以队尾元素在rear-1处 return data[(rear - 1 capacity) % capacity]; } // 判空 public boolean isEmpty() { return front rear; } // 判满 public boolean isFull() { return (rear 1) % capacity front; } }数组下标循环的小技巧向后移动index (index offset) % length向前移动index (index - offset length) % length四、双端队列既能当栈又能当队列4.1 什么是双端队列双端队列DequeDouble Ended Queue​ 允许在两端进行插入和删除操作。也就是说它可以当作栈用也可以当作队列用。队头 ←→ 元素1 ←→ 元素2 ←→ 元素3 ←→ 队尾 ↑ ↑ 可插入/删除 可插入/删除4.2 Deque的使用import java.util.Deque; import java.util.LinkedList; import java.util.ArrayDeque; public class DequeDemo { public static void main(String[] args) { // 当做栈使用推荐使用ArrayDeque DequeInteger stack new ArrayDeque(); stack.push(1); // 入栈 stack.push(2); stack.push(3); System.out.println(stack.pop()); // 3出栈 System.out.println(stack.peek()); // 2查看栈顶 // 当做队列使用推荐使用LinkedList DequeInteger queue new LinkedList(); queue.offer(1); // 入队 queue.offer(2); queue.offer(3); System.out.println(queue.poll()); // 1出队 System.out.println(queue.peek()); // 2查看队头 } }为什么推荐用Deque替代StackJava官方文档已经建议使用Deque替代Stack。因为Stack继承自Vector是线程安全的有额外的同步开销而且设计上不够灵活。五、栈与队列的相互实现这是一类经典的面试题考察对两种数据结构本质的理解。5.1 用两个栈实现队列思路一个栈负责入队一个栈负责出队。class MyQueue { private StackInteger inputStack; // 入队栈 private StackInteger outputStack; // 出队栈 public MyQueue() { inputStack new Stack(); outputStack new Stack(); } // 入队直接压入inputStack public void push(int x) { inputStack.push(x); } // 出队 public int pop() { // 如果outputStack为空将inputStack全部倒入outputStack if (outputStack.empty()) { while (!inputStack.empty()) { outputStack.push(inputStack.pop()); } } return outputStack.pop(); } // 查看队头 public int peek() { if (outputStack.empty()) { while (!inputStack.empty()) { outputStack.push(inputStack.pop()); } } return outputStack.peek(); } // 判空 public boolean empty() { return inputStack.empty() outputStack.empty(); } }原理两次后进先出 先进先出。就像把一摞书搬到另一摞书上顺序就反转过来了。5.2 用两个队列实现栈思路始终保持一个队列为空入栈时加入非空队列出栈时将非空队列的前n-1个元素移到空队列中最后一个元素出队。class MyStack { private QueueInteger queue1; private QueueInteger queue2; public MyStack() { queue1 new LinkedList(); queue2 new LinkedList(); } // 入栈加入非空队列 public void push(int x) { if (!queue1.isEmpty()) { queue1.offer(x); } else { queue2.offer(x); } } // 出栈 public int pop() { if (empty()) { throw new RuntimeException(栈为空); } // 将非空队列的前n-1个元素移到空队列 if (!queue1.isEmpty()) { while (queue1.size() 1) { queue2.offer(queue1.poll()); } return queue1.poll(); } else { while (queue2.size() 1) { queue1.offer(queue2.poll()); } return queue2.poll(); } } // 查看栈顶 public int top() { if (empty()) { throw new RuntimeException(栈为空); } int top pop(); push(top); // 取出来后重新入栈 return top; } // 判空 public boolean empty() { return queue1.isEmpty() queue2.isEmpty(); } }六、栈与队列的对比总结特性栈Stack队列Queue原则后进先出LIFO先进先出FIFO插入操作push栈顶offer队尾删除操作pop栈顶poll队头查看操作peek栈顶peek队头底层实现数组Vector链表LinkedList典型应用括号匹配、函数调用、撤销操作消息队列、BFS、缓冲区七、常见面试题括号匹配问题给定一个只包含(){}[]的字符串判断括号是否正确闭合逆波兰表达式求值计算后缀表达式的值最小栈设计一个能在O(1)时间内获取最小值的栈用栈实现队列用两个栈模拟队列的行为用队列实现栈用两个队列模拟栈的行为设计循环队列设计一个能复用空间的循环队列八、总结与学习建议8.1 核心要点回顾栈是后进先出的线性表只能在栈顶操作队列是先进先出的线性表队尾入队、队头出队双端队列Deque​ 兼具栈和队列的功能推荐替代Stack使用循环队列用数组实现通过取模运算复用空间栈和队列可以互相实现体现了数据结构的灵活性8.2 学习建议画图理解栈和队列的操作逻辑很适合画图辅助理解动手实现自己手写一遍栈和队列的底层实现刷题巩固在LeetCode上搜索Stack和Queue标签从简单题开始刷起联系实际想想你写的代码中哪些地方可以用栈或队列来优化如果你觉得这篇文章对你有帮助欢迎点赞收藏。下一篇我们将深入Java集合框架的更多内容敬请期待注本文为个人学习总结所有代码示例均为独立编写。建议读者在学习过程中结合JDK官方文档和源码进行验证。