数据结构（C语言篇）：（九）队列

_OP_CHEN

发布于 2026-01-14 09:33:39

1050

文章被收录于专栏：C++C++

前言

队列是一种基础且重要的线性数据结构，广泛应用于计算机科学的各个领域。其核心特性遵循“先进先出”（FIFO）原则，使得队列在任务调度、缓冲管理、广度优先搜索等场景中具有不可替代的作用。随着现代系统对实时性和并发处理需求的提升，队列的高效实现与优化成为开发者和研究者关注的焦点。本文将从队列的基本概念入手，逐步探讨其实现方式、典型应用场景以及性能优化策略，下面就让我们正式开始吧！

一、概念与结构

概念：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO（First In First Out）的特性。

入队列：进行插入操作的一端称为队尾。

出队列：进行删除操作的一端称为队头。

示意图如下所示：

队列可以使用数组和链表的结构来实现，但是显然使用链表的结构实现更优一些，因为如果使用数组的结构，出队列的时候只能在数组头上出数据，效率会比较低。

二、队列的实现

2.1 头文件的准备

我们将队列的结构和相关函数在头文件中声明如下：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;
//定义节点结构
typedef struct QueueNode {
	QDataType data;
	struct QueueNode* next;
}QueueNode;

//定义队列的结构
typedef struct Queue {
	QueueNode* phead; //队头
	QueueNode* ptail; //队尾
	//int size;         //队列中有效数据个数
}Queue; 

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDesTroy(Queue* pq);

//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);

bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);

2.2 函数的实现

2.2.1 QueueInit( )函数（初始化）

函数的实现逻辑如下：

1.参数验证：确保队列指针 pq 不为 NULL。

assert(pq);

2.初始化头尾指针：

将队列的头指针 phead 设置为 NULL

将队列的尾指针 ptail 设置为 NULL

表示队列为空，没有任何节点

pq->phead = pq->ptail = NULL;

完整代码如下所示：

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
}

使用示例如下：

Queue q;
QueueInit(&q);  // 初始化队列

// 现在队列是空的，可以开始使用
QueuePush(&q, 10);
QueuePush(&q, 20);
// ...

2.2.2 QueuePush( )函数（入队）

画图分析如下：

函数的实现逻辑如下：

1.参数验证：确保队列指针 pq 不为 NULL。

assert(pq);

2.创建新结点：动态分配新结点的内存；检查内存分配是否成功；设置新结点的数据和指针。

QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
    perror("malloc fail!");
    exit(1);
}
newnode->data = x;
newnode->next = NULL;

3.处理空队列情况：如果队列为空（头指针为 NULL），将头指针和尾指针都指向新节点（新节点既是队头也是队尾）。

if (pq->phead == NULL)
{
    pq->phead = pq->ptail = newnode;
}

4.处理非空队列情况：将当前尾节点的 next 指向新节点，然后更新尾指针指向新节点，最后新节点成为新的队尾。

else {
    pq->ptail->next = newnode;
    pq->ptail = pq->ptail->next;
}

使用示例如下：

Queue q;
QueueInit(&q);

QueuePush(&q, 10);  // 队列: 10
QueuePush(&q, 20);  // 队列: 10 → 20  
QueuePush(&q, 30);  // 队列: 10 → 20 → 30

2.2.3 QueuePop( )函数（出队）

在实现出队函数之前，我们先来实现一下QueueEmpty 函数，即判空函数：

实现逻辑如下：

参数验证：确保队列指针不为 NULL
空队列判断：如果头指针为 NULL，队列为空，返回 true
非空队列：如果头指针不为 NULL，队列非空，返回 false

bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->phead == NULL;
}

接着画图分析一下出队函数：

函数实现逻辑如下：

1.前置条件检查：确保队列不为空，不能从空队列出队。

assert(!QueueEmpty(pq));

2.处理只有一个结点的情况：如果头指针和尾指针指向同一个结点，说明队列只有一个结点；释放该节点的内存；将头尾指针都设置为 NULL，表示队列为空。

if (pq->phead == pq->ptail)
{
    free(pq->phead);
    pq->phead = pq->ptail = NULL;
}

