队列

队列是一种基础且重要的线性数据结构，它的核心特征是"先进先出"（FIFO, First In First Out）。这种特性使得队列在许多场景中都有独特的作用，比如任务调度、消息传递、广度优先搜索等。

理解队列的本质

想象在银行排队办理业务：先来的人排在前面，先被服务；后来的人排在后面，等待前面的服务完成后才能轮到自己。这就是队列的工作方式。

队列只允许在两端进行操作：

• 队尾（Rear）：只能在这里插入元素，称为入队（Enqueue）
• 队头（Front）：只能在这里删除元素，称为出队（Dequeue）

由于只能在固定位置操作，所有基本操作的时间复杂度都是 $O(1)$。

队列与栈的对比

特性	栈	队列
操作原则	后进先出（LIFO）	先进先出（FIFO）
插入位置	栈顶	队尾
删除位置	栈顶	队头
典型应用	函数调用、表达式求值	任务调度、BFS

队列的实现

数组实现（循环队列）

使用普通数组实现队列会面临一个问题：随着不断入队和出队，队头和队尾都会向数组末尾移动，导致数组前面的空间被浪费。解决方案是使用循环队列（也叫环形缓冲区）。

循环队列通过取模运算，让队头和队尾指针在到达数组末尾后回到数组开头，从而复用已出队的空间。

public class CircularQueue<E> {
    private E[] data;
    private int front;  // 队头索引
    private int rear;   // 队尾索引（指向下一个可插入位置）
    private int size;   // 当前元素数量
    
    private static final int DEFAULT_CAPACITY = 10;
    
    @SuppressWarnings("unchecked")
    public CircularQueue() {
        this.data = (E[]) new Object[DEFAULT_CAPACITY];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }
    
    // 入队 - 均摊 O(1)
    public boolean enqueue(E element) {
        if (isFull()) {
            resize(data.length * 2);
        }
        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--;
        
        // 缩容
        if (size > 0 && size == data.length / 4) {
            resize(data.length / 2);
        }
        return element;
    }
    
    // 查看队头 - O(1)
    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return data[front];
    }
    
    public boolean isEmpty() { return size == 0; }
    public boolean isFull() { return size == data.length; }
    public int size() { return size; }
    
    @SuppressWarnings("unchecked")
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        // 从 front 开始，按顺序复制 size 个元素
        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % data.length];
        }
        data = newData;
        front = 0;
        rear = size;
    }
}

循环队列的关键点：

1. 索引计算：使用 (index + 1) % capacity 让指针循环
2. 判空判满：可以用 size 变量记录元素数量，或者牺牲一个空间来区分（当 (rear + 1) % capacity == 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 都指向新节点
            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;
        // 如果队列变空，rear 也要置空
        if (front == null) {
            rear = null;
        }
        size--;
        return element;
    }
    
    // 查看队头 - O(1)
    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return front.val;
    }
    
    public boolean isEmpty() { return size == 0; }
    public int size() { return size; }
}

为什么链表实现需要同时维护 front 和 rear？

如果只有 front 指针，入队操作需要遍历整个链表才能找到队尾，时间复杂度变成 $O(n)$。维护 rear 指针后，入队和出队都是 $O(1)$。

实现方式对比

特性	循环数组	链表
时间复杂度	均摊 $O(1)$	严格 $O(1)$
空间效率	可能有未使用空间	每个节点有额外指针开销
扩容开销	偶尔需要复制数组	无
缓存友好	是（内存连续）	否

实际应用中，如果队列大小相对稳定，循环数组更高效；如果队列大小波动很大，链表更灵活。

双端队列（Deque）

双端队列（Double-Ended Queue，发音为"deck"）是一种两端都可以进行插入和删除操作的队列。它结合了栈和队列的特性，既可以作为栈使用（LIFO），也可以作为队列使用（FIFO）。

接口定义

Java 的 Deque 接口定义了以下核心方法：

操作	队头操作（抛异常）	队头操作（返回特殊值）	队尾操作（抛异常）	队尾操作（返回特殊值）
插入	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
删除	removeFirst()	pollFirst()	removeLast()	pollLast()
查看	getFirst()	peekFirst()	getLast()	peekLast()

