当前位置：首页 > news >正文

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

news 2025/7/29 9:46:48

个人主页-爱因斯晨

文章专栏-数据结构

继续加油！

文章目录

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

一、队列的基本概念

队列是一种先进先出（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;
}

顺序队列特点：

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

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) 时间复杂度）
对内存使用敏感	顺序队列	内存连续分配，缓存利用率高