第10章队列

课程目录第10章队列

队列：先进先出的艺术

队列这东西，说白了就是「先来后到」。你想想看，生活中排队买奶茶，第一个排队的先拿到，最后一个排队的只能等着——这就是队列最朴素的逻辑。我在早年做嵌入式系统时，经常用队列来处理串口数据，那时候才真正体会到，一个简单的数据结构，用对了地方能省多少事。

队列的定义与核心操作

队列是一种先进先出（FIFO, First In First Out）的线性表。它只允许在一端插入（称为队尾），在另一端删除（称为队头）。

嗯，这里要注意：队列和栈正好相反。栈是后进先出，队列是先进先出。我见过不少初学者把这两个搞混，其实你只要记住「排队」这个生活场景就行了。

队列的核心操作就这几个：

入队（Enqueue）：在队尾插入一个元素
出队（Dequeue）：删除队头元素
判空（IsEmpty）：检查队列是否为空
取队头（Front）：获取队头元素的值，但不删除
取队尾（Rear）：获取队尾元素的值
获取长度（Size）：返回队列中元素个数

重要概念：队列的插入和删除操作分别发生在两端，时间复杂度均为 O(1)。这是队列高效性的核心保证。

循环队列：解决「假溢出」问题

用数组实现队列时，会遇到一个尴尬的问题。我举个例子：你有一个长度为5的数组，先入队3个元素，再出队3个元素。此时队头指针已经跑到数组末尾了，但数组前面空着的位置却用不了。这就是「假溢出」。

怎么解决？把数组首尾相连，形成一个环。这就是循环队列。

我的经验：循环队列在嵌入式开发中非常实用。我曾经在一个数据采集项目中，用循环队列做环形缓冲区，完美解决了数据流的中断处理问题。内存占用固定，没有动态分配，非常适合资源受限的环境。

循环队列的关键在于取模运算。队头指针 front 和队尾指针 rear 在数组范围内循环移动：

// 入队操作
rear = (rear + 1) % MAX_SIZE;
queue[rear] = value;

// 出队操作
front = (front + 1) % MAX_SIZE;
value = queue[front];

这里有个坑：如何区分队列「空」和「满」？当 front == rear 时，队列可能是空的，也可能是满的。常用的解决方案有两种：

方案一：牺牲一个存储单元。当 (rear + 1) % MAX_SIZE == front 时，认为队列已满。此时队列最多存储 MAX_SIZE - 1 个元素。
方案二：增加一个 size 变量记录元素个数。这样 front == rear 时，通过 size 就能判断是空还是满。

我个人习惯用方案一，因为不需要额外维护一个变量，代码更简洁。

我曾经踩过的坑：有一次写循环队列，忘记处理取模运算的边界情况。当 rear 等于 MAX_SIZE - 1 时，直接加 1 就数组越界了。后来我养成了一个习惯——所有涉及循环队列指针移动的地方，一律用取模运算，绝不偷懒。

下面是循环队列的完整实现：

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;  // 队头指针
    int rear;   // 队尾指针
} CircularQueue;

// 初始化
void initQueue(CircularQueue *q) {
    q->front = 0;
    q->rear = 0;
}

// 判空
int isEmpty(CircularQueue *q) {
    return q->front == q->rear;
}

// 判满
int isFull(CircularQueue *q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

// 入队
int enqueue(CircularQueue *q, int value) {
    if (isFull(q)) {
        return -1;  // 队列已满
    }
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return 0;
}

// 出队
int dequeue(CircularQueue *q, int *value) {
    if (isEmpty(q)) {
        return -1;  // 队列为空
    }
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return 0;
}

队列的链式存储结构

数组实现的队列有个硬伤：大小固定。你想想看，如果事先不知道数据量，数组要么浪费空间，要么不够用。这时候就需要链式队列了。

链式队列本质上是一个带头结点的单链表，队头指针指向头结点，队尾指针指向最后一个结点。入队操作在链表尾部插入，出队操作在链表头部删除。

为什么用带头结点的链表？因为这样出队操作时，不需要特殊处理空队列的情况。头结点永远存在，代码更统一。

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    Node *front;  // 队头指针，指向头结点
    Node *rear;   // 队尾指针，指向最后一个结点
} LinkedQueue;

// 初始化
void initQueue(LinkedQueue *q) {
    q->front = (Node*)malloc(sizeof(Node));
    q->front->next = NULL;
    q->rear = q->front;
}

// 入队
void enqueue(LinkedQueue *q, int value) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;
    q->rear->next = newNode;
    q->rear = newNode;
}

// 出队
int dequeue(LinkedQueue *q, int *value) {
    if (q->front == q->rear) {
        return -1;  // 队列为空
    }
    Node *temp = q->front->next;
    *value = temp->data;
    q->front->next = temp->next;
    if (q->rear == temp) {
        q->rear = q->front;  // 删除最后一个元素时，更新队尾指针
    }
    free(temp);
    return 0;
}

注意：链式队列的入队和出队操作时间复杂度仍然是 O(1)。但每个结点需要额外的指针空间，内存开销比数组大。在内存紧张的场景下，我倾向于用循环队列。

两种实现的对比

对比维度	循环队列（数组）	链式队列
空间大小	固定，事先确定	动态，按需分配
内存开销	小，只有数据本身	大，每个结点多一个指针
入队/出队	O(1)	O(1)
适用场景	数据量已知，内存受限	数据量未知，频繁插入删除
实现复杂度	中等，需处理取模	简单，但需注意内存管理

队列知识体系总览

下面这张图展示了队列的核心知识结构，帮你理清思路：

队列的应用其实很广。比如操作系统的任务调度、打印机的任务队列、网络数据包的缓冲处理，底层都是队列。我记得有一次做网络协议栈，用队列来管理接收到的数据包，配合中断处理，整个系统的吞吐量提升了不少。

队列的两种实现各有优劣。循环队列适合数据量确定的场景，链式队列则更灵活。实际开发中，我建议你根据具体需求来选择——没有最好的数据结构，只有最合适的。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录

队列：先进先出的艺术

队列的定义与核心操作

循环队列：解决「假溢出」问题

队列的链式存储结构

两种实现的对比

队列知识体系总览