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

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

生活中的队列场景：

银行窗口排队办理业务

打印机任务队列

消息队列中的消息传递

二、队列的核心操作初始化（InitQueue）：创建一个空队列

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

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

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

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

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

三、C 语言实现队列 3.1 顺序队列（数组实现）顺序队列使用数组存储元素，通过队头指针（front）和队尾指针（rear）标记队列边界。

#include <stdio.h> #include <stdlib.h> #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);  // 输出：20return 0;

} AI写代码 c 运行 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 顺序队列特点：

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

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

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

#include <stdio.h> #include <stdlib.h>

// 节点结构体 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;

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

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

四、队列的应用场景广度优先搜索（BFS）：在二叉树层次遍历、图的遍历中常用

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

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

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

五、两种实现的对比选择场景推荐实现理由已知数据量且固定顺序队列效率更高，无需额外指针开销数据量动态变化链式队列避免空间浪费和溢出问题频繁插入删除链式队列操作更高效（O (1) 时间复杂度）对内存使用敏感顺序队列内存连续分配，缓存利用率高 ———————————————— 版权声明：本文为CSDN博主「钮祜禄.爱因斯晨」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。原文链接：https://blog.csdn.net/2401_87533975/article/details/149719304

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.tpcf.cn/news/918182.html

如若内容造成侵权/违法违规/事实不符，请联系多彩编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！