《数据结构：从0到1》-09-队列

队列(Queue)：先进先出

还记得我们上一篇文章聊的“栈”吗？那种后进先出(LIFO)的规则，就像我们叠盘子一样。今天，我们要来聊聊它的好兄弟——队列(Queue)。如果说栈是“后来者居上”，那队列就是彻头彻尾的“先来后到”，它讲究公平，讲求秩序。

计算机里面好多理论都是源于生活，队列就是其中一个经典例子。下面以奶茶店排队的场景为例，详细介绍一下：

你先来的，所以你排在最前面。后面来的人，依次排在队伍末尾。店员做完一杯奶茶，总是递给队伍最前面的人。最前面的人拿到奶茶后离开，后面的人依次向前移动一位。

这个“排队的队伍”，就是队列在现实世界中最完美的体现！ 它的核心规则就是 FIFO，也就是 先进先出。

在计算机世界里，队列几乎无处不在：打印任务排队、CPU进程调度、网络数据包缓存、甚至是我们在键盘上敲下的每一个字符等等，涉及到的底层逻辑都离不开队列。

今天，就让我们一起从零开始盘一盘队列！

本篇学习路线图：

---

一、 队列是什么？

在开始敲代码之前，我们必须从骨子里理解队列的定义和操作。

1.1 队列的定义与核心特性

队列(Queue) 是一种特殊的线性表，它只允许在表的前端进行删除操作，在表的后端进行插入操作。

我们把进行插入操作的一端称为 队尾(Rear)，把进行删除操作的一端称为 队头(Front)。

队列的两个核心操作：

入队(Enqueue)：将一个新元素放入队尾。出队(Dequeue)：从队头移除一个元素。

通常还会伴随两个常用的操作：

获取队头元素(Peek/Front)：看一眼队头是谁，但不让它出队。判断队列是否为空(IsEmpty)：看看队伍里是不是没人了。

队列的FIFO特性，就像一根单行道的水管：

水从一端（队尾）流入从另一端（队头）流出先流进去的水，一定会先流出来

1.2 队列的ADT

在动手实现之前，我们先定义好队列这个“东西”应该有哪些“行为”，这就是抽象数据类型。

public interface Queue<T> {
    /**
     * 入队操作：将元素添加到队尾
     * @param item 要入队的元素
     */
    void enqueue(T item);
    
    /**
     * 出队操作：移除并返回队头元素
     * @return 队头元素
     * @throws Exception 如果队列为空
     */
    T dequeue() throws Exception;
    
    /**
     * 获取队头元素，但不移除
     * @return 队头元素
     * @throws Exception 如果队列为空
     */
    T peek() throws Exception;
    
    /**
     * 判断队列是否为空
     * @return 空返回true，否则返回false
     */
    boolean isEmpty();
    
    /**
     * 获取队列中元素的个数
     * @return 元素个数
     */
    int size();
}

有了这些知识，我们就可以用不同的方式来实现它了。最经典的两种方式就是：数组 和 链表。这篇文章，我们主要聚焦于数组实现，因为它能更好地引出我们下一个重要概念——循环队列。

---

二、 队列的数组实现

用数组实现队列是最直观的想法。我们用一个固定大小的数组来存储元素，再用两个指针（或者叫索引）
front 和
rear 来分别标记队列头和尾。

2.1 初始状态与指针


front：总是指向队列中的第一个元素的位置。
rear：总是指向队列中最后一个元素的下一个位置（即新元素要插入的位置）。

初始时，队列为空：

front = 0
rear  = 0
数组: [ null, null, null, null, null ]
       ^
      front & rear

2.2 入队与出队过程

假设我们的队列容量为5。

步骤1：初始状态

Index:   0     1     2     3     4
Array: [ null, null, null, null, null ]
        ^
       front = 0, rear = 0

步骤2：执行
enqueue("A")

将
"A" 放入
rear 的位置（索引0）
rear 指针后移一位

Index:   0     1     2     3     4
Array: [ "A",  null, null, null, null ]
        ^      ^
       front  rear

