栈与队列

1. 栈（Stack）

1.1 栈的基本概念

栈是一种后进先出（Last In First Out, LIFO）的线性数据结构。可以想象成一叠盘子——最后放上去的盘子最先被取走。

入栈 (push)    出栈 (pop)
    ↓              ↑
  ┌───┐
  │ 5 │  ← 栈顶 (top)
  ├───┤
  │ 3 │
  ├───┤
  │ 1 │
  ├───┤
  │ 7 │  ← 栈底 (bottom)
  └───┘

1.2 栈的核心操作

2. 栈的实现

2.1 顺序栈（基于数组）

// Java：基于数组的顺序栈
public class ArrayStack<E> {
    private Object[] data;
    private int top;        // 栈顶指针，-1 表示空栈
    private int capacity;

    public ArrayStack(int capacity) {
        this.data = new Object[capacity];
        this.top = -1;
        this.capacity = capacity;
    }

    public void push(E element) {
        if (top == capacity - 1) {
            resize(capacity * 2); // 扩容
        }
        data[++top] = element;
    }

    @SuppressWarnings("unchecked")
    public E pop() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        E element = (E) data[top];
        data[top--] = null; // 帮助 GC
        return element;
    }

    @SuppressWarnings("unchecked")
    public E peek() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return (E) data[top];
    }

    public boolean isEmpty() { return top == -1; }
    public int size() { return top + 1; }

    private void resize(int newCapacity) {
        Object[] newData = new Object[newCapacity];
        System.arraycopy(data, 0, newData, 0, top + 1);
        data = newData;
        capacity = newCapacity;
    }
}

2.2 链式栈（基于链表）

// Java：基于链表的链式栈
public class LinkedStack<E> {
    private static class Node<E> {
        E value;
        Node<E> next;
        Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    private Node<E> top;  // 栈顶节点
    private int size;

    public void push(E element) {
        top = new Node<>(element, top);
        size++;
    }

    public E pop() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        E element = top.value;
        top = top.next;
        size--;
        return element;
    }

    public E peek() {
        if (isEmpty()) throw new RuntimeException("Stack is empty");
        return top.value;
    }

    public boolean isEmpty() { return top == null; }
    public int size() { return size; }
}

# Python：基于列表的栈（最常用方式）
class Stack:
    def __init__(self):
        self._data = []

    def push(self, item):
        self._data.append(item)

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._data.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._data[-1]

    def is_empty(self):
        return len(self._data) == 0

    def size(self):
        return len(self._data)

2.3 两种实现对比

3. 栈的经典应用

3.1 括号匹配

// Java：判断括号是否匹配
public boolean isValid(String s) {
    Map<Character, Character> map = Map.of(')', '(', ']', '[', '}', '{');
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (map.containsValue(c)) {
            stack.push(c);
        } else if (map.containsKey(c)) {
            if (stack.isEmpty() || stack.pop() != map.get(c)) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

# Python：括号匹配
def is_valid(s: str) -> bool:
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in pairs.values():
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

3.2 表达式求值（逆波兰表达式）

# Python：逆波兰表达式求值（LeetCode 150）
def evalRPN(tokens):
    stack = []
    for token in tokens:
        if token in '+-*/':
            b = stack.pop()
            a = stack.pop()
            if token == '+': stack.append(a + b)
            elif token == '-': stack.append(a - b)
            elif token == '*': stack.append(a * b)
            elif token == '/': stack.append(int(a / b))  # 截断向零
        else:
            stack.append(int(token))
    return stack[0]

3.3 中缀表达式转后缀表达式

// Java：中缀转后缀（调度场算法 Shunting Yard）
public String infixToPostfix(String expr) {
    StringBuilder output = new StringBuilder();
    Deque<Character> ops = new ArrayDeque<>();
    Map<Character, Integer> precedence = Map.of('+', 1, '-', 1, '*', 2, '/', 2);

    for (char c : expr.toCharArray()) {
        if (Character.isDigit(c)) {
            output.append(c);
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (ops.peek() != '(') {
                output.append(ops.pop());
            }
            ops.pop(); // 弹出 '('
        } else { // 运算符
            while (!ops.isEmpty() && ops.peek() != '('
                   && precedence.getOrDefault(ops.peek(), 0) >= precedence.get(c)) {
                output.append(ops.pop());
            }
            ops.push(c);
        }
    }
    while (!ops.isEmpty()) {
        output.append(ops.pop());
    }
    return output.toString();
}

3.4 单调栈

单调栈是栈的高级应用，用于解决”寻找下一个更大/更小元素”类问题：

// Java：每日温度（LeetCode 739）
// 找到每个位置右侧第一个更大元素的距离
public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];
    Deque<Integer> stack = new ArrayDeque<>(); // 存索引，单调递减栈

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prev = stack.pop();
            answer[prev] = i - prev;
        }
        stack.push(i);
    }
    return answer;
}

