队列Queue原理及其C语言实现

原理

队列是一种 先进先出（FIFO, First In First Out） 的线性数据结构，操作限制在两端：

队尾（Rear）：仅允许插入元素（入队，enqueue）。
队头（Front）：仅允许删除元素（出队，dequeue）。

队列的底层可通过数组或链表实现。数组实现需处理固定大小和循环利用（避免空间浪费），链表实现则动态扩展。

对列操作示意

1. 初始状态Front = -1, Rear = -1+---+---+---+---+---+|   |   |   |   |   |+---+---+---+---+---+2. 入队元素 AFront = 0, Rear = 0+---+---+---+---+---+| A |   |   |   |   |+---+---+---+---+---+3. 入队元素 B、CFront = 0, Rear = 2+---+---+---+---+---+| A | B | C |   |   |+---+---+---+---+---+4. 出队元素 AFront = 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 5typedef 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));  // 输出 101printf("下一个客户: %d\n", peek(queue));    // 输出 102// 新客户继续取号enqueue(queue, 104);enqueue(queue, 105);enqueue(queue, 106);  // 触发队列已满提示printQueue(queue);    // 输出: 102 103 104 105return 0;
}

实现方式对比