数据结构之队列

什么是队列

队列（Queue）是一种受限的线性表。它的核心规则是 FIFO (First In First Out)，即先进先出。

  • 它就像一个单向隧道或排队买票。最早进去的人，必须最早出来；后来的人只能乖乖站在队尾。
  • 它只允许在表的队尾进行插入操作，而在队头进行删除操作。


主要的队列

根据物理结构和逻辑规则的不同，队列主要分为以下几类：

  • 普通队列：简单的数组实现，指针单向移动（存在“假溢出”缺陷）
  • 循环队列：首尾相连的环形数组（空间复用，能解决假溢出问题）
  • 链式队列：基于链表实现的队列，动态扩容而无需担心固定容量限制
  • 双端队列 (Deque)：两端均可入队和出队，灵活性极高，可同时作为栈和队列使用
  • 优先队列 (Priority)：按优先级出队（通常基于堆实现），处理“急件”，不按先来后到，按重要性


典型的应用场景

队列是计算机系统中处理 “异步” 和 “缓冲” 的灵魂工具：

  • CPU 任务调度：操作系统会将等待执行的进程放入就绪队列，按时间片公平分配资源。
  • MQ 消息队列 ：在分布式系统中，如 RabbitMQ 或 Kafka，用于解耦不同服务，对服务流量削峰填谷。
  • 广度优先搜索 (BFS)：在算法逻辑中，队列用来保存 “下一层” 待访问的节点。


主要队列的代码实现

普通队列

上面我们已经提到，普通队列存在一个致命缺陷：假溢出 (False Overflow)。想象一下这个场景：

  • 你有一个容量为 5 的队列，入队了 5 个元素。此时 rear = 5。
  • 你出队了 5 个元素。此时 front = 5，队列空了。
  • 尴尬发生了，当你想再入队一个新元素时，程序判断 rear == capacity（即 5 == 5），提示队列已满。

明明数组里全是空的，数据就是存不进去。由于普通顺序队列存在严重的‘内存浪费（假溢出），我们在实战中几乎从不直接使用它，而是转向它的进阶版——循环队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class MyQueue01 {

    private int[] data;
    private int capacity;

    private int front; // 头
    private int rear;  // 尾

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

    /**
     * 入队：新成员从队尾进入
     */
    public void enqueue(int val) {
        if (rear == capacity) {
            System.out.println("队列已满");
            return;
        }
        data[rear++] = val;
    }

    /**
     * 出队：老成员从队头离开
     */
    public int dequeue() {
        if (front == rear) throw new RuntimeException("队列为空");
        return data[front++];
    }
}


循环队列

这种队列使用循环数组，解决了普通队列 “假溢出” 的问题。

循环队列交互演示
逻辑：(rear + 1) % 6 == front
0
1
2
3
4
5
▲
F
▲
R
等待操作...

循环队列是 “有限空间无限流转” 的典型的例子。那个看似奇怪的取模运算，实际上是为程序安装了一个回力标，它告诉你：在线性存储的终点，只要你愿意回头，永远有新的空间在等待。而那故意留白的一个格子，则是数据结构中的 “留白艺术”。为了消除歧义，我们宁愿放弃一点空间，也要保证逻辑的绝对清晰。这便是底层设计的取舍之道。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * @author KJ
 * @description 环形队列
 */
public class MyCircularQueue {
    private int[] data;
    private int front;
    private int rear;
    private int size;

    public MyCircularQueue(int capacity) {
        // 关键：为了留空位，数组长度需为 capacity+1
        this.size = capacity + 1;
        this.data = new int[size];
        this.front = 0;
        this.rear = 0;
    }

    public boolean isFull() {
        return (rear + 1) % size == front;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    public int getFront() {
        if (isEmpty()) throw new RuntimeException("队列已空！");
        return data[front];
    }

    /**
     * 入队
     */
    public boolean enqueue(int value) {
        if (isFull()) return false;
        data[rear] = value;
        rear = (rear + 1) % size; // 环形跳跃
        return true;
    }

    /**
     * 出队
     */
    public boolean dequeue() {
        if (isEmpty()) return false;
        front = (front + 1) % size;
        return true;
    }
}


双端队列

双端队列既允许你从前端入队和出队；也允许你从后端入队和出队，既可以当队列使用，也可以当栈使用。Java 官方推荐使用 ArrayDeque 来替代 Stack 类，因为 ArrayDeque 正是基于循环数组实现的双端队列，性能更优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * @author KJ
 * @description 基于循环数组的双端队列
 */
public class MyArrayDeque {
    private int[] data;
    private int front;
    private int rear;
    private int size;

    public MyArrayDeque(int capacity) {
        this.size = capacity + 1;
        this.data = new int[size];
        this.front = 0;
        this.rear = 0;
    }

