深入解析 Stack 和 Queue：从原理到实战应用

一、栈（Stack）基础概念

栈是一种操作受限的线性数据结构，遵循后进先出（LIFO） 原则，只允许在栈顶进行插入和删除操作。

1.1 栈的核心特性

• 基本操作：

  • push(): 元素入栈（栈顶添加）
  • pop(): 元素出栈（栈顶移除）
  • peek(): 查看栈顶元素
  • isEmpty(): 判断栈是否为空

• 现实类比：

  • 子弹夹：最后压入的子弹最先射出
  • 书本堆叠：最后放的书最先取出
  • 函数调用栈：最近调用的函数最先返回

1.2 栈的底层实现

栈可通过两种方式实现：

// 数组实现（顺序栈）
class ArrayStack {private int[] data;private int top = -1; // 栈顶指针public void push(int val) {data[++top] = val;}
}// 链表实现（链式栈）
class LinkedStack {static class Node {int val;Node next;}private Node top;
}

二、队列（Queue）基础概念

队列是一种操作受限的线性数据结构，遵循先进先出（FIFO） 原则，允许在队尾添加元素，在队头移除元素。

2.1 队列的核心特性

• 基本操作：

  • enqueue(): 元素入队（队尾添加）
  • dequeue(): 元素出队（队头移除）
  • front(): 获取队头元素
  • isEmpty(): 判断队列是否为空

• 现实类比：

  • 排队购票：先来的人先获得服务
  • 打印机队列：先提交的任务先打印
  • 消息队列：先发送的消息先被处理

2.2 队列的底层实现

// 数组实现（循环队列）
class CircularQueue {private int[] data;private int front = 0;private int rear = 0;public void enqueue(int val) {data[rear] = val;rear = (rear + 1) % data.length;}
}// 链表实现（链式队列）
class LinkedQueue {static class Node {int val;Node next;}private Node head; // 队头private Node tail; // 队尾
}

三、Java 集合框架中的实现

3.1 Stack 类（不推荐使用）

Stack<Integer> stack = new Stack<>();
stack.push(1);
int top = stack.pop(); // 1

问题：

1. 继承自 Vector（线程安全但性能差）
2. 方法同步导致效率低下
3. 官方推荐使用 Deque 替代

3.2 Queue 接口实现

// 常用实现类
Queue<Integer> arrayQueue = new ArrayDeque<>(); // 数组实现
Queue<Integer> linkedQueue = new LinkedList<>(); // 链表实现// 基本操作
queue.offer(1); // 入队（推荐）
queue.poll();   // 出队（推荐）
queue.peek();   // 查看队头

3.3 Deque 双端队列

Deque<Integer> deque = new ArrayDeque<>();
// 可作为栈使用
deque.push(1); // 入栈
deque.pop();   // 出栈// 可作为队列使用
deque.offer(1); // 入队
deque.poll();   // 出队// 双端操作
deque.offerFirst(1); // 队头入
deque.offerLast(2);  // 队尾入

ArrayDeque vs LinkedList：

四、核心源码解析

4.1 ArrayDeque 扩容机制

// 简化版扩容源码
private void doubleCapacity() {int newCapacity = elements.length << 1; // 双倍扩容Object[] a = new Object[newCapacity];// 分两段拷贝数据System.arraycopy(elements, 0, a, 0, head);System.arraycopy(elements, head, a, head + capacity, capacity - head);elements = a;tail = head + capacity; // 重置尾指针capacity = newCapacity;
}

 4.2 ArrayDeque 循环索引计算

// 关键索引计算方法
final int inc(int i, int modulus) {return (++i >= modulus) ? 0 : i;
}final int dec(int i, int modulus) {return (--i < 0) ? modulus - 1 : i;
}

4.3 LinkedList 队列操作

// 入队操作
public boolean offer(E e) {return add(e);
}void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;if (l == null)first = newNode;elsel.next = newNode;size++;
}

五、栈的应用场景与实战

5.1 括号匹配（编译器基础）

public boolean isValid(String s) {Deque<Character> stack = new ArrayDeque<>();for (char c : s.toCharArray()) {if (c == '(') stack.push(')');else if (c == '[') stack.push(']');else if (c == '{') stack.push('}');else if (stack.isEmpty() || stack.pop() != c) return false;}return stack.isEmpty();
}

5.2 逆波兰表达式计算

public int evalRPN(String[] tokens) {Deque<Integer> stack = new ArrayDeque<>();for (String token : tokens) {switch (token) {case "+": stack.push(stack.pop() + stack.pop()); break;case "*": stack.push(stack.pop() * stack.pop()); break;case "-": int b = stack.pop(), a = stack.pop();stack.push(a - b); break;case "/": b = stack.pop(); a = stack.pop();stack.push(a / b); break;default: stack.push(Integer.parseInt(token));}}return stack.pop();
}

