欢迎拜访:雾里看山-CSDN博客
本篇主题:数据结构之队列
发布时间:2025.7.9
隶属专栏:数据结构
目录
队列的概念与结构
基本概念
队列是一种先进先出(FIFO: First-In-First-Out
)的线性数据结构,只允许在固定的一端进行插入(入队),在另一端进行删除(出队)。队列的操作特性可类比现实生活中的排队:
- 入队 (Enqueue):将元素添加到队列尾部
- 出队 (Dequeue):从队列头部移除元素
- 队头 (Front):队列中最早添加的元素位置
- 队尾 (Rear):队列中最新添加的元素位置
核心特性
- FIFO原则:最先入队的元素最先出队
- 受限访问:只能访问队头和队尾元素
- 动态大小:大小随操作变化(除固定大小队列)
- 操作高效:所有操作时间复杂度为O(1)
队列的实现
链表实现队列
队列结构的定义
- 定义存储的数据类型。
- 定义每一个节点,节点里面存储数据和下一个节点的指针
- 定义队列,队列里存储头结点和尾结点以及队列中存储数据的个数
typedef int QDataType;
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Que;
队列基本操作的实现
队列的基本操作包括:初始化,销毁,入队列,出队列,获取头部节点数据,获取尾部节点数据,队列判空,队列存储数据个数。
初始化:
void QueueInit(Que* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
销毁:
void QueueDestroy(Que* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* tmp = cur;
cur = cur->next;
free(tmp);
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
入队列:
void QueuePush(Que* pq, QDataType x)
{
assert(pq);
QNode* newnode = (QNode* )malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)// Ϊ
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
出队列:
void QueuePop(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
QNode* temp = pq->head;
if (pq->head->next == NULL)
{
pq->head = pq->tail = NULL;
}
else
{
pq->head = pq->head->next;
}
pq->size--;
free(temp);
}
获取队列头部数据:
QDataType QueueFront(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
获取队列尾部数据:
QDataType QueueBack(Que* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}
队列判空:
bool QueueEmpty(Que* pq)
{
assert(pq);
return pq->size == 0;
}
队列中存储元素个数:
int QueueSize(Que* pq)
{
assert(pq);
return pq->size;
}
数组实现循环队列
队列结构的定义
- 需要指定循环队列的大小,可以存储的数据量是
MAX_SIZE-1
- 定义存储的数据类型
- 定义循环队列,包括用于存储数据的数组,和两个下标分别指向头部位置和尾部的下一个位置
#define MAX_SIZE 10
typedef int CirQueueDataType;
typedef struct cir_queue
{
CirQueueDataType data[MAX_SIZE];
int front;
int rear;
}CirQueue;
队列基本操作的实现
队列的基本操作包括:初始化,队列判空,队列判满,入队列,出队列,获取头部节点数据,获取尾部节点数据,队列存储数据个数。
初始化:
void CirQueueInit(CirQueue* pcq)
{
assert(pcq);
pcq->front = pcq->rear = 0;
}
队列判空:
bool CirQueueIsEmpty(CirQueue* pcq)
{
assert(pcq);
return pcq->front == pcq->rear;
}
队列判满:
bool CirQueueIsFull(CirQueue* pcq)
{
assert(pcq);
return (pcq->rear + 1) % MAX_SIZE == pcq->front;
}
入队列:
void CirQueuePush(CirQueue* pcq, CirQueueDataType x)
{
if (CirQueueIsFull(pcq))
{
printf("队列已满\n");
return;
}
pcq->data[pcq->rear] = x;
pcq->rear = (pcq->rear + 1) % MAX_SIZE;
}
出队列:
void CirQueuePop(CirQueue* pcq)
{
if (CirQueueIsEmpty(pcq))
{
printf("队列为空\n");
return;
}
pcq->front = (pcq->front + 1) % MAX_SIZE;
}
获取队列头部数据:
CirQueueDataType CirQueueFront(CirQueue* pcq)
{
if (CirQueueIsEmpty(pcq))
{
printf("队列为空\n");
return;
}
return pcq->data[pcq->front];
}
获取队列尾部数据:
CirQueueDataType CirQueueBack(CirQueue* pcq)
{
if (CirQueueIsEmpty(pcq))
{
printf("队列为空\n");
return;
}
return pcq->data[((pcq->rear - 1)+MAX_SIZE)%MAX_SIZE];
}
队列存储数据个数:
int CirQueueSize(CirQueue* pcq)
{
return (pcq->rear - pcq->front + MAX_SIZE) % MAX_SIZE;
}
两种实现的比较
特性 | 循环队列 | 链式队列 |
---|---|---|
内存分配 | 静态/固定大小 | 动态分配/无固定大小 |
空间效率 | 无额外指针开销 | 每个节点额外指针开销 |
时间效率 | 所有操作O(1) | 所有操作O(1) |
扩容能力 | 有限(固定大小) | 无限(除非内存耗尽) |
假溢出 | 不存在 | 不存在 |
缓存友好 | 高(连续内存) | 低(非连续内存) |
适用场景 | 元素数量固定/可预测 | 元素数量变化大/不可预测 |
总结与选择建议
队列的核心价值
- 先进先出:保证元素处理顺序的公平性
- 缓冲机制:平衡生产者和消费者的速度差异
- 解耦系统:分离任务的产生和处理
- 高效操作:所有基本操作时间复杂度O(1)
实现选择建议
场景 | 推荐实现 | 理由 |
---|---|---|
元素数量固定/可预测 | 循环队列 | 内存紧凑,无额外开销 |
元素数量变化大/不可预测 | 链式队列 | 动态扩展,无容量限制 |
高频访问/内存敏感 | 循环队列 | 缓存友好,访问速度快 |
需要精确控制内存 | 循环队列 | 预分配固定大小内存 |
需要实现复杂队列类型 | 链式队列 | 灵活性高,易于扩展 |
应用领域总结
- 操作系统:进程调度、I/O请求管理
- 网络通信:数据包缓冲、流量控制
- 实时系统:事件处理、消息传递
- 算法实现:BFS、缓存算法
- 分布式系统:任务队列、消息队列
- 图形处理:渲染队列、事件处理
⚠️ 写在最后:以上内容是我在学习以后得一些总结和概括,如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流!!!