步骤3：执行
enqueue("B")

将
"B" 放入
rear 的位置（索引1）
rear 指针后移一位

Index:   0     1     2     3     4
Array: [ "A",  "B",  null, null, null ]
        ^             ^
       front         rear

步骤4：执行
dequeue()

取出
front 位置的元素
"A"
front 指针后移一位

Index:   0     1     2     3     4
Array: [ null, "B",  null, null, null ]
               ^      ^
              front  rear

看到问题了吗？索引0的位置现在空出来了，但我们再也用不到了！随着不断地入队和出队，
front 和
rear 指针会不断地向右移动，即使数组前面有空位，我们也无法利用。这就是 “假溢出”。

2.3 “假溢出”问题与代码实现

“假溢出”：当
rear 指针移动到数组末尾时，即使数组前面还有空闲位置，我们也无法再插入新元素，因为
rear 已经“无处可去”了。

下面我们用代码实现这个基础的数组队列，让大家切身感受一下这个问题：

/**
 * 使用数组实现的基础队列（存在假溢出问题）
 */
public class ArrayQueue<T> {
    private T[] data;       // 存储队列元素的数组
    private int front;      // 队头指针
    private int rear;       // 队尾指针
    private int capacity;   // 队列容量
    private int count;      // 当前元素个数

    // 构造函数，初始化队列
    @SuppressWarnings("unchecked")
    public ArrayQueue(int capacity) {
        this.capacity = capacity;
        this.data = (T[]) new Object[capacity]; 
        this.front = 0;
        this.rear = 0;
        this.count = 0;
    }

    /**
     * 入队操作
     * @param item 要入队的元素
     * @throws RuntimeException 如果队列已满
     */
    public void enqueue(T item) {
        // 检查队列是否已满
        if (count == capacity) {
            throw new RuntimeException("Queue is full! Cannot enqueue.");
        }
        
        // 将元素放入队尾
        data[rear] = item;
        // 队尾指针后移
        rear++;
        // 元素计数加一
        count++;
        
        System.out.println("Enqueued: " + item + " | Front: " + front + ", Rear: " + rear);
    }

    /**
     * 出队操作
     * @return 队头元素
     * @throws RuntimeException 如果队列为空
     */
    public T dequeue() {
        // 检查队列是否为空
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty! Cannot dequeue.");
        }
        
        // 获取队头元素
        T item = data[front];
        // 将原位置置空
        data[front] = null;
        // 队头指针后移
        front++;
        // 元素计数减一
        count--;
        
        System.out.println("Dequeued: " + item + " | Front: " + front + ", Rear: " + rear);
        return item;
    }

    /**
     * 查看队头元素但不出队
     */
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("Queue is empty! Cannot peek.");
        }
        return data[front];
    }

    /**
     * 判断队列是否为空
     */
    public boolean isEmpty() {
        return count == 0;
    }

    /**
     * 获取队列元素个数
     */
    public int size() {
        return count;
    }

    /**
     * 打印队列当前状态
     */
    public void printQueue() {
        System.out.print("Queue: [ ");
        for (int i = front; i < rear; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println("]");
    }
}

测试一下我们的基础队列：

public class Main {
    public static void main(String[] args) {
        // 创建一个容量为3的队列
        ArrayQueue<String> queue = new ArrayQueue<>(3);
        
        // 入队三个元素
        queue.enqueue("A");
        queue.enqueue("B");
        queue.enqueue("C");
        queue.printQueue(); // 输出: Queue: [ A B C ]
        
        // 出队一个元素
        queue.dequeue();    // A 出队
        queue.printQueue(); // 输出: Queue: [ B C ]
        
        // 尝试入队第四个元素 - 这里会抛出异常！
        // 但实际上我们的数组索引0是空的，这就是假溢出
        try {
            queue.enqueue("D");
        } catch (RuntimeException e) {
            System.out.println("错误: " + e.getMessage());
        }
    }
}

