数据结构之队列

欢迎拜访：雾里看山-CSDN博客
本篇主题：数据结构之队列
发布时间：2025.7.9
隶属专栏：数据结构

队列的概念与结构

基本概念

队列是一种先进先出（FIFO: First-In-First-Out）的线性数据结构，只允许在固定的一端进行插入（入队），在另一端进行删除（出队）。队列的操作特性可类比现实生活中的排队：

• 入队 (Enqueue)：将元素添加到队列尾部
• 出队 (Dequeue)：从队列头部移除元素
• 队头 (Front)：队列中最早添加的元素位置
• 队尾 (Rear)：队列中最新添加的元素位置

核心特性

• FIFO原则：最先入队的元素最先出队
• 受限访问：只能访问队头和队尾元素
• 动态大小：大小随操作变化（除固定大小队列）
• 操作高效：所有操作时间复杂度为O(1)

队列的实现

链表实现队列

队列结构的定义

1. 定义存储的数据类型。
2. 定义每一个节点，节点里面存储数据和下一个节点的指针
3. 定义队列，队列里存储头结点和尾结点以及队列中存储数据的个数

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;
}

数组实现循环队列

队列结构的定义

1. 需要指定循环队列的大小，可以存储的数据量是MAX_SIZE-1
2. 定义存储的数据类型
3. 定义循环队列，包括用于存储数据的数组，和两个下标分别指向头部位置和尾部的下一个位置

#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)

实现选择建议

应用领域总结

• 操作系统：进程调度、I/O请求管理
• 网络通信：数据包缓冲、流量控制
• 实时系统：事件处理、消息传递
• 算法实现：BFS、缓存算法
• 分布式系统：任务队列、消息队列
• 图形处理：渲染队列、事件处理

⚠️ 写在最后：以上内容是我在学习以后得一些总结和概括，如有错误或者需要补充的地方欢迎各位大佬评论或者私信我交流！！！