队列的完整实现
队列(Queue)是计算机科学中一种基础且关键的数据结构。无论是操作系统任务调度、网络数据包管理,还是广度优先搜索(BFS),其'先进先出'(FIFO)的特性都使其不可或缺。理解队列的实现原理,能为后续学习复杂数据结构打下坚实基础。
本文将采用链式结构为核心,详细介绍队列的完整实现。相比于数组,链表在动态扩容和头部操作效率上更具优势。我们将重点剖析入队(push)、出队(pop)、获取队头/队尾元素等核心操作,并通过清晰的代码示例帮助深入理解内部机制。
1. 队列的概念与结构选择
概念 队列是一种只允许在一端插入数据、另一端删除数据的特殊线性表。
- 入队列:插入端称为队尾,对应
push操作。 - 出队列:删除端称为队头,对应
pop操作。
结构选择
虽然数组和链表均可实现队列,但链表更为优。数组在头部出数据时涉及大量元素移动,效率较低;而链表实现的队列,入队对应尾插,出队对应头删,仅需 O(1) 时间复杂度。因此,本文采用单链表来实现队列。
2. 核心接口与架构设计
我们需要定义以下核心接口:
- 初始化与销毁队列
- 队尾入队、队头出队
- 获取队头/队尾元素
- 获取有效元素个数、检测队列是否为空
结构体定义
typedef int QDataType;
typedef struct QNode {
struct QNode* next;
QDataType data;
} QNode;
typedef struct Queue {
QNode* head;
QNode* tail;
int size;
} Queue;
这里使用 QNode 表示链表结点,包含数据和指向下一个结点的指针。struct Queue 则维护整个队列的状态,其中 head 和 tail 分别指向第一个和最后一个结点,方便快速访问两端;size 用于记录当前元素个数,避免每次计算长度时遍历链表。
3. 初始化与销毁
初始化时,需将头尾指针置空,大小归零。销毁时,必须逐个释放链表结点,防止内存泄漏。
void QueueInit(Queue* pQueue) {
assert(pQueue);
pQueue->head = pQueue->tail = NULL;
pQueue->size = 0;
}
void QueueDestroy {
assert(pQueue);
QNode* cur = pQueue->head;
(cur != ) {
QNode* next = cur->next;
(cur);
cur = next;
}
pQueue->head = pQueue->tail = ;
pQueue->size = ;
}


