队列

队列是一种先进先出（FIFO, First In First Out）的数据结构，只允许在队尾插入，在队头删除。

队列的特性

• 先进先出：最先插入的元素最先被删除
• 队尾入队，队头出队
• 时间复杂度：enqueue、dequeue 都是 O(1)

队列的实现

循环队列 (数组实现)

使用取模运算和预留空间来区分“队空”和“队满”。

public class CircularQueue<E> {
    private E[] data;
    private int front;  // 队头索引
    private int rear;   // 队尾索引的下一个位置
    private int size;
    
    @SuppressWarnings("unchecked")
    public CircularQueue(int capacity) {
        this.data = (E[]) new Object[capacity + 1];  // 多开一个空间用于区分空和满
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }
    
    // 入队 - O(1)
    public boolean enqueue(E element) {
        if (isFull()) return false;
        data[rear] = element;
        rear = (rear + 1) % data.length;
        size++;
        return true;
    }
    
    // 出队 - O(1)
    public E dequeue() {
        if (isEmpty()) throw new IllegalStateException("Queue is empty");
        E element = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        return element;
    }
    
    public boolean isEmpty() { return front == rear; }
    public boolean isFull() { return (rear + 1) % data.length == front; }
}

链表实现

使用队头和队尾指针，实现两端的高效操作。

public class LinkedQueue<E> {
    private static class Node<E> {
        E val;
        Node<E> next;
        Node(E val) { this.val = val; }
    }
    
    private Node<E> front;  // 队头
    private Node<E> rear;   // 队尾
    private int size;
    
    // 入队 - O(1)
    public void enqueue(E element) {
        Node<E> newNode = new Node<>(element);
        if (rear == null) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }
    
    // 出队 - O(1)
    public E dequeue() {
        if (isEmpty()) throw new IllegalStateException("Queue is empty");
        E element = front.val;
        front = front.next;
        if (front == null) rear = null;
        size--;
        return element;
    }
    
    public boolean isEmpty() { return size == 0; }
}

队列的应用

1. 层序遍历 (BFS)

二叉树或图的广度优先搜索通常使用队列维护待访问的节点。

// 二叉树层序遍历
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;
}

2. 用栈实现队列 / 用队列实现栈

这类平衡问题在面试中很常见。

双端队列 Deque

双端队列允许在两端进行插入和删除。Java 中 ArrayDeque 是其常见的高效实现，可以作为栈也可以作为队列。

滑动窗口最大值

使用单调递减的双端队列存储索引。

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();  // 存储索引，其值在数组中单调递减
    for (int i = 0; i < n; i++) {
        // 移除超出窗口的元素
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) deque.pollFirst();
        // 维护其单调递减
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) deque.pollLast();
        deque.offerLast(i);
        // 记录当前窗口最大值
        if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
    }
    return result;
}

练习

1. LeetCode 102：二叉树的层序遍历
2. LeetCode 232：用栈实现队列
3. LeetCode 225：用队列实现栈
4. LeetCode 239：滑动窗口最大值
5. LeetCode 622：设计循环队列
6. LeetCode 641：设计循环双端队列