5.3 浏览器前进后退

class Browser {private Deque<String> backStack = new ArrayDeque<>();private Deque<String> forwardStack = new ArrayDeque<>();private String current;public void visit(String url) {if (current != null) backStack.push(current);current = url;forwardStack.clear(); // 清空前进栈}public String back() {if (backStack.isEmpty()) return null;forwardStack.push(current);current = backStack.pop();return current;}public String forward() {if (forwardStack.isEmpty()) return null;backStack.push(current);current = forwardStack.pop();return current;}
}

六、队列的应用场景与实战

6.1 生产者-消费者模型

class MessageQueue {private final Queue<String> queue = new LinkedList<>();private final int maxSize;public MessageQueue(int maxSize) {this.maxSize = maxSize;}public synchronized void produce(String msg) throws InterruptedException {while (queue.size() == maxSize) {wait(); // 队列满时等待}queue.offer(msg);notifyAll(); // 唤醒消费者}public synchronized String consume() throws InterruptedException {while (queue.isEmpty()) {wait(); // 队列空时等待}String msg = queue.poll();notifyAll(); // 唤醒生产者return msg;}
}

6.2 二叉树的层序遍历

public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList<>();if (root == null) return result;Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int levelSize = queue.size();List<Integer> level = new ArrayList<>();for (int i = 0; i < levelSize; i++) {TreeNode node = queue.poll();level.add(node.val);if (node.left != null) queue.offer(node.left);if (node.right != null) queue.offer(node.right);}result.add(level);}return result;
}

6.3 请求速率限制器

class RateLimiter {private final Queue<Long> timestamps = new LinkedList<>();private final int maxRequests;private final long timeWindow; // 毫秒public RateLimiter(int maxRequests, long timeWindow) {this.maxRequests = maxRequests;this.timeWindow = timeWindow;}public synchronized boolean allowRequest() {long now = System.currentTimeMillis();// 移除超时请求while (!timestamps.isEmpty() && now - timestamps.peek() > timeWindow) {timestamps.poll();}if (timestamps.size() < maxRequests) {timestamps.offer(now);return true;}return false;}
}

七、高级应用与经典算法

7.1 单调栈：下一个更大元素

public int[] nextGreaterElement(int[] nums) {int[] result = new int[nums.length];Arrays.fill(result, -1);Deque<Integer> stack = new ArrayDeque<>(); // 存储索引for (int i = 0; i < nums.length; i++) {while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {int idx = stack.pop();result[idx] = nums[i];}stack.push(i);}return result;
}

7.2 双队列实现栈

class QueueStack {private Queue<Integer> q1 = new LinkedList<>();private Queue<Integer> q2 = new LinkedList<>();public void push(int x) {q2.offer(x);while (!q1.isEmpty()) {q2.offer(q1.poll());}// 交换引用Queue<Integer> temp = q1;q1 = q2;q2 = temp;}public int pop() {return q1.poll();}
}

7.3 循环队列设计

class MyCircularQueue {private int[] data;private int head;private int tail;private int size;public MyCircularQueue(int k) {data = new int[k];head = 0;tail = -1;size = 0;}public boolean enQueue(int value) {if (isFull()) return false;tail = (tail + 1) % data.length;data[tail] = value;size++;return true;}public boolean deQueue() {if (isEmpty()) return false;head = (head + 1) % data.length;size--;return true;}
}

八、性能优化与最佳实践

8.1 栈和队列选择指南

8.2 性能优化技巧 

预分配空间：//预估10000个元素
Deque<Integer> stack = new ArrayDeque<>(10000);避免装箱开销：
// 使用原始类型专有队列
IntQueue queue = new IntArrayDeque();批量操作优化：
// 一次性添加多个元素
deque.addAll(Arrays.asList(1,2,3,4,5));迭代器使用：
// 高效遍历（避免多次调用get()）
for (Iterator<Integer> it = deque.iterator(); it.hasNext();) {System.out.println(it.next());
}

8.3 常见陷阱

Stack 类误用：
// 错误：使用继承自Vector的get方法
stack.get(0); // 违反栈原则空队列操作：
// 未检查空队列
queue.remove();// 抛出NoSuchElementException并发修改异常：
for (String s : queue) {queue.remove(); // 抛出ConcurrentModificationException
}

九、总结

1. 栈是算法世界的"时间胶囊"，保存最近状态
2. 队列是系统设计的"缓冲带"，协调异步操作
3. 双端队列是灵活的多面手，融合两者优势