运行结果会清楚地显示，即使数组还有空位，我们也无法插入新元素。这种设计显然是对内存的极大浪费。那么，如何解决这个问题呢？答案就是——循环队列。

---

三、 循环队列：解决“假溢出”的银弹

循环队列的核心理念是把数组想象成一个环，而不是一条直线。当指针移动到数组末尾时，它可以“绕回”到数组的开头。

3.1 循环队列的核心思想

把线性数组“掰弯”成一个环：

线性索引: 0 -> 1 -> 2 -> 3 -> 4 -> 回到0

指针移动的公式：

// 普通后移
index = (index + 1) % capacity;

// 例如，容量为5：
// 从4移动到0: (4 + 1) % 5 = 5 % 5 = 0
// 从0移动到1: (0 + 1) % 5 = 1 % 5 = 1

通过取模运算
%，我们可以让指针在数组范围内循环移动。

3.2 队空与队满的判断

在基础队列中，我们通过
count 变量来判断空和满。在循环队列中，我们也可以这样做，但还有一种更好的方式：通过
front 和
rear 的相对位置来判断。

两种判断方式：

方式一：使用计数器
count


isEmpty():
count == 0
isFull():
count == capacity

方式二：通过front和rear相对位置判断


isEmpty():
front == rear
isFull():
(rear + 1) % capacity == front

第二种方式中，我们有意浪费一个数组空间来区分队空和队满的状态。这是循环队列中一个非常经典的技巧！

3.3 循环队列的完整实现

下面让我们实现一个完整的循环队列：

/**
 * 循环队列实现 - 解决假溢出问题
 */
public class CircularQueue<T> {
    private T[] data;       // 存储队列元素的数组
    private int front;      // 头指针
    private int rear;       // 尾指针
    private int capacity;   // 容量

    // 构造函数
    @SuppressWarnings("unchecked")
    public CircularQueue(int capacity) {
        this.capacity = capacity + 1; // 多分配一个空间，用于区分空和满
        this.data = (T[]) new Object[this.capacity];
        this.front = 0;
        this.rear = 0;
    }

    /**
     * 入队操作
     */
    public void enqueue(T item) {
        if (isFull()) {
            throw new RuntimeException("CircularQueue is full! Cannot enqueue.");
        }
        
        // 元素放入队尾
        data[rear] = item;
        // 队尾指针循环后移
        rear = (rear + 1) % capacity;
        
        System.out.println("Enqueued: " + item + " | Front: " + front + ", Rear: " + rear);
    }

    /**
     * 出队操作
     */
    public T dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("CircularQueue is empty! Cannot dequeue.");
        }
        
        // 获取队头元素
        T item = data[front];
        // 将原位置置空
        data[front] = null;
        // 队头指针循环后移
        front = (front + 1) % capacity;
        
        System.out.println("Dequeued: " + item + " | Front: " + front + ", Rear: " + rear);
        return item;
    }

    /**
     * 查看队头元素
     */
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("CircularQueue is empty! Cannot peek.");
        }
        return data[front];
    }

    /**
     * 判断队列是否为空
     * 队空条件：front == rear
     */
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * 判断队列是否已满
     * 队满条件：(rear + 1) % capacity == front
     */
    public boolean isFull() {
        return (rear + 1) % capacity == front;
    }

    /**
     * 获取队列元素个数
     * 需要处理循环的情况
     */
    public int size() {
        return (rear - front + capacity) % capacity;
    }

    /**
     * 队列状态
     */
    public void printQueue() {
        System.out.print("CircularQueue: [ ");
        if (!isEmpty()) {
            int i = front;
            while (i != rear) {
                System.out.print(data[i] + " ");
                i = (i + 1) % capacity;
            }
        }
        System.out.println("]");
        
        // 底层数组状态
        System.out.print("Underlying Array: [ ");
        for (int i = 0; i < capacity; i++) {
            if (data[i] == null) {
                System.out.print("null ");
            } else {
                System.out.print(data[i] + " ");
            }
        }
        System.out.println("]");
    }
}

