数据结构 - 队列
队列（Queue）是一种遵循先进先出（First In First Out，FIFO）原则的线性数据结构，可以类比为现实生活中排队买票的场景——最先排队的人最先获得服务。
队列的概念与原理
队列 (Queue) — FIFO 原理示意
队首
front
→
front
20
30
队尾
rear
rear
← dequeue (出队)enqueue (入队) →
enqueue：在 rear (队尾) 插入 | dequeue：从 front (队首) 删除 | 复杂度 O(1)
FIFO 验证：入队 10→20→30，出队 10→20→30（先进先出）
队列只允许在一端（队尾）进行插入操作，在另一端（队首）进行删除操作。
这与栈的 LIFO 原则恰好相反。
数组实现队列
实例
#include <stdio.h>
#include <stdbool.h>
#define MAX 100
struct Queue {
int items[MAX];
int front; /* 队首指针：指向第一个元素 */
int rear; /* 队尾指针：指向下一个待插入位置 */
};
void initQueue(struct Queue* q) {
q->front = 0;
q->rear = 0;
}
bool isEmpty(struct Queue* q) {
return q->front == q->rear;
}
bool isFull(struct Queue* q) {
return q->rear == MAX;
}
/* 入队：在队尾添加元素 */
void enqueue(struct Queue* q, int value) {
if (isFull(q)) {
printf("队列已满！\n");
return;
}
q->items[q->rear++] = value; /* 在 rear 处写入，然后 rear 后移 */
printf("入队: %d\n", value);
}
/* 出队：从队首移除元素 */
int dequeue(struct Queue* q) {
if (isEmpty(q)) {
printf("队列为空！\n");
return -1;
}
return q->items[q->front++]; /* 返回 front 处元素，然后 front 后移 */
}
int main() {
struct Queue q;
initQueue(&q);
enqueue(&q, 10); /* 入队: 10 */
enqueue(&q, 20); /* 入队: 20 */
enqueue(&q, 30); /* 入队: 30 */
printf("出队: %d\n", dequeue(&q)); /* 输出: 出队: 10 (先进先出) */
printf("出队: %d\n", dequeue(&q)); /* 输出: 出队: 20 */
printf("出队: %d\n", dequeue(&q)); /* 输出: 出队: 30 */
return 0;
}
#include <stdbool.h>
#define MAX 100
struct Queue {
int items[MAX];
int front; /* 队首指针：指向第一个元素 */
int rear; /* 队尾指针：指向下一个待插入位置 */
};
void initQueue(struct Queue* q) {
q->front = 0;
q->rear = 0;
}
bool isEmpty(struct Queue* q) {
return q->front == q->rear;
}
bool isFull(struct Queue* q) {
return q->rear == MAX;
}
/* 入队：在队尾添加元素 */
void enqueue(struct Queue* q, int value) {
if (isFull(q)) {
printf("队列已满！\n");
return;
}
q->items[q->rear++] = value; /* 在 rear 处写入，然后 rear 后移 */
printf("入队: %d\n", value);
}
/* 出队：从队首移除元素 */
int dequeue(struct Queue* q) {
if (isEmpty(q)) {
printf("队列为空！\n");
return -1;
}
return q->items[q->front++]; /* 返回 front 处元素，然后 front 后移 */
}
int main() {
struct Queue q;
initQueue(&q);
enqueue(&q, 10); /* 入队: 10 */
enqueue(&q, 20); /* 入队: 20 */
enqueue(&q, 30); /* 入队: 30 */
printf("出队: %d\n", dequeue(&q)); /* 输出: 出队: 10 (先进先出) */
printf("出队: %d\n", dequeue(&q)); /* 输出: 出队: 20 */
printf("出队: %d\n", dequeue(&q)); /* 输出: 出队: 30 */
return 0;
}
普通数组实现的队列存在"假溢出"问题：随着不断的入队和出队，front 和 rear 持续向数组末尾移动，即使数组前面已有大量空位也无法再利用。解决方案是使用循环队列。
循环队列
循环队列 — 取模运算实现指针回绕
循环队列关键公式
入队: items[rear] = value; rear = (rear + 1) % MAX;
出队: value = items[front]; front = (front + 1) % MAX;
判空: front == rear | 判满: (rear + 1) % MAX == front
运行示例 (容量=5, 最多存4个)：入队 10→20→30→40, 出队 10→20, 入队 50→60 → 60 存入索引 0（回绕）完美利用释放空间
循环队列将数组在逻辑上视为首尾相连的环形结构，通过取模运算实现指针回绕。
实例
#include <stdio.h>
#include <stdbool.h>
#define MAX 5 /* 故意设置较小的容量，便于观察循环效果 */
struct CircularQueue {
int items[MAX];
int front; /* 队首索引 */
int rear; /* 队尾索引（下一个插入位置）*/
};
void initQueue(struct CircularQueue* q) {
q->front = 0;
q->rear = 0;
}
/* 判空：front 和 rear 重合 */
bool isEmpty(struct CircularQueue* q) {
return q->front == q->rear;
}
/* 判满：(rear + 1) % MAX == front
注意：循环队列故意空一个位置，用于区分空和满 */
bool isFull(struct CircularQueue* q) {
return (q->rear + 1) % MAX == q->front;
}
/* 入队：在 rear 处写入，然后 rear 循环后移 */
void enqueue(struct CircularQueue* q, int value) {
if (isFull(q)) {
printf("循环队列已满！\n");
return;
}
q->items[q->rear] = value;
q->rear = (q->rear + 1) % MAX; /* 取模实现回绕 */
printf("入队: %d (rear=%d)\n", value, q->rear);
}
/* 出队：返回 front 处元素，然后 front 循环后移 */
int dequeue(struct CircularQueue* q) {
if (isEmpty(q)) {
printf("循环队列为空！\n");
return -1;
}
int value = q->items[q->front];
q->front = (q->front + 1) % MAX; /* 取模实现回绕 */
return value;
}
int main() {
struct CircularQueue q;
initQueue(&q);
enqueue(&q, 10); /* 入队: 10 (rear=1) */
enqueue(&q, 20); /* 入队: 20 (rear=2) */
enqueue(&q, 30); /* 入队: 30 (rear=3) */
enqueue(&q, 40); /* 入队: 40 (rear=4) — 容量 5，最多存 4 个 */
printf("出队: %d\n", dequeue(&q)); /* 出队: 10 (front=1) */
printf("出队: %d\n", dequeue(&q)); /* 出队: 20 (front=2) */
enqueue(&q, 50); /* 入队: 50 (rear=0 — 回绕到开头！) */
enqueue(&q, 60); /* 入队: 60 (rear=1) */
printf("剩余元素: ");
while (!isEmpty(&q)) {
printf("%d ", dequeue(&q));
}
printf("\n"); /* 输出: 剩余元素: 30 40 50 60 */
return 0;
}
#include <stdbool.h>
#define MAX 5 /* 故意设置较小的容量，便于观察循环效果 */
struct CircularQueue {
int items[MAX];
int front; /* 队首索引 */
int rear; /* 队尾索引（下一个插入位置）*/
};
void initQueue(struct CircularQueue* q) {
q->front = 0;
q->rear = 0;
}
/* 判空：front 和 rear 重合 */
bool isEmpty(struct CircularQueue* q) {
return q->front == q->rear;
}
/* 判满：(rear + 1) % MAX == front
注意：循环队列故意空一个位置，用于区分空和满 */
bool isFull(struct CircularQueue* q) {
return (q->rear + 1) % MAX == q->front;
}
/* 入队：在 rear 处写入，然后 rear 循环后移 */
void enqueue(struct CircularQueue* q, int value) {
if (isFull(q)) {
printf("循环队列已满！\n");
return;
}
q->items[q->rear] = value;
q->rear = (q->rear + 1) % MAX; /* 取模实现回绕 */
printf("入队: %d (rear=%d)\n", value, q->rear);
}
/* 出队：返回 front 处元素，然后 front 循环后移 */
int dequeue(struct CircularQueue* q) {
if (isEmpty(q)) {
printf("循环队列为空！\n");
return -1;
}
int value = q->items[q->front];
q->front = (q->front + 1) % MAX; /* 取模实现回绕 */
return value;
}
int main() {
struct CircularQueue q;
initQueue(&q);
enqueue(&q, 10); /* 入队: 10 (rear=1) */
enqueue(&q, 20); /* 入队: 20 (rear=2) */
enqueue(&q, 30); /* 入队: 30 (rear=3) */
enqueue(&q, 40); /* 入队: 40 (rear=4) — 容量 5，最多存 4 个 */
printf("出队: %d\n", dequeue(&q)); /* 出队: 10 (front=1) */
printf("出队: %d\n", dequeue(&q)); /* 出队: 20 (front=2) */
enqueue(&q, 50); /* 入队: 50 (rear=0 — 回绕到开头！) */
enqueue(&q, 60); /* 入队: 60 (rear=1) */
printf("剩余元素: ");
while (!isEmpty(&q)) {
printf("%d ", dequeue(&q));
}
printf("\n"); /* 输出: 剩余元素: 30 40 50 60 */
return 0;
}
队列的应用场景
| 应用场景 | 说明 |
|---|---|
| 广度优先搜索（BFS） | 按层次逐层遍历图的节点，需要队列来存储"待访问"的节点 |
| 操作系统任务调度 | CPU 按任务到达的先后顺序分配时间片 |
| 打印任务队列 | 多台电脑共享一台打印机，打印请求按提交顺序排队处理 |
| 消息队列 | 分布式系统中，生产者产生的消息通过队列传递给消费者 |