7.栈（Stack）与队列（Queue）

引言

在计算机科学领域，栈与队列是两种最基础且应用最广泛的数据结构。它们不仅支撑着现代编程语言的核心功能（如函数调用栈、消息队列），更是理解复杂算法（如深度优先搜索、广度优先搜索）的基石。

核心价值点

底层原理可视化：通过动态示意图解析栈的"羽毛球筒"模型与队列的"排队取号"机制性能对比实验室：实测不同底层容器（数组/链表）在栈/队列操作中的时间复杂度差异异常处理指南：系统梳理空栈/空队列场景下的安全操作模式工程化实践：结合Spring框架消息队列、Android事件分发等真实场景案例

第一章：栈（Stack）

1.1 核心概念解析

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

类比模型：

羽毛球筒：最后放入的球最先取出浏览器历史记录：后退按钮总是返回最近访问的页面函数调用栈：程序执行时的方法调用顺序

1.2 Java标准库实现剖析

1.2.1 遗留的Stack类（不推荐）

import java.util.Stack;

public class LegacyStackDemo {

public static void main(String[] args) {

Stack stack = new Stack<>();

stack.push(1);

stack.push(2);

System.out.println("栈顶元素: " + stack.peek()); // 2

System.out.println("出栈元素: " + stack.pop()); // 2

System.out.println("栈是否为空: " + stack.empty()); // false

}

}

缺陷警示：

所有方法同步（synchronized）导致单线程性能损耗JDK官方文档明确标注为"遗留类"，建议使用Deque替代

1.2.2 现代实现：Deque接口

import java.util.ArrayDeque;

import java.util.Deque;

public class DequeStackDemo {

public static void main(String[] args) {

Deque stack = new ArrayDeque<>();

stack.push(10);

stack.push(20);

System.out.println("栈大小: " + stack.size()); // 2

System.out.println("栈顶元素: " + stack.peek()); // 20

stack.pop();

System.out.println("新栈顶: " + stack.peek()); // 10

}

}

优势对比：

特性Stack类ArrayDeque线程安全是否性能慢快（3-5倍）方法完整性缺失完整1.3 自定义栈实现（数组版）

1.3.1 基础实现

public class ArrayStack {

private Object[] elements;

private int top;

private int capacity;

public ArrayStack(int capacity) {

this.capacity = capacity;

elements = new Object[capacity];

top = -1;

}

// 入栈操作（带扩容机制）

public void push(T item) {

if (isFull()) {

resize(capacity * 2);

}

elements[++top] = item;

}

// 出栈操作（安全模式）

public T pop() {

if (isEmpty()) {

throw new RuntimeException("Stack is empty");

}

@SuppressWarnings("unchecked")

T item = (T) elements[top];

elements[top--] = null; // 防止内存泄漏

return item;

}

// 动态扩容实现

private void resize(int newCapacity) {

Object[] newElements = new Object[newCapacity];

System.arraycopy(elements, 0, newElements, 0, top + 1);

elements = newElements;

capacity = newCapacity;

}

}

1.3.2 链表实现方案

public class LinkedStack {

private static class Node {

T data;

Node next;

Node(T data) {

this.data = data;

}

}

private Node top;

public void push(T item) {

Node newNode = new Node<>(item);

newNode.next = top;

top = newNode;

}

public T pop() {

if (isEmpty()) {

throw new RuntimeException("Stack is empty");

}

T item = top.data;

top = top.next;

return item;

}

}

1.4 经典应用场景实战

1.4.1 括号匹配算法

import java.util.Stack;

public class BracketValidator {

public static boolean isValid(String s) {

Stack stack = new Stack<>();

for (char c : s.toCharArray()) {

switch (c) {

case '(':

case '[':

case '{':

stack.push(c);

break;

case ')':

if (stack.isEmpty() || stack.pop() != '(') return false;

break;

case ']':

if (stack.isEmpty() || stack.pop() != '[') return false;

break;

case '}':

if (stack.isEmpty() || stack.pop() != '{') return false;

break;

}

}

return stack.isEmpty();

}

}

1.4.2 表达式求值（逆波兰表示法）

import java.util.Stack;

public class ExpressionEvaluator {

public static int evalRPN(String[] tokens) {

Stack 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 "/":

b = stack.pop();

a = stack.pop();

stack.push(a / b);

break;

default:

stack.push(Integer.parseInt(token));

}

}

return stack.pop();

}

}

第二章：队列（Queue）

2.1 核心概念解析

定义：队列是一种遵循先进先出（FIFO）原则的线性数据结构，允许在队尾插入（enqueue）元素，在队头删除（dequeue）元素。

