队列与双端队列Deque

一、队列(Queue)

1.1 定义

队列是先进先出(FIFO, First In First Out)的线性数据结构。

1.2 核心操作

操作	说明	时间复杂度
enqueue/offer	入队（队尾）	( O(1) )
dequeue/poll	出队（队头）	( O(1) )
peek	查看队头	( O(1) )
isEmpty	判空	( O(1) )

1.3 生活类比

排队买票，先到的人先服务。

二、队列的实现

2.1 数组实现 - 循环队列

class CircularQueue {
    private int[] data;
    private int front = 0;  // 队头
    private int rear = 0;   // 队尾下一个位置
    private int size = 0;
    
    public boolean offer(int val) {
        if (size == data.length) return false;
        data[rear] = val;
        rear = (rear + 1) % data.length;
        size++;
        return true;
    }
    
    public int poll() {
        if (size == 0) throw new RuntimeException("Queue is empty");
        int val = data[front];
        front = (front + 1) % data.length;
        size--;
        return val;
    }
}

2.2 链表实现

class LinkedQueue {
    private ListNode head, tail;
    
    public void offer(int val) {
        ListNode node = new ListNode(val);
        if (tail == null) {
            head = tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
    }
    
    public int poll() {
        if (head == null) throw new RuntimeException("Queue is empty");
        int val = head.val;
        head = head.next;
        if (head == null) tail = null;
        return val;
    }
}

2.3 Java标准库

Queue<Integer> queue = new LinkedList<>();  // 链表实现
Queue<Integer> queue = new ArrayDeque<>();   // 数组实现，推荐

三、双端队列(Deque)

3.1 定义

Deque(Double Ended Queue)允许在两端进行插入和删除操作。

3.2 操作

操作	队头	队尾
插入	offerFirst	offerLast
删除	pollFirst	pollLast
查看	peekFirst	peekLast

3.3 Java实现

Deque<Integer> deque = new ArrayDeque<>();

deque.offerFirst(1);  // [1]
deque.offerLast(2);   // [1, 2]
deque.pollFirst();    // [2]
deque.pollLast();     // []

四、队列的经典应用

4.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 size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; 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;
}

4.2 滑动窗口最大值

使用单调队列（双端队列实现）：

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] res = 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) {
            res[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return res;
}

4.3 任务调度

// 使用阻塞队列实现生产者-消费者
BlockingQueue<Task> queue = new LinkedBlockingQueue<>();

// 生产者
queue.put(task);

// 消费者
Task task = queue.take();

五、特殊队列

5.1 优先队列(Priority Queue)

元素按优先级出队，底层是堆实现。

PriorityQueue<Integer> pq = new PriorityQueue<>();  // 小顶堆
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());  // 大顶堆

5.2 延迟队列(DelayQueue)

元素只有到期后才能出队。

5.3 阻塞队列

ArrayBlockingQueue  // 有界数组
LinkedBlockingQueue // 无界链表
SynchronousQueue    // 不存储元素

六、总结

数据结构	特点	核心应用
普通队列	FIFO	BFS、缓冲区
双端队列	两端操作	滑动窗口、回文判断
优先队列	按优先级	TopK、合并有序列表
阻塞队列	线程安全	生产者-消费者

队列的FIFO特性使其非常适合处理按顺序处理和公平调度的场景。理解不同队列变体的特性，能在实际开发中做出恰当选择。