    public boolean isFull() {
        return (rear + 1) % size == front;
    }

    public boolean isEmpty() {
        return front == rear;
    }

    // --- 队尾操作 (像普通队列) ---

    public boolean addLast(int value) {
        if (isFull()) return false;
        data[rear] = value;
        rear = (rear + 1) % size;
        return true;
    }

    public int removeLast() {
        if (isEmpty()) throw new RuntimeException("Deque is empty");
        // rear 指向的是下一个空位，所以要先退回一步
        rear = (rear - 1 + size) % size;
        return data[rear];
    }

    // --- 队头操作 (像栈) ---

    public boolean addFirst(int value) {
        if (isFull()) return false;
        // front 指向当前第一个元素，需先向前开辟空间
        front = (front - 1 + size) % size;
        data[front] = value;
        return true;
    }

    public int removeFirst() {
        if (isEmpty()) throw new RuntimeException("Deque is empty");
        int val = data[front];
        front = (front + 1) % size;
        return val;
    }
}

注：Java 官方的 ArrayDeque 并没有使用取模 % 实现基于数组的双端队列，而是使用了位运算代替取模，Java 要求数组长度必须是 2^n。这样 (i + 1) % size 就可以写成 (i + 1) & (size - 1)。在底层，按位与运算比取模运算快得多。另外官方实现通过逻辑判断（head == tail 时触发扩容）来区分空和满，从而利用了每一个格子。


优先队列

在优先队列中，元素的出队顺序不再取决于它进入队列的时间，而是取决于它的优先级。为了保证高效，它在底层通常不是用数组或链表线性存储的，而是使用二叉堆 (Heap)，入队和出队都能达到平衡的 O(log n)。关键操作：

  • 上浮 (Swim)：新元素插在末尾，不断与父节点比较，如果优先级更高就 “上位”。
  • 下沉 (Sink)：堆顶出队后，把最后一个元素顶替到堆顶，然后不断与子节点比较，直到回到合适的位置。

为了高效起见，我用数组来存放这棵树（二叉堆），那么数组如何变成一棵树呢？在代码中，heap 数组是从下标 1 开始使用的。这样做有一个非常好的数学规律：

  • 找左孩子：2 * k
  • 找右孩子：2 * k + 1
  • 找父节点：k / 2

当你调用 enqueue(int x) 时：

  • 入队：新来的元素先乖乖待在数组的最后一位（heap[++size] = x）。
  • 上浮：这个新元素（比如是 2）会抬头看自己的父节点（比如是 10）。
  • 较量：如果比父节点小，自己就和父节点交换位置。交换后，自己到了新位置，继续向上看，直到发现父节点比自己小，或者自己已经爬到了堆顶（索引 1）。

当你调用 dequeue() 时：

  • 暂代：为了不让树散架，把数组最后一位的那个元素（通常是大数值）暴力地挪到堆顶（heap[1] = heap[size–]）。
  • 下沉：这个 “德不配位” 的大数值坐在堆顶会很尴尬，它必须向下走。
  • 较量：它会看自己的两个孩子，挑一个最小的孩子。如果自己比这个最小的孩子还大，就跟它交换，自己降一级。重复这个过程，直到它比底下的孩子都小，或者已经到了最底层。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
 * @author KJ
 * @description 简易优先队列 (最小堆实现)
 */
public class MyPriorityQueue {
    private int[] heap;
    private int size;

    public MyPriorityQueue(int capacity) {
        this.heap = new int[capacity + 1]; // 索引0不用，方便计算
        this.size = 0;
    }

    /**
     * 入队：先放末尾，再上浮
     */
    public void enqueue(int x) {
        heap[++size] = x;
        swim(size);
    }

    /**
     * 出队：取出堆顶，末尾顶替，再下沉
     */
    public int dequeue() {
        int min = heap[1];
        heap[1] = heap[size--]; // 把最后一个换到堆顶
        sink(1);
        return min;
    }

    private void swim(int k) {
        // 当子节点比父节点小时，交换
        while (k > 1 && heap[k] < heap[k/2]) {
            swap(k, k/2);
            k = k / 2;
        }
    }

    private void sink(int k) {
        while (2 * k <= size) {
            int j = 2 * k;
            // 找到两个子节点中较小的一个
            if (j < size && heap[j] > heap[j+1]) j++;
            if (heap[k] <= heap[j]) break;
            swap(k, j);
            k = j;
        }
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}


优先队列：上浮与下沉过程演示

最小堆规则：父节点索引 k，孩子为 2k 和 2k+1

10
30
50
40
-
0
#
1
10
2
30
3
50
4
40
5
-
准备就绪：输入数值入队，或直接出队
标题：
数据结构之队列
作者：
kinglyjn
声明：
引用 本文 请务必注明出处，原创不易，感谢尊重。