数据结构 | 队列：从概念到实战

个人主页-爱因斯晨

文章专栏-数据结构

继续加油！

文章目录

• • 个人主页-爱因斯晨
  • 文章专栏-数据结构
  • 一、队列的基本概念
  • 二、队列的核心操作
  • 三、C 语言实现队列
  • • 3.1 顺序队列（数组实现）
    • 3.2 链式队列（链表实现）
  • 四、队列的应用场景
  • 五、两种实现的对比选择

一、队列的基本概念

队列是一种先进先出（FIFO，First In First Out） 的线性数据结构，仅允许在一端进行插入操作（队尾），另一端进行删除操作（队头）。

生活中的队列场景：

• 银行窗口排队办理业务

• 打印机任务队列

• 消息队列中的消息传递

二、队列的核心操作

1. 初始化（InitQueue）：创建一个空队列

2. 入队（EnQueue）：在队尾插入元素

3. 出队（DeQueue）：从队头删除元素

4. 获取队头元素（GetFront）：返回队头元素值

5. 判空（IsEmpty）：判断队列是否为空

6. 销毁（DestroyQueue）：释放队列占用的内存

三、C 语言实现队列

3.1 顺序队列（数组实现）

顺序队列使用数组存储元素，通过队头指针（front）和队尾指针（rear）标记队列边界。

#include #include #define MAX_SIZE 100 // 队列最大容量// 顺序队列结构体typedef struct { int data[MAX_SIZE]; int front; // 队头指针（指向队头元素） int rear; // 队尾指针（指向队尾元素的下一个位置）} SeqQueue;// 初始化队列void InitQueue(SeqQueue *q) { q->front = 0; q->rear = 0;}// 判空int IsEmpty(SeqQueue *q) { return q->front == q->rear;}// 判满int IsFull(SeqQueue *q) { return (q->rear + 1) % MAX_SIZE == q->front; // 预留一个空间区分空满}// 入队int EnQueue(SeqQueue *q, int value) { if (IsFull(q)) { printf(\"队列已满，无法入队\\n\"); return 0; // 入队失败 } q->data[q->rear] = value; q->rear = (q->rear + 1) % MAX_SIZE; // 循环移动队尾指针 return 1; // 入队成功}// 出队int DeQueue(SeqQueue *q, int *value) { if (IsEmpty(q)) { printf(\"队列为空，无法出队\\n\"); return 0; // 出队失败 } *value = q->data[q->front]; q->front = (q->front + 1) % MAX_SIZE; // 循环移动队头指针 return 1; // 出队成功}// 获取队头元素int GetFront(SeqQueue *q, int *value) { if (IsEmpty(q)) { printf(\"队列为空，无队头元素\\n\"); return 0; } *value = q->data[q->front]; return 1;}// 测试顺序队列int main() { SeqQueue q; InitQueue(&q); // 入队操作 EnQueue(&q, 10); EnQueue(&q, 20); EnQueue(&q, 30); // 获取队头元素 int frontVal; GetFront(&q, &frontVal); printf(\"队头元素：%d\\n\", frontVal); // 输出：10 // 出队操作 int deVal; DeQueue(&q, &deVal); printf(\"出队元素：%d\\n\", deVal); // 输出：10 // 再次获取队头 GetFront(&q, &frontVal); printf(\"新队头元素：%d\\n\", frontVal); // 输出：20 return 0;}

顺序队列特点：

• 优点：实现简单，访问速度快

• 缺点：容量固定，存在 “假溢出” 问题（需用循环队列优化）

3.2 链式队列（链表实现）

链式队列使用链表存储元素，队头指针指向头节点，队尾指针指向尾节点。

#include #include // 节点结构体typedef struct Node { int data; struct Node *next;} Node;// 链式队列结构体typedef struct { Node *front; // 队头指针（指向头节点） Node *rear; // 队尾指针（指向尾节点）} LinkQueue;// 初始化队列void InitQueue(LinkQueue *q) { // 创建头节点（不存储数据） Node *head = (Node*)malloc(sizeof(Node)); head->next = NULL; q->front = head; q->rear = head;}// 判空int IsEmpty(LinkQueue *q) { return q->front == q->rear;}// 入队void EnQueue(LinkQueue *q, int value) { // 创建新节点 Node *newNode = (Node*)malloc(sizeof(Node)); newNode->data = value; newNode->next = NULL; // 插入到队尾 q->rear->next = newNode; q->rear = newNode; // 更新队尾指针}// 出队int DeQueue(LinkQueue *q, int *value) { if (IsEmpty(q)) { printf(\"队列为空，无法出队\\n\"); return 0; } Node *temp = q->front->next; // 待删除节点 *value = temp->data; q->front->next = temp->next; // 如果删除的是最后一个节点，需更新队尾指针 if (q->rear == temp) { q->rear = q->front; } free(temp); // 释放节点内存 return 1;}// 获取队头元素int GetFront(LinkQueue *q, int *value) { if (IsEmpty(q)) { printf(\"队列为空，无队头元素\\n\"); return 0; } *value = q->front->next->data; return 1;}// 销毁队列void DestroyQueue(LinkQueue *q) { // 释放所有节点 while (q->front != NULL) { q->rear = q->front->next; free(q->front); q->front = q->rear; }}// 测试链式队列int main() { LinkQueue q; InitQueue(&q); // 入队 EnQueue(&q, 100); EnQueue(&q, 200); EnQueue(&q, 300); // 获取队头 int frontVal; GetFront(&q, &frontVal); printf(\"队头元素：%d\\n\", frontVal); // 输出：100 // 出队 int deVal; DeQueue(&q, &deVal); printf(\"出队元素：%d\\n\", deVal); // 输出：100 // 销毁队列 DestroyQueue(&q); return 0;}

链式队列特点：

• 优点：容量动态扩展，不存在溢出问题

• 缺点：需要额外空间存储指针，操作稍复杂

四、队列的应用场景

1. 广度优先搜索（BFS）：在二叉树层次遍历、图的遍历中常用

2. 缓冲处理：如键盘输入缓冲、网络数据接收缓冲

3. 任务调度：操作系统中的进程调度、线程池任务调度

4. 消息传递：分布式系统中的消息队列（如 RabbitMQ）

五、两种实现的对比选择

场景 推荐实现 理由 已知数据量且固定 顺序队列 效率更高，无需额外指针开销 数据量动态变化 链式队列 避免空间浪费和溢出问题 频繁插入删除 链式队列 操作更高效（O (1) 时间复杂度） 对内存使用敏感 顺序队列 内存连续分配，缓存利用率高