# Python：柱状图中最大矩形（LeetCode 84）
def largestRectangleArea(heights):
    stack = []  # 单调递增栈，存索引
    max_area = 0
    heights = heights + [0]  # 哨兵，确保最后清空栈

    for i, h in enumerate(heights):
        while stack and h < heights[stack[-1]]:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
    return max_area

4. 队列（Queue）

4.1 队列的基本概念

队列是一种先进先出（First In First Out, FIFO）的线性数据结构。类似于日常生活中的排队——先到的人先被服务。

入队 (enqueue)              出队 (dequeue)
    ↓                           ↑
  ┌───┬───┬───┬───┬───┐
  │ 7 │ 1 │ 3 │ 5 │   │
  └───┴───┴───┴───┴───┘
  rear                front

4.2 队列的核心操作

5. 队列的实现

5.1 循环队列（基于数组）

普通数组队列在出队后，前方空间无法复用，造成假溢出。循环队列通过取模运算将数组首尾相连，解决了这个问题。

初始状态 (capacity=6, size=3):
  ┌───┬───┬───┬───┬───┬───┐
  │   │   │ 5 │ 3 │ 1 │   │
  └───┴───┴───┴───┴───┴───┘
         rear↑    front↑

循环后 (继续入队):
  ┌───┬───┬───┬───┬───┬───┐
  │ 9 │ 8 │   │ 3 │ 1 │ 7 │
  └───┴───┴───┴───┴───┴───┘
  rear↑         front↑

// Java：循环队列
public class CircularQueue<E> {
    private Object[] data;
    private int front;
    private int rear;
    private int size;
    private int capacity;

    public CircularQueue(int capacity) {
        this.data = new Object[capacity];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
        this.capacity = capacity;
    }

    public boolean enqueue(E element) {
        if (isFull()) return false;
        data[rear] = element;
        rear = (rear + 1) % capacity;
        size++;
        return true;
    }

    @SuppressWarnings("unchecked")
    public E dequeue() {
        if (isEmpty()) throw new RuntimeException("Queue is empty");
        E element = (E) data[front];
        data[front] = null;
        front = (front + 1) % capacity;
        size--;
        return element;
    }

    @SuppressWarnings("unchecked")
    public E front() {
        if (isEmpty()) throw new RuntimeException("Queue is empty");
        return (E) data[front];
    }

    public boolean isEmpty() { return size == 0; }
    public boolean isFull() { return size == capacity; }
    public int size() { return size; }
}

# Python：循环队列（LeetCode 622）
class MyCircularQueue:
    def __init__(self, k: int):
        self.data = [0] * k
        self.front = 0
        self.rear = 0
        self.size = 0
        self.capacity = k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.data[self.rear] = value
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return True

    def Front(self) -> int:
        return -1 if self.isEmpty() else self.data[self.front]

    def Rear(self) -> int:
        return -1 if self.isEmpty() else self.data[(self.rear - 1) % self.capacity]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.capacity

5.2 链式队列（基于链表）

// Java：链式队列
public class LinkedQueue<E> {
    private static class Node<E> {
        E value;
        Node<E> next;
        Node(E value) { this.value = value; }
    }

    private Node<E> front;  // 队首
    private Node<E> rear;   // 队尾
    private int size;

