队列的核心概念与基本操作

学习目标

本节学习队列的核心概念和基本操作。

学习完成后，你需要能够解释队头、队尾、入队、出队，以及为什么队列的处理顺序符合先进先出。

---

队列的基本结构

队列是一种从一端进入、另一端离开的线性结构。

队头                       队尾
 ↓                         ↓
 A  ->  B  ->  C  ->  D

A 最早进入队列，因此会最先离开。D 最晚进入队列，因此需要等待前面的元素都离开之后才能被处理。

这种规则与现实生活中的排队非常相似。

---

入队和出队

入队通常叫 enqueue，表示把元素加入队尾。

出队通常叫 dequeue，表示移除并返回队头元素。

不同语言库中的方法名称可能不同，但行为一致。

C++

queue<string> names;

names.push("A");
names.push("B");
names.push("C");

string firstName = names.front();
names.pop();

Java

Queue<String> names = new ArrayDeque<>();

names.offer("A");
names.offer("B");
names.offer("C");

String firstName = names.peek();
names.poll();

Python

from collections import deque

names = deque()

names.append("A")
names.append("B")
names.append("C")

first_name = names[0]
names.popleft()

C#

Queue<string> names = new Queue<string>();

names.Enqueue("A");
names.Enqueue("B");
names.Enqueue("C");

string firstName = names.Peek();
names.Dequeue();

这四段代码中，A、B、C 依次进入队列。最先进入的是 A，所以队头元素是 A。执行一次出队后，A 离开，B 成为新的队头。

---

判断队列是否为空

和栈一样，出队前也需要判断队列是否为空。对空队列执行出队操作通常会出错。

C++

if (!names.empty()) {
    string value = names.front();
    names.pop();
}

Java

if (!names.isEmpty()) {
    String value = names.poll();
}

Python

if names:
    value = names.popleft()

C#

if (names.Count > 0)
{
    string value = names.Dequeue();
}

判空可以避免访问不存在的队头元素，是队列使用中的基本边界处理。

---

队列的操作复杂度

如果底层实现合理，队列的常见操作通常也很高效：

操作              常见时间复杂度
入队 enqueue       O(1)
出队 dequeue       O(1)
查看队头           O(1)
判空               O(1)

需要注意的是，不同语言中并不是所有列表结构都适合做队列。例如，Python 的普通列表在头部删除元素可能需要移动后续元素，因此更推荐使用 collections.deque 表示队列。

---

队列的核心不是容器，而是规则

队列的关键是先进先出，而不是某个具体容器名称。

只要一个问题要求“先来的先处理”，就可以考虑队列。任务排队、消息缓冲、打印队列、请求处理、广度优先搜索，都可以使用队列来表达处理顺序。

---

本节小结

队列是一种先进先出的受限线性结构。

它的主要操作包括入队、出队、查看队头和判空。队列适合表达先到先处理的过程。与栈相比，队列强调顺序保持，先进入的数据会先被处理。