类比模型：

银行排队系统：先到先服务打印机任务队列：按提交顺序处理文档消息中间件：Kafka/RabbitMQ的消息传递机制

2.2 Java标准库实现对比

2.2.1 LinkedList实现

import java.util.LinkedList;

import java.util.Queue;

public class LinkedListQueueDemo {

public static void main(String[] args) {

Queue queue = new LinkedList<>();

queue.offer("Task1");

queue.offer("Task2");

System.out.println("队头元素: " + queue.peek()); // Task1

System.out.println("出队元素: " + queue.poll()); // Task1

System.out.println("队列大小: " + queue.size()); // 1

}

}

2.2.2 ArrayDeque实现（推荐）

import java.util.ArrayDeque;

import java.util.Queue;

public class ArrayDequeQueueDemo {

public static void main(String[] args) {

Queue queue = new ArrayDeque<>();

queue.offer(100);

queue.offer(200);

System.out.println("队列是否包含100: " + queue.contains(100)); // true

queue.poll();

System.out.println("新队头: " + queue.peek()); // 200

}

}

性能对比：

操作LinkedListArrayDequeoffer()O(1)O(1)poll()O(1)O(1)peek()O(1)O(1)内存占用高（节点指针）低（连续存储）2.3 自定义队列实现方案

2.3.1 数组实现（循环队列）

public class CircularQueue {

private Object[] elements;

private int front;

private int rear;

private int size;

private final int capacity;

public CircularQueue(int capacity) {

this.capacity = capacity;

elements = new Object[capacity];

front = rear = 0;

}

public boolean enqueue(T item) {

if (isFull()) {

return false;

}

elements[rear] = item;

rear = (rear + 1) % capacity;

size++;

return true;

}

public T dequeue() {

if (isEmpty()) {

throw new RuntimeException("Queue is empty");

}

@SuppressWarnings("unchecked")

T item = (T) elements[front];

elements[front] = null; // 防止内存泄漏

front = (front + 1) % capacity;

size--;

return item;

}

}

2.3.2 链表实现方案

public class LinkedQueue {

private static class Node {

T data;

Node next;

Node(T data) {

this.data = data;

}

}

private Node front;

private Node rear;

public void enqueue(T item) {

Node newNode = new Node<>(item);

if (isEmpty()) {

front = rear = newNode;

} else {

rear.next = newNode;

rear = newNode;

}

}

public T dequeue() {

if (isEmpty()) {

throw new RuntimeException("Queue is empty");

}

T item = front.data;

front = front.next;

if (front == null) {

rear = null;

}

return item;

}

}

2.4 高级应用场景解析

2.4.1 滑动窗口最大值

import java.util.ArrayDeque;

import java.util.Deque;

public class SlidingWindowMaximum {

public static int[] maxSlidingWindow(int[] nums, int k) {

if (nums == null || nums.length == 0) return new int[0];

Deque deque = new ArrayDeque<>();

int[] result = new int[nums.length - k + 1];

for (int i = 0; i < nums.length; i++) {

// 移除不在窗口范围内的元素索引

while (!deque.isEmpty() && deque.peek() < i - k + 1) {

deque.poll();

}

// 移除所有小于当前元素的队列元素

while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {

deque.pollLast();

}

deque.offer(i);

// 当窗口形成时记录最大值

if (i >= k - 1) {

result[i - k + 1] = nums[deque.peek()];

}

}

return result;

}

}

2.4.2 多线程生产者消费者模型

import java.util.LinkedList;

import java.util.Queue;

import java.util.concurrent.locks.Condition;

import java.util.concurrent.locks.Lock;

import java.util.concurrent.locks.ReentrantLock;

public class BlockingQueue {

private final Queue queue = new LinkedList<>();

private final int capacity;

private final Lock lock = new ReentrantLock();

private final Condition notFull = lock.newCondition();

private final Condition notEmpty = lock.newCondition();

public BlockingQueue(int capacity) {

this.capacity = capacity;

}

public void put(T item) throws InterruptedException {

lock.lock();

try {

while (queue.size() == capacity) {

notFull.await();

}

queue.offer(item);

notEmpty.signal();

} finally {

lock.unlock();

}

}

public T take() throws InterruptedException {

lock.lock();

try {

while (queue.isEmpty()) {

notEmpty.await();

}

T item = queue.poll();

notFull.signal();

return item;

} finally {

lock.unlock();

}

}

}

第三章：栈与队列的深度融合

3.1 用队列实现栈

import java.util.LinkedList;

import java.util.Queue;

