原理
队列是一种 先进先出(FIFO, First In First Out) 的线性数据结构,操作限制在两端:
队尾(Rear):仅允许插入元素(入队,
enqueue
)。队头(Front):仅允许删除元素(出队,
dequeue
)。
队列的底层可通过 数组 或 链表 实现。数组实现需处理固定大小和循环利用(避免空间浪费),链表实现则动态扩展。
对列操作示意
1. 初始状态
Front = -1, Rear = -1
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
2. 入队元素 A
Front = 0, Rear = 0
+---+---+---+---+---+
| A | | | | |
+---+---+---+---+---+
3. 入队元素 B、C
Front = 0, Rear = 2
+---+---+---+---+---+
| A | B | C | | |
+---+---+---+---+---+
4. 出队元素 A
Front = 1, Rear = 2
+---+---+---+---+---+
| | B | C | | |
+---+---+---+---+---+
5. 循环队列(数组满后复用空间)
Front = 1, Rear = 0
+---+---+---+---+---+
| D | B | C | E | F | → Rear 回到索引 0(循环)
+---+---+---+---+---+
应用场景
任务调度:操作系统按顺序处理进程请求。
消息队列:异步通信系统中缓冲消息(如 RabbitMQ)。
打印机任务:按提交顺序打印文件。
广度优先搜索(BFS):遍历树或图的节点层级。
实时系统:事件按发生顺序处理(如键盘输入缓冲)。
C语言代码实现
//1. 定义队列结构
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5
typedef struct Queue {
int data[MAX_SIZE];
int front; // 队头索引
int rear; // 队尾索引
} Queue;
//2. 初始化队列
Queue* createQueue() {
Queue* queue = (Queue*)malloc(sizeof(Queue));
if (!queue) {
printf("内存分配失败!\n");
exit(1);
}
queue->front = -1;
queue->rear = -1;
return queue;
}
//3. 基本操作实现
// 判空
int isEmpty(Queue* queue) {
return queue->front == -1;
}
// 判满
int isFull(Queue* queue) {
return (queue->rear + 1) % MAX_SIZE == queue->front;
}
// 入队
void enqueue(Queue* queue, int value) {
if (isFull(queue)) {
printf("队列已满,无法入队!\n");
return;
}
if (isEmpty(queue)) {
queue->front = 0;
}
queue->rear = (queue->rear + 1) % MAX_SIZE;
queue->data[queue->rear] = value;
}
// 出队
int dequeue(Queue* queue) {
if (isEmpty(queue)) {
printf("队列为空,无法出队!\n");
return -1;
}
int value = queue->data[queue->front];
if (queue->front == queue->rear) {
// 队列只剩一个元素,重置指针
queue->front = queue->rear = -1;
} else {
queue->front = (queue->front + 1) % MAX_SIZE;
}
return value;
}
// 查看队头
int peek(Queue* queue) {
if (isEmpty(queue)) {
printf("队列为空!\n");
return -1;
}
return queue->data[queue->front];
}
// 打印队列
void printQueue(Queue* queue) {
if (isEmpty(queue)) {
printf("队列为空!\n");
return;
}
int i = queue->front;
printf("队列元素: ");
do {
printf("%d ", queue->data[i]);
i = (i + 1) % MAX_SIZE;
} while (i != (queue->rear + 1) % MAX_SIZE);
printf("\n");
}
/* ---------- 应用示例:模拟银行叫号系统 ---------- */
int main() {
Queue* queue = createQueue(); // 创建容量为5的队列
// 客户取号
enqueue(queue, 101);
enqueue(queue, 102);
enqueue(queue, 103);
printQueue(queue); // 输出: 101 102 103
// 柜员处理客户
printf("正在处理: %d\n", dequeue(queue)); // 输出 101
printf("下一个客户: %d\n", peek(queue)); // 输出 102
// 新客户继续取号
enqueue(queue, 104);
enqueue(queue, 105);
enqueue(queue, 106); // 触发队列已满提示
printQueue(queue); // 输出: 102 103 104 105
return 0;
}
实现方式对比
总结
核心特性:先进先出,操作受限(仅队头出队、队尾入队)。
时间复杂度:入队、出队、查看队头均为 O(1)。
适用场景:需按顺序处理任务的场景(如调度、缓冲、BFS)。