3.处理多个结点的情况：保存头结点的下一个结点指针；释放当前头结点的内存，最后将头指针指向下一个结点。

else {
    QueueNode* next = pq->phead->next;
    free(pq->phead);
    pq->phead = next;
}

完整代码如下所示：

//出队列
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));

	//队列中只有一个节点
	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else {
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
}

使用示例如下：

Queue q;
QueueInit(&q);

QueuePush(&q, 10);
QueuePush(&q, 20);
QueuePush(&q, 30);
// 队列: 10 → 20 → 30

QueuePop(&q);  // 移除10，队列: 20 → 30
QueuePop(&q);  // 移除20，队列: 30
QueuePop(&q);  // 移除30，队列: 空

2.2.4 QueueFront( )和QueueBack( )函数（取队头和取队尾）

首先来看取队头函数的实现逻辑：

前置条件检查：确保队列不为空；
返回数据：返回头指针所指节点的数据。

完整代码如下：

QDataType QueueFront(Queue* pq)
{
    assert(!QueueEmpty(pq));
    return pq->phead->data;
}

再来看取队尾函数的实现逻辑：

前置条件检查：确保队列不为空；
返回数据：返回尾指针所指节点的数据。

完整代码如下：

QDataType QueueBack(Queue* pq)
{
    assert(!QueueEmpty(pq));
    return pq->ptail->data;
}

两个函数的使用示例如下：

Queue q;
QueueInit(&q);

QueuePush(&q, 10);
QueuePush(&q, 20); 
QueuePush(&q, 30);
QueuePush(&q, 40);
// 队列: 10 → 20 → 30 → 40

QDataType front = QueueFront(&q);  // front = 10
QDataType back = QueueBack(&q);    // back = 40

printf("队头: %d, 队尾: %d\n", front, back);
// 输出: 队头: 10, 队尾: 40

// 队列保持不变: 10 → 20 → 30 → 40

2.2.5 QueueSize( )函数（获取队列有效元素个数）

函数的实现逻辑如下：

1.参数验证：确保队列指针 pq 不为 NULL。

assert(pq);

2.初始化遍历变量：

pcur 指向队列的头节点，用于遍历链表；
size 初始化为0，用于计数。

QueueNode* pcur = pq->phead;
int size = 0;

3.遍历队列计数：循环遍历每个结点，直到遇到遇到 NULL（链表结束）；每遇到一个节点，计数器 size 加1；移动到下一个节点继续遍历。

while (pcur)
{
    ++size;
    pcur = pcur->next;
}

完整代码如下：

//队列有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	QueueNode* pcur = pq->phead;
	int size = 0;
	while (pcur)
	{
		++size;
		pcur = pcur->next;
	}
	return size;

	//return pq->size;
}

使用示例如下：

Queue q;
QueueInit(&q);

printf("初始队列大小: %d\n", QueueSize(&q));  // 输出: 0

QueuePush(&q, 10);
QueuePush(&q, 20);
QueuePush(&q, 30);

printf("当前队列大小: %d\n", QueueSize(&q));  // 输出: 3

QueuePop(&q);
printf("出队后大小: %d\n", QueueSize(&q));    // 输出: 2

2.2.6 QueueDestroy( )函数（销毁队列）

1.参数验证：确保队列指针 pq 不为 NULL。

assert(pq);

2.初始化遍历指针：创建当前指针 pcur 并初始化为头指针，用于遍历队列中的所有节点。

QueueNode* pcur = pq->phead;

3.遍历并释放所有结点：

保存下一个节点：在释放当前节点前，先保存下一个节点的指针；
释放当前节点：使用 free() 释放当前节点的内存；
移动到下一个节点：将 pcur 指向之前保存的下一个节点；
循环继续直到 pcur 为 NULL（队列末尾）。

while (pcur)
{
    QueueNode* next = pcur->next;
    free(pcur);
    pcur = next;
}

4.重置队列指针：将头指针和尾指针都设置为 NULL，表示队列为空，避免野指针。

pq->phead = pq->ptail = NULL;

完整代码如下：

//销毁
void QueueDesTroy(Queue* pq)
{
	assert(pq);

	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail = NULL;
}