public class QueueStack {

private Queue primary = new LinkedList<>();

private Queue secondary = new LinkedList<>();

public void push(T item) {

primary.offer(item);

}

public T pop() {

while (primary.size() > 1) {

secondary.offer(primary.poll());

}

T item = primary.poll();

// 交换队列引用

Queue temp = primary;

primary = secondary;

secondary = temp;

return item;

}

}

3.2 用栈实现队列

import java.util.Stack;

public class StackQueue {

private Stack inStack = new Stack<>();

private Stack outStack = new Stack<>();

public void enqueue(T item) {

inStack.push(item);

}

public T dequeue() {

if (outStack.isEmpty()) {

while (!inStack.isEmpty()) {

outStack.push(inStack.pop());

}

}

return outStack.pop();

}

}

第四章：性能调优与最佳实践

4.1 容量规划策略

预分配原则：对于已知规模的场景，初始化时分配足够容量

// 预分配1000个元素的队列

Queue orders = new ArrayDeque<>(1000);

动态扩容阈值：数组实现时建议扩容因子为1.5-2.0

// 自定义扩容策略示例

private void ensureCapacity(int minCapacity) {

if (minCapacity > elements.length) {

int newCapacity = elements.length * 2;

if (newCapacity < minCapacity) {

newCapacity = minCapacity;

}

resize(newCapacity);

}

}

4.2 异常处理模式

安全方法优先：推荐使用offer()/poll()而非add()/remove()

Queue queue = new ArrayDeque<>(1);

boolean success = queue.offer("item"); // 返回false而非抛异常

空容器处理范式

public T safePoll(Queue queue) {

return queue.isEmpty() ? null : queue.poll();

}

4.3 并发场景解决方案

线程安全容器选择

场景推荐实现单生产者单消费者ConcurrentLinkedQueue多生产者多消费者LinkedBlockingQueue优先级队列PriorityBlockingQueue

CAS操作优化：对于高频竞争场景，可考虑使用AtomicReferenceArray实现无锁队列

第五章：实战项目：基于队列的限流器实现

5.1 令牌桶算法实现

import java.util.concurrent.TimeUnit;

public class TokenBucket {

private final long capacity;

private final long refillTokens;

private long tokens;

private long lastRefillTime;

public TokenBucket(long capacity, long refillTokens, long refillPeriod, TimeUnit unit) {

this.capacity = capacity;

this.refillTokens = refillTokens;

this.tokens = capacity;

this.lastRefillTime = System.nanoTime();

}

public synchronized boolean tryConsume() {

refill();

if (tokens > 0) {

tokens--;

return true;

}

return false;

}

private void refill() {

long now = System.nanoTime();

long elapsedTime = now - lastRefillTime;

// 转换为纳秒单位的周期

// 实际项目中应使用更精确的时间计算

long tokensToAdd = elapsedTime * refillTokens / 1_000_000_000L;

if (tokensToAdd > 0) {

tokens = Math.min(capacity, tokens + tokensToAdd);

lastRefillTime = now;

}

}

}

5.2 漏桶算法实现

import java.util.concurrent.TimeUnit;

public class LeakyBucket {

private final long capacity;

private final long leakRate; // 每秒漏出的令牌数

private long water;

private long lastLeakTime;

public LeakyBucket(long capacity, long leakRate) {

this.capacity = capacity;

this.leakRate = leakRate;

this.water = 0;

this.lastLeakTime = System.nanoTime();

}

public synchronized boolean tryConsume() {

leak();

if (water < capacity) {

water++;

return true;

}

return false;

}

private void leak() {

long now = System.nanoTime();

long elapsedTime = now - lastLeakTime;

// 转换为秒单位的漏出量

long leakedAmount = elapsedTime * leakRate / 1_000_000_000L;

if (leakedAmount > 0) {

water = Math.max(0, water - leakedAmount);

lastLeakTime = now;

}

}

}

第六章：学习路径与资源推荐

6.1 渐进式学习路线

基础阶段：掌握栈/队列的基本操作

完成所有代码示例的手动实现理解时间复杂度分析

进阶阶段：理解底层实现原理

研究ArrayDeque的源码实现实现循环队列的完整版本

实战阶段：工程化应用

实现消息队列中间件核心逻辑完成限流器的压力测试

6.2 经典学习资源

书籍推荐

《算法导论》第3版：第10章栈与队列《Java数据结构与算法分析》：第3章线性数据结构

在线课程

Coursera《数据结构与算法专项课程》MIT OpenCourseWare《Introduction to Algorithms》

开源项目

Apache Kafka消息队列核心实现Guava的Monitor类（线程安全容器）