认识队列：概念与基础结构

大家好！今天我们来学习一种非常有用的数据结构——队列（Queue）。

想象一下我们在排队买票或者等公交车，是不是遵守“先来的人先服务”的规则？队列就是这样一种遵循 "先进先出"（FIFO, First In First Out） 原则的线性数据结构。

队列就像一个管道

1
2
3
4
← 队头 (Front) - 出队 队尾 (Rear/Back) - 入队 →

队列的主要特点：

  • 数据只能从一端（通常称为 队尾 Rear/Back）进入队列，这个操作叫做 入队（Enqueue / Push）。
  • 数据只能从另一端（通常称为 队头 Front）离开队列，这个操作叫做 出队（Dequeue / Pop）。
  • 最早进入队列的元素，会最先被移出队列。

队列的基本操作 (queue)

在 C++ 中，我们可以方便地使用标准库提供的 <queue> 头文件中的 queue 容器适配器来实现队列。它封装了底层容器（默认是 deque），并提供了队列的标准操作。

动手试一试！

← 队头 队尾 →
请点击下方按钮操作队列

常用操作详解：

  • push(element)：将一个新元素添加到队尾。
  • pop()：移除队头的元素（注意：不返回元素值）。
  • front()：返回队头元素的引用（不移除）。对空队列调用是未定义行为！
  • back()：返回队尾元素的引用（不移除）。对空队列调用是未定义行为！
  • empty()：检查队列是否为空，是则返回 true，否则返回 false。
  • size()：返回队列中当前元素的数量。

特殊队列：循环队列与双端队列

循环队列 (Circular Queue)

使用普通数组实现队列时，随着入队和出队操作，可能会出现数组前面有很多空位，但队尾指针已经到达数组末端，导致无法再入队，这就是“假溢出”。

循环队列 通过将数组看作一个环形空间来解决这个问题。当指针到达数组末尾时，它可以“绕回”到数组的开头。

循环队列示意图 (大小为 5)

实现循环队列的关键在于使用取模运算(%)来更新头尾指针，并需要判断队列是空还是满。

双端队列 (Deque - Double-Ended Queue)

deque (发音类似 "deck") 是一种更强大的序列容器，它允许在 两端 进行高效的插入和删除操作。

虽然 queue 默认使用 deque 作为底层容器，但 deque 本身提供了更丰富的功能。

双端队列操作

←
push_front / pop_front
push_back / pop_back
→

队列的典型应用

1. 操作系统与缓冲

队列的 FIFO 特性使其非常适合处理需要按顺序处理的任务或数据。

  • 任务调度： 操作系统中的进程调度，先请求服务的进程先被执行。
  • 打印队列： 将打印任务放入队列，打印机按顺序打印。
  • 网络数据包缓冲： 路由器或服务器接收到的数据包按到达顺序放入队列处理，防止数据丢失。
  • 消息队列： 在分布式系统中解耦服务，生产者将消息放入队列，消费者按顺序取出处理。

2. 滑动窗口问题 (例如：求窗口最大值)

问题：给定一个数组和一个固定大小的窗口 k，窗口从左到右滑动，每次滑动一步，求出每个窗口内的最大值。

思路： 使用一个双端队列 (deque) 来维护一个单调递减的索引序列。队头始终是当前窗口最大值的索引。

滑动窗口 (大小 k=3) 演示

当前窗口: [], 最大值: -

3. 图的广度优先搜索 (BFS - Breadth-First Search)

BFS 是一种用于遍历或搜索树或图的算法。它从根节点（或任意选定的起始节点）开始，探索邻近节点，然后再扩展到下一层级的节点。队列是实现 BFS 的核心工具。

BFS 过程示意

队列: [ ]
状态: 点击 '开始/下一步'

BFS 过程：

  1. 选择一个起始节点，标记为已访问，并将其加入队列。
  2. 当队列不为空时：
    • 取出队头节点（出队）。
    • 访问该节点的所有未被访问过的邻居节点。
    • 将这些邻居节点标记为已访问，并加入队列（入队）。

应用场景： 寻找无权图的最短路径、层序遍历、查找连通分量等。

课堂练习与总结

练一练，加深理解！

练习 1：队列反转

编写一个 C++ 函数，接收一个 queue<int> 作为参数，将其元素顺序反转。你可以使用栈 (stack) 作为辅助数据结构，但不能使用另一个队列。

练习 2：用队列模拟栈

请尝试使用 两个 queue 来实现一个栈。你需要实现栈的基本操作：push(x), pop() (移除栈顶元素), top() (返回栈顶元素), 和 empty()。

本节课小结

今天我们学习了队列（Queue）这种重要的数据结构，掌握了它的核心特性和操作：

  • 核心原则： 先进先出 (FIFO)。
  • 基本操作： push, pop, front, back, empty, size (以 queue 为例)。
  • 特殊类型： 了解了循环队列如何解决“假溢出”，以及双端队列 (deque) 的两端操作能力。
  • 典型应用： 认识到队列在任务调度、数据缓冲、滑动窗口问题和广度优先搜索 (BFS) 中的广泛应用。

使用队列的注意事项：

  • 空队列检查： 在调用 front(), back(), 或 pop() 之前，务必使用 empty() 检查队列是否为空，避免程序出错。
  • pop() 不返回值： queue::pop() 只负责移除队头元素，如果需要获取该元素的值，应先调用 front()。
  • 选择合适的容器： C++ STL 提供了 queue (FIFO), priority_queue (优先出队), deque (双端操作)。根据具体需求选择最合适的。
  • 效率考量： queue（默认基于deque）和deque 的两端操作通常是 O(1) 均摊时间复杂度，但在某些实现或极端情况下可能涉及内存重新分配。

希望大家课后多多练习，熟练掌握队列的使用！

🌙