    public void enqueue(E element) {
        Node<E> node = new Node<>(element);
        if (isEmpty()) {
            front = rear = node;
        } else {
            rear.next = node;
            rear = node;
        }
        size++;
    }

    public E dequeue() {
        if (isEmpty()) throw new RuntimeException("Queue is empty");
        E element = front.value;
        front = front.next;
        if (front == null) rear = null; // 队列变为空
        size--;
        return element;
    }

    public E front() {
        if (isEmpty()) throw new RuntimeException("Queue is empty");
        return front.value;
    }

    public boolean isEmpty() { return front == null; }
    public int size() { return size; }
}

5.3 两种实现对比

6. 双端队列（Deque）

6.1 双端队列概念

双端队列（Double-ended Queue，Deque）允许在两端都进行入队和出队操作，是栈和队列的泛化。

左端操作: addFirst / removeFirst / getFirst
右端操作: addLast  / removeLast  / getLast

  ┌───┬───┬───┬───┬───┐
  │ 5 │ 3 │ 1 │ 7 │ 9 │
  └───┴───┴───┴───┴───┘
  ←left              right→

6.2 双端队列的实现

// Java：使用 ArrayDeque（JDK 推荐的栈和队列实现）
// 作为栈使用
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);    // 等价于 addFirst
stack.pop();      // 等价于 removeFirst

// 作为队列使用
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);   // 等价于 addLast
queue.poll();     // 等价于 removeFirst

// 双端操作
Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(1);
deque.addLast(2);
int first = deque.removeFirst();  // 1
int last = deque.removeLast();    // 2

# Python：使用 collections.deque
from collections import deque

dq = deque()
dq.appendleft(1)   # 左端入队
dq.append(2)       # 右端入队
dq.popleft()       # 左端出队 → 1
dq.pop()           # 右端出队 → 2

# 滑动窗口最大值（LeetCode 239）——单调队列经典应用
def maxSlidingWindow(nums, k):
    dq = deque()  # 存索引，单调递减
    result = []
    for i, num in enumerate(nums):
        # 移除超出窗口的元素
        while dq and dq[0] <= i - k:
            dq.popleft()
        # 维护单调递减
        while dq and nums[dq[-1]] < num:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])
    return result

7. 栈与队列的典型应用场景

7.1 应用总览

7.2 用栈实现队列

// Java：用两个栈实现队列（LeetCode 232）
class MyQueue {
    private Deque<Integer> inStack = new ArrayDeque<>();
    private Deque<Integer> outStack = new ArrayDeque<>();

    public void push(int x) {
        inStack.push(x);
    }

    public int pop() {
        ensureOut();
        return outStack.pop();
    }

    public int peek() {
        ensureOut();
        return outStack.peek();
    }

    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }

    private void ensureOut() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop());
            }
        }
    }
}

7.3 用队列实现栈

# Python：用一个队列实现栈（LeetCode 225）
from collections import deque

class MyStack:
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        # 将前面的元素依次移到后面，使新元素成为队首
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return not self.q

7.4 BFS 中的队列应用

// Java：二叉树层序遍历（LeetCode 102）
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;
}

7.5 DFS 中的栈应用

# Python：用栈实现 DFS（二叉树前序遍历）
def preorderTraversal(root):
    if not root:
        return []
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        result.append(node.val)
        # 右子树先入栈，左子树后入栈（保证左先访问）
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

8. 各语言内置栈与队列

8.1 Java 注意事项

//  不推荐：Stack 继承自 Vector，性能差
Stack<Integer> stack = new Stack<>();

//  推荐：ArrayDeque 作为栈
Deque<Integer> stack = new ArrayDeque<>();

//  推荐：ArrayDeque 作为队列
Deque<Integer> queue = new ArrayDeque<>();

9. 总结

栈和队列是最基础的受限线性表，虽然操作简单，但应用极其广泛。理解它们的底层实现（顺序 vs 链式、循环队列避免假溢出）以及高级变体（单调栈、单调队列），是算法学习的重要基础。