3.4 循环队列工作流程

通过一个具体的例子，看看循环队列是如何工作的：

public class CircularQueueDemo {
    public static void main(String[] args) {
        // 创建容量为3的循环队列（实际数组大小为4）
        CircularQueue<String> queue = new CircularQueue<>(3);
        
        System.out.println("=== 初始状态 ===");
        queue.printQueue();
        System.out.println("是否为空: " + queue.isEmpty());
        System.out.println();
        
        System.out.println("=== 入队A, B, C ===");
        queue.enqueue("A");
        queue.enqueue("B");
        queue.enqueue("C");
        queue.printQueue();
        System.out.println("是否已满: " + queue.isFull());
        System.out.println();
        
        System.out.println("=== 出队A ===");
        queue.dequeue();
        queue.printQueue();
        System.out.println();
        
        System.out.println("=== 入队D（利用了A空出的位置） ===");
        queue.enqueue("D");  
        queue.printQueue();
        System.out.println();
        
        System.out.println("=== 再入队E ===");
        try {
            queue.enqueue("E"); 
        } catch (RuntimeException e) {
            System.out.println("错误: " + e.getMessage());
        }
    }
}

运行Demo，可以看到循环队列“绕回”数组开头，完美解决了假溢出问题！

---

四、 优先队列

有时候，严格的“先来后到”并不是最优解。比方说医院急诊科的场景：一个感冒病人先来挂号，但随后来了一个心脏病发作的病人。医生肯定会优先处理病情更危急的病人。

这就是优先队列(Priority Queue) 的思想——元素出队的顺序由优先级决定，而不是入队的顺序。

4.1 什么是优先队列？

优先队列中的每个元素都有一个相关的优先级。在进行出队操作时，优先级最高的元素最先出队。

优先队列的特点：

入队(Enqueue)：元素按任意顺序进入队列出队(Dequeue)：总是移除当前队列中优先级最高的元素如果多个元素具有相同的优先级，通常按它们入队的顺序出队

4.2 优先队列的实现方式

优先队列有多种实现方式，每种方式在时间效率上有所不同：

数据结构	入队时间复杂度	出队时间复杂度	说明
无序数组	O(1)	O(n)	出队时需要扫描整个数组找最大值
有序数组	O(n)	O(1)	入队时需要找到正确位置并移动元素
堆(Heap)	O(log n)	O(log n)	最常用的实现方式

由于堆的优异性能，Java中的
PriorityQueue 类和C++中的
priority_queue 都是基于堆实现的。

4.3 基于堆的优先队列简单实现

下面我们用Java内置的
PriorityQueue 来演示优先队列的用法：

import java.util.PriorityQueue;

/**
 * 优先队列使用
 */
public class PriorityQueueExample {
    
    // 定义一个任务类，包含任务名和优先级
    static class Task implements Comparable<Task> {
        String name;
        int priority; // 数字越小，优先级越高
        
        public Task(String name, int priority) {
            this.name = name;
            this.priority = priority;
        }
        
        // 实现Comparable接口，定义比较规则
        @Override
        public int compareTo(Task other) {
            // 优先级数字小的排在前面
            return Integer.compare(this.priority, other.priority);
        }
        
        @Override
        public String toString() {
            return name + "(优先级:" + priority + ")";
        }
    }
    
    public static void main(String[] args) {
        // 创建优先队列
        PriorityQueue<Task> taskQueue = new PriorityQueue<>();
        
        // 添加任务
        taskQueue.offer(new Task("写邮件", 3));
        taskQueue.offer(new Task("修复紧急BUG", 1)); // 最高优先级
        taskQueue.offer(new Task("参加会议", 2));
        taskQueue.offer(new Task("整理文档", 4));
        
        System.out.println("=== 按优先级顺序处理任务 ===");
        
        // 依次出队，会按优先级从高到低执行
        while (!taskQueue.isEmpty()) {
            Task task = taskQueue.poll();
            System.out.println("正在处理: " + task);
        }
    }
}