当 Deque 作为队列使用时：

• add(e) 等价于 addLast(e)
• offer(e) 等价于 offerLast(e)
• remove() 等价于 removeFirst()
• poll() 等价于 pollFirst()

当 Deque 作为栈使用时：

• push(e) 等价于 addFirst(e)
• pop() 等价于 removeFirst()
• peek() 等价于 peekFirst()

ArrayDeque 实现原理

Java 的 ArrayDeque 是双端队列的高效实现，基于循环数组：

// 使用 ArrayDeque 作为栈
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);  // 添加到队头
stack.push(2);
stack.pop();    // 从队头移除，返回 2

// 使用 ArrayDeque 作为队列
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); // 添加到队尾
queue.offer(2);
queue.poll();   // 从队头移除，返回 1

ArrayDeque 相比 Stack 类的优势：

• 性能更好：Stack 是线程安全的，有同步开销
• 设计更合理：Stack 继承自 Vector，暴露了不该暴露的方法
• 官方推荐：Java 文档明确建议使用 Deque 替代 Stack

滑动窗口最大值

双端队列的一个重要应用是解决滑动窗口问题。给定一个数组和窗口大小 $k$，求每个窗口内的最大值。

思路：维护一个单调递减的双端队列，存储元素索引（不是值）。队列头部始终是当前窗口的最大值索引。

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++) {
        // 移除超出窗口的元素（窗口左边界是 i - k + 1）
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        
        // 维护单调递减：移除所有小于当前元素的值
        // 因为这些值不可能成为未来窗口的最大值
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        
        deque.offerLast(i);
        
        // 当窗口形成后（i >= k - 1），记录结果
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

时间复杂度分析：每个元素最多入队一次、出队一次，所以是 $O(n)$。

优先队列（Priority Queue）

优先队列是一种特殊的队列，元素的出队顺序不是按照入队顺序，而是按照优先级（通常是元素的大小）。优先级最高的元素最先出队。

实现原理：二叉堆

优先队列通常使用二叉堆实现。二叉堆是一棵完全二叉树，满足堆序性质：

• 最小堆：每个节点的值都小于等于其子节点的值，堆顶是最小值
• 最大堆：每个节点的值都大于等于其子节点的值，堆顶是最大值

由于是完全二叉树，可以用数组高效存储。对于索引 $i$ 的节点：

• 父节点索引：$(i - 1) / 2$
• 左子节点索引：$2i + 1$
• 右子节点索引：$2i + 2$

核心操作

public class MinHeap {
    private int[] heap;
    private int size;
    
    public MinHeap(int capacity) {
        this.heap = new int[capacity];
        this.size = 0;
    }
    
    // 入队：添加到末尾，然后上浮
    public void offer(int val) {
        heap[size] = val;
        siftUp(size);
        size++;
    }
    
    // 上浮操作：与父节点比较，如果更小则交换
    private void siftUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[parent] <= heap[i]) break;
            swap(parent, i);
            i = parent;
        }
    }
    
    // 出队：保存堆顶，用末尾元素替换堆顶，然后下沉
    public int poll() {
        int result = heap[0];
        heap[0] = heap[size - 1];
        size--;
        siftDown(0);
        return result;
    }
    
    // 下沉操作：与较小的子节点比较，如果更大则交换
    private void siftDown(int i) {
        while (true) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int smallest = i;
            
            if (left < size && heap[left] < heap[smallest]) {
                smallest = left;
            }
            if (right < size && heap[right] < heap[smallest]) {
                smallest = right;
            }
            if (smallest == i) break;
            
            swap(i, smallest);
            i = smallest;
        }
    }
    
    // 查看堆顶 - O(1)
    public int peek() {
        return heap[0];
    }
    
    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

时间复杂度

操作	时间复杂度	说明
入队（offer）	$O(\log n)$	可能需要上浮
出队（poll）	$O(\log n)$	需要下沉
查看堆顶（peek）	$O(1)$	直接访问数组首元素
建堆（heapify）	$O(n)$	从底向上构建

Java 中的 PriorityQueue

Java 的 PriorityQueue 是最小堆实现，堆顶是最小元素：

// 默认是最小堆
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(3);
minHeap.offer(1);
minHeap.offer(2);
minHeap.poll();  // 返回 1（最小值）

