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

个人主页-爱因斯晨

文章专栏-数据结构

继续加油！

文章目录

• 个人主页-爱因斯晨
• 文章专栏-数据结构
• 一、队列的基本概念
• 二、队列的核心操作
• 三、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<stdio.h>#include<stdlib.h>#defineMAX_SIZE100// 队列最大容量// 顺序队列结构体typedefstruct{int data[MAX_SIZE];int front;// 队头指针（指向队头元素）int rear;// 队尾指针（指向队尾元素的下一个位置）} SeqQueue;// 初始化队列voidInitQueue(SeqQueue *q){ q->front =0; q->rear =0;}// 判空intIsEmpty(SeqQueue *q){return q->front == q->rear;}// 判满intIsFull(SeqQueue *q){return(q->rear +1)% MAX_SIZE == q->front;// 预留一个空间区分空满}// 入队intEnQueue(SeqQueue *q,int value){if(IsFull(q)){printf("队列已满，无法入队\n");return0;// 入队失败} q->data[q->rear]= value; q->rear =(q->rear +1)% MAX_SIZE;// 循环移动队尾指针return1;// 入队成功}// 出队intDeQueue(SeqQueue *q,int*value){if(IsEmpty(q)){printf("队列为空，无法出队\n");return0;// 出队失败}*value = q->data[q->front]; q->front =(q->front +1)% MAX_SIZE;// 循环移动队头指针return1;// 出队成功}// 获取队头元素intGetFront(SeqQueue *q,int*value){if(IsEmpty(q)){printf("队列为空，无队头元素\n");return0;}*value = q->data[q->front];return1;}// 测试顺序队列intmain(){ 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);// 输出：20return0;}

顺序队列特点：

• 优点：实现简单，访问速度快
• 缺点：容量固定，存在 “假溢出” 问题（需用循环队列优化）

3.2 链式队列（链表实现）

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

#include<stdio.h>#include<stdlib.h>// 节点结构体typedefstructNode{int data;structNode*next;} Node;// 链式队列结构体typedefstruct{ Node *front;// 队头指针（指向头节点） Node *rear;// 队尾指针（指向尾节点）} LinkQueue;// 初始化队列voidInitQueue(LinkQueue *q){// 创建头节点（不存储数据） Node *head =(Node*)malloc(sizeof(Node)); head->next =NULL; q->front = head; q->rear = head;}// 判空intIsEmpty(LinkQueue *q){return q->front == q->rear;}// 入队voidEnQueue(LinkQueue *q,int value){// 创建新节点 Node *newNode =(Node*)malloc(sizeof(Node)); newNode->data = value; newNode->next =NULL;// 插入到队尾 q->rear->next = newNode; q->rear = newNode;// 更新队尾指针}// 出队intDeQueue(LinkQueue *q,int*value){if(IsEmpty(q)){printf("队列为空，无法出队\n");return0;} Node *temp = q->front->next;// 待删除节点*value = temp->data; q->front->next = temp->next;// 如果删除的是最后一个节点，需更新队尾指针if(q->rear == temp){ q->rear = q->front;}free(temp);// 释放节点内存return1;}// 获取队头元素intGetFront(LinkQueue *q,int*value){if(IsEmpty(q)){printf("队列为空，无队头元素\n");return0;}*value = q->front->next->data;return1;}// 销毁队列voidDestroyQueue(LinkQueue *q){// 释放所有节点while(q->front !=NULL){ q->rear = q->front->next;free(q->front); q->front = q->rear;}}// 测试链式队列intmain(){ 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);return0;}

链式队列特点：

• 优点：容量动态扩展，不存在溢出问题
• 缺点：需要额外空间存储指针，操作稍复杂

四、队列的应用场景

1. 广度优先搜索（BFS）：在二叉树层次遍历、图的遍历中常用
2. 缓冲处理：如键盘输入缓冲、网络数据接收缓冲
3. 任务调度：操作系统中的进程调度、线程池任务调度
4. 消息传递：分布式系统中的消息队列（如 RabbitMQ）

五、两种实现的对比选择