运行结果：

=== 按优先级顺序处理任务 ===
正在处理: 修复紧急BUG(优先级:1)
正在处理: 参加会议(优先级:2)
正在处理: 写邮件(优先级:3)
正在处理: 整理文档(优先级:4)

看到了吗？即使”修复紧急BUG”不是第一个入队的，但由于它的优先级最高，所以最先出队被执行。这就是优先队列！！！

---

五、 队列的应用场景

下面我们来看几个经典队列的例子：

5.1 操作系统中的进程调度

操作系统使用就绪队列来管理所有准备运行的进程。CPU按照某种调度算法（如先来先服务等）从队列中取出进程执行。

5.2 消息队列（如RabbitMQ, Kafka）

在分布式系统中，消息队列用于解耦服务之间的直接依赖。生产者将消息放入队列，消费者从队列中取出消息处理。

应用场景：

异步处理：比如用户注册后，不需要等待发送邮件的操作完成流量削峰：比如应对突发流量，避免系统被冲垮应用解耦：比如服务之间通过消息通信，而不是直接调用

5.3 广度优先搜索(BFS)

在图和树的遍历算法中，广度优先搜索使用队列来按层遍历节点：

/**
 * 二叉树的层次遍历（BFS）
 */
public void levelOrderTraversal(TreeNode root) {
    if (root == null) return;
    
    Queue<TreeNode> queue = new LinkedList<>();
    // 根节点入队
    queue.offer(root); 
    
    while (!queue.isEmpty()) {
        // 出队当前节点
        TreeNode node = queue.poll(); 
        System.out.print(node.val + " ");
        
        // 将左右子节点入队
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

5.4 其他案例

打印机任务队列，多个打印任务按提交顺序排队打印；网络数据包缓存，路由器处理网络数据包；客服呼叫中心，来电按顺序分配给客服人员；

---

六、 总结

至此队列数据结构已经全讲完了。总结一下：

6.1 核心知识点

队列的基本概念

FIFO（先进先出）：最核心的特性，像排队一样公平队头(Front)：进行删除操作的一端队尾(Rear)：进行插入操作的一端基本操作：入队(Enqueue)、出队(Dequeue)、查看队头(Peek)

队列的实现方式

数组实现：相对简单，存在”假溢出”问题循环队列：通过取模运算实现数组循环使用，解决假溢出队空队满判断：
front == rear 为空，
(rear + 1) % capacity == front 为满

优先队列

出队顺序由优先级决定，而不是入队顺序常用堆(Heap)实现，保证入队出队都是O(log n)时间复杂度应用场景：任务调度、急诊分诊等需要优先处理的场景

队列的实际应用

操作系统进程调度消息中间件广度优先搜索(BFS)各种需要缓冲和排队的场景

6.2 队列 vs 栈：如何选择？

特性	栈(Stack)	队列(Queue)
原则	LIFO（后进先出）	FIFO（先进先出）
类比	摞盘子	排队
插入端	栈顶(Top)	队尾(Rear)
删除端	栈顶(Top)	队头(Front)
应用	函数调用、表达式求值、回溯	进程调度、BFS、消息队列

简单来说：

需要”撤销”功能？→ 用栈需要保持顺序公平处理？→ 用队列需要按优先级处理？→ 用优先队列

---

写在最后

队列，这个看似简单的数据结构，却蕴含着深刻的计算机科学思想。从最基本的FIFO队列，到解决内存浪费的循环队列，再到打破常规的优先队列，每一种变体都是为了解决特定的实际问题而生。

理解队列的关键不在于死记硬背代码，而在于理解其”先进先出”的核心思想，以及这种思想如何应用于各种实际场景。当你遇到需要按顺序处理、需要缓冲、需要公平调度的场景时，不妨想想：“这里是不是可以用队列？”

如果觉得这篇文章对你有帮助，请不要吝啬你的‘一键三连’（点赞、关注、收藏），我们下篇见！

---

版权声明：本文为CSDN博主「[QuantumLeap丶]」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。