// 使用 Comparator 构建最大堆
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
    (a, b) -> b - a  // 降序比较器
);
maxHeap.offer(3);
maxHeap.offer(1);
maxHeap.offer(2);
maxHeap.poll();  // 返回 3（最大值）

// 自定义对象的优先级
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparingInt(Task::getPriority)
);

注意事项：

• PriorityQueue 不允许 null 元素
• 不是线程安全的，多线程环境使用 PriorityBlockingQueue
• 迭代器不保证任何特定顺序

经典应用：合并 K 个有序链表

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    
    // 使用优先队列，按节点值排序
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>(
        Comparator.comparingInt(node -> node.val)
    );
    
    // 将所有链表的头节点加入堆
    for (ListNode node : lists) {
        if (node != null) {
            minHeap.offer(node);
        }
    }
    
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;
    
    while (!minHeap.isEmpty()) {
        ListNode minNode = minHeap.poll();  // 取出最小节点
        current.next = minNode;
        current = current.next;
        
        // 如果该节点还有后续节点，加入堆
        if (minNode.next != null) {
            minHeap.offer(minNode.next);
        }
    }
    
    return dummy.next;
}

阻塞队列（BlockingQueue）

阻塞队列是 Java 并发包中重要的数据结构，主要用于生产者-消费者场景。与普通队列不同，阻塞队列在队列满时入队会阻塞，队列空时出队会阻塞。

核心方法

BlockingQueue 的方法分为四类：

操作	抛异常	返回特殊值	阻塞等待	超时等待
入队	add(e)	offer(e)	put(e)	offer(e, time, unit)
出队	remove()	poll()	take()	poll(time, unit)
查看	element()	peek()	不支持	不支持

常见实现类

实现类	特点	适用场景
ArrayBlockingQueue	有界，基于数组，需要指定容量	资源受限的生产者-消费者
LinkedBlockingQueue	可选有界，基于链表，默认容量 Integer.MAX_VALUE	无界或大容量场景
PriorityBlockingQueue	无界，支持优先级排序	需要按优先级处理任务
SynchronousQueue	容量为 0，直接传递	线程间直接传递数据

生产者-消费者示例

public class ProducerConsumer {
    private final BlockingQueue<String> queue;
    private volatile boolean running = true;
    
    public ProducerConsumer(int capacity) {
        this.queue = new ArrayBlockingQueue<>(capacity);
    }
    
    // 生产者
    class Producer implements Runnable {
        @Override
        public void run() {
            try {
                while (running) {
                    String item = produce();
                    // 队列满时会阻塞
                    queue.put(item);
                    System.out.println("Produced: " + item);
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
        
        private String produce() {
            return "Item-" + System.currentTimeMillis();
        }
    }
    
    // 消费者
    class Consumer implements Runnable {
        @Override
        public void run() {
            try {
                while (running || !queue.isEmpty()) {
                    // 队列空时会阻塞
                    String item = queue.take();
                    System.out.println("Consumed: " + item);
                }
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }
    
    public void start(int producers, int consumers) {
        for (int i = 0; i < producers; i++) {
            new Thread(new Producer()).start();
        }
        for (int i = 0; i < consumers; i++) {
            new Thread(new Consumer()).start();
        }
    }
}

单调队列

单调队列是一种特殊的双端队列，队列中的元素保持单调递增或单调递减。它是解决滑动窗口极值问题的利器。

工作原理

单调队列的核心思想是"淘汰不可能成为答案的元素"：

1. 单调递减队列（找最大值）：新元素入队时，移除所有比它小的元素
2. 单调递增队列（找最小值）：新元素入队时，移除所有比它大的元素

通用模板

// 单调队列模板（单调递减，用于求最大值）
public int[] monotonicQueue(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++) {
        // 步骤1：移除超出窗口的元素
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        
        // 步骤2：维护单调性（单调递减）
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        
        // 步骤3：加入当前元素
        deque.offerLast(i);
        
        // 步骤4：窗口形成后取结果
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

应用：滑动窗口中位数

使用两个优先队列（一个大顶堆、一个小顶堆）维护窗口内元素：

public double[] medianSlidingWindow(int[] nums, int k) {
    // 大顶堆存储较小的一半
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
    // 小顶堆存储较大的一半
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    
    // 平衡两个堆，保证 maxHeap.size() >= minHeap.size()
    // 且 maxHeap.size() - minHeap.size() <= 1
    
    double[] result = new double[nums.length - k + 1];
    
    for (int i = 0; i < nums.length; i++) {
        // 添加元素
        if (maxHeap.isEmpty() || nums[i] <= maxHeap.peek()) {
            maxHeap.offer(nums[i]);
        } else {
            minHeap.offer(nums[i]);
        }
        
        // 平衡两个堆
        balance(maxHeap, minHeap);
        
        // 窗口形成后计算中位数
        if (i >= k - 1) {
            if (k % 2 == 1) {
                result[i - k + 1] = maxHeap.peek();
            } else {
                result[i - k + 1] = (maxHeap.peek() / 2.0 + minHeap.peek() / 2.0);
            }
            
            // 移除窗口最左边的元素
            int toRemove = nums[i - k + 1];
            if (toRemove <= maxHeap.peek()) {
                maxHeap.remove(toRemove);
            } else {
                minHeap.remove(toRemove);
            }
            balance(maxHeap, minHeap);
        }
    }
    
    return result;
}

private void balance(PriorityQueue<Integer> maxHeap, PriorityQueue<Integer> minHeap) {
    while (maxHeap.size() > minHeap.size() + 1) {
        minHeap.offer(maxHeap.poll());
    }
    while (minHeap.size() > maxHeap.size()) {
        maxHeap.offer(minHeap.poll());
    }
}

队列的经典应用

广度优先搜索（BFS）

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;
}

// 图的最短路径（无权图）
public int shortestPath(int[][] graph, int start, int end) {
    int n = graph.length;
    boolean[] visited = new boolean[n];
    int[] distance = new int[n];
    Arrays.fill(distance, -1);
    
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;
    distance[start] = 0;
    
    while (!queue.isEmpty()) {
        int current = queue.poll();
        if (current == end) return distance[current];
        
        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                distance[neighbor] = distance[current] + 1;
                queue.offer(neighbor);
            }
        }
    }
    return -1;  // 无法到达
}

为什么 BFS 能保证最短路径？

BFS 按"层"扩展，先访问距离起点为 1 的节点，再访问距离为 2 的节点，以此类推。当第一次访问到终点时，一定是最短路径。

用栈实现队列 / 用队列实现栈

这类问题考察对数据结构本质的理解。

用两个栈实现队列：

public class MyQueue {
    private Deque<Integer> inStack;   // 入队栈
    private Deque<Integer> outStack;  // 出队栈
    
    public MyQueue() {
        inStack = new ArrayDeque<>();
        outStack = new ArrayDeque<>();
    }
    
    // 入队：直接压入 inStack
    public void push(int x) {
        inStack.push(x);
    }
    
    // 出队：如果 outStack 为空，先把 inStack 全部倒入 outStack
    public int pop() {
        if (outStack.isEmpty()) {
            transfer();
        }
        return outStack.pop();
    }
    
    public int peek() {
        if (outStack.isEmpty()) {
            transfer();
        }
        return outStack.peek();
    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
    
    // 将 inStack 的元素全部倒入 outStack
    // 关键：这会反转元素顺序，实现 FIFO
    private void transfer() {
        while (!inStack.isEmpty()) {
            outStack.push(inStack.pop());
        }
    }
}

用两个队列实现栈：

public class MyStack {
    private Queue<Integer> mainQueue;
    private Queue<Integer> helperQueue;
    
    public MyStack() {
        mainQueue = new LinkedList<>();
        helperQueue = new LinkedList<>();
    }
    
    // 入栈：先加入 helperQueue，然后把 mainQueue 的元素全部移过来
    // 这样新元素就在队头（栈顶）
    public void push(int x) {
        helperQueue.offer(x);
        while (!mainQueue.isEmpty()) {
            helperQueue.offer(mainQueue.poll());
        }
        // 交换引用
        Queue<Integer> temp = mainQueue;
        mainQueue = helperQueue;
        helperQueue = temp;
    }
    
    public int pop() {
        return mainQueue.poll();
    }
    
    public int top() {
        return mainQueue.peek();
    }
    
    public boolean empty() {
        return mainQueue.isEmpty();
    }
}

拓扑排序

拓扑排序用于解决依赖关系问题，如课程安排、编译顺序等。使用队列实现的 Kahn 算法是一种常用的拓扑排序方法。

public int[] findOrder(int numCourses, int[][] prerequisites) {
    // 构建邻接表和入度数组
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[numCourses];
    
    for (int i = 0; i < numCourses; i++) {
        graph.add(new ArrayList<>());
    }
    
    for (int[] prereq : prerequisites) {
        int course = prereq[0];
        int prerequisite = prereq[1];
        graph.get(prerequisite).add(course);
        inDegree[course]++;
    }
    
    // 将入度为 0 的节点加入队列
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }
    
    int[] result = new int[numCourses];
    int index = 0;
    
    while (!queue.isEmpty()) {
        int course = queue.poll();
        result[index++] = course;
        
        // 减少邻居的入度，如果入度变为 0 则加入队列
        for (int neighbor : graph.get(course)) {
            if (--inDegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }
    
    // 如果存在环，无法完成所有课程
    return index == numCourses ? result : new int[0];
}

最佳实践

选择正确的实现

// 作为普通队列使用
Queue<Integer> queue = new LinkedList<>();  // 简单场景
Queue<Integer> queue = new ArrayDeque<>();  // 性能更好的选择

// 作为双端队列或栈使用
Deque<Integer> deque = new ArrayDeque<>();  // 推荐

// 需要优先级排序
Queue<Integer> pq = new PriorityQueue<>();  // 最小堆

// 多线程环境
BlockingQueue<Integer> bq = new ArrayBlockingQueue<>(100);

方法选择指南

场景	推荐方法	原因
队列容量足够	add(e) / remove()	简洁
队列可能满/空	offer(e) / poll()	安全，不抛异常
需要阻塞等待	put(e) / take()	生产者-消费者模式
需要超时	offer(e, time, unit)	避免无限等待

避免常见陷阱

// 错误：使用 remove() 时没有检查
Queue<Integer> queue = new LinkedList<>();
queue.remove();  // 抛出 NoSuchElementException

// 正确：使用 poll() 或先检查
if (!queue.isEmpty()) {
    queue.poll();
}
Integer item = queue.poll();  // 返回 null 而不是抛异常

// 错误：PriorityQueue 迭代不保证顺序
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3);
pq.offer(1);
for (int x : pq) {
    System.out.println(x);  // 输出顺序不确定！
}

// 正确：使用 poll() 获取有序元素
while (!pq.isEmpty()) {
    System.out.println(pq.poll());  // 1, 3
}

小结

队列是一种简单但应用广泛的数据结构：

1. 普通队列：先进先出，适合任务调度、BFS
2. 双端队列：两端操作，可模拟栈和队列，适合滑动窗口
3. 优先队列：按优先级出队，适合任务调度、Top K 问题
4. 阻塞队列：线程安全，适合生产者-消费者模式
5. 单调队列：维护极值，适合滑动窗口最值问题

选择合适的队列实现，取决于具体场景的需求：是否需要优先级、是否需要线程安全、是否需要双端操作。

练习

基础：

1. LeetCode 232：用栈实现队列
2. LeetCode 225：用队列实现栈
3. LeetCode 622：设计循环队列
4. LeetCode 641：设计循环双端队列

优先队列： 5. LeetCode 215：数组中的第K个最大元素 6. LeetCode 23：合并K个升序链表 7. LeetCode 347：前K个高频元素 8. LeetCode 295：数据流的中位数

单调队列： 9. LeetCode 239：滑动窗口最大值 10. LeetCode 1438：绝对差不超过限制的最长连续子数组

BFS： 11. LeetCode 102：二叉树的层序遍历 12. LeetCode 207：课程表 13. LeetCode 210：课程表 II 14. LeetCode 994：腐烂的橘子

进阶： 15. LeetCode 862：和至少为K的最短子数组 16. LeetCode 239：滑动窗口最大值（用单调队列优化） 17. LeetCode 1642：可以到达的最远建筑