数据结构：队列

前言 

本篇文章将讲解队列的概念和结构，队列的实现等知识的相关内容，本章代码实现的知识，与单向链表相关，所以如果还没看过单向链表文章，可以看看：

https://blog.ZEEKLOG.net/2401_86982201/article/details/154615762?fromshare=blogdetail&sharetype=blogdetail&sharerId=154615762&sharerefer=PC&sharesource=2401_86982201&sharefrom=from_link

一、队列概念与结构

概念

与栈的数据结构类似，队列：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)特性。

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

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

图示：

我们可以将其类比成“单向管道”，数据从管道的一端（队尾）进入，只能从另一端（队头）按顺序流出，中间无法插队或删除中间元素，正好契合了他的“先进先出（FIFO）”的特性。

即：

入队（Enqueue） → 向管道塞入数据；出队（Dequeue） → 从管道取出最先进去的数据；队空 → 管道里没有数据；队满（顺序队列） → 管道被数据塞满，无法再塞入。

结构

  队列常见实现方式有顺序队列（数组）和链式队列（链表）。但是如果我们使用顺序结构时，我们的插入值的操作是可以很好的满足，但如果我们删除值呢？如果直接删去头部值，那样头部的空间会被空住了，浪费空间，如果数据很多的情况下那是个不小的损耗，我们如果通过整体前移动一位，那样操作，每次的时间复杂度都是O(n)。至于最好的解决方法，是构建循环队列。循环队列的整体实现较难，所以就不讲数组的结构了。

链式存储

  虽然使用链表在入队尾插的时候，时间复杂度也很高，但我们可以定义一个尾结点，在进行插入时通过尾指针来实现:

#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int type; typedef struct QueueNode { type date; struct QueueNode* next; }QueueNode; typedef struct Queue { struct QueueNode* phead; struct QueueNode* ptail; }Queue;

讲解：

通过头指针（phead）和尾指针（ptail）分别指向队头和队尾，可以支持高效的入队（尾插）和出队（头删）操作。结构成员详解QueueNode（队列节点结构体）date：存储队列元素的数据域（类型为 type，此处定义为 int）。next：指向后一个节点的指针域，构建链表结构。Queue（队列管理结构体）phead：指向队列的头节点（队头），出队操作从此处移除元素。ptail：指向队列的尾节点（队尾），入队操作从此处添加元素。

二、队列实现

1.队列初始化

• 目标：将队列初始化为空队列状态，即队头（phead）和队尾（ptail）指针均指向 NULL。
• 我们可以将队列的实现简单看成链表的实现，毕竟底层用的是链表。

函数为：

void QueueInit(Queue* h);

代码：

void QueueInit(Queue* h) { assert(h); h->phead = h->ptail = NULL; }

讲解：

函数功能

将链式队列初始化为空队列，即队头（phead）和队尾（ptail）指针均指向 NULL。

assert(h) 的作用强制检查传入的队列指针 h 是否有效（非 NULL），若为 NULL 则程序直接终止并报错，避免后续对空指针的非法访问（如 h->phead 操作）。初始化逻辑空队列的标志是 phead 和 ptail 均为 NULL，表示队列中暂无任何节点。

赋值语句 h->phead = h->ptail = NULL 等价于：

h->phead = NULL; h->ptail = NULL; 

所以可以以h->phead = h->ptail = NULL 形式简写。

 2.入队列

• 入队操作是队列的核心功能，时间复杂度为 O(1)（仅修改指针），我们可将其实现；类比链表的尾差，不同的是，链表尾差需要先遍历到尾节点，在进行插入，我们使用队列的尾指针可以以时间复杂度为 O(1)来访问尾节点的。

图例：

函数为：

void QueuePush(Queue* h, type x);

因为插入的是节点，所以需要与链表一样写一个创建节点的函数：

创建节点的函数

QueueNode* Creat(type x)

代码：

QueueNode* Creat(type x) { QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode)); if (p == NULL) { printf("创建失败\n"); exit(-1); } p->date = x; p->next = NULL; return p; }

讲解：

在此基础上，我们来实现下该函数：

void QueuePush(Queue* h, type x) { assert(h); QueueNode* p = Creat(x); if (h->phead == NULL) { h->phead = h->ptail = p; } else { h->ptail->next = p; h->ptail = h->ptail->next; } }

代码讲解：

注：队列为空时（h->phead == NULL）：
头指针（phead）和尾指针（ptail）必须同时指向新节点 p，否则后续操作会出现指针混乱（如尾指针仍为 NULL）。队列非空时（核心修正点）：h->ptail->next = p：通过尾节点的 next 指针连接新节点，确保新节点插入队尾（而非队头）。h->ptail = h->ptail->next：等价于 h->ptail = p（因 ptail->next 已指向 p），目的是更新尾指针到新节点，保持 ptail 始终指向队尾。

  3.队列判空

• 队列判空的本质是判断队列中是否存在有效元素，我们可以根据队列结构配合头指针和尾指针 来判断，也可以直接根据头指针的值内容来判断。

函数为：

bool QueueEmpty(Queue* h)

代码：

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

讲解：

这样判断就好，省去了写if else 的代码。

 4.出队列

内容为：从链式队列 h 的队头删除节点，并释放其内存。

可近似看做链表的头删。

函数为：

void QueuePop(Queue* h)

图例：

代码：

void QueuePop(Queue* h) { if (QueueEmpty(h)) { return; } if (h->phead == h->ptail) { free(h->phead); h->phead = h->ptail = NULL; } else { QueueNode* p = h->phead->next; free(h->phead); h->phead = p; } }

讲解：

1.函数定义与入参void：无返回值（出队操作通常不返回元素）。Queue* h：传入队列的指针，来进行操作。

2. 空队列检查QueueEmpty(h)：调用队列判空函数。作用：若队列为空，直接返回，避免后续操作引发空指针异常（如访问h->phead->next）。

3. 单节点队列的出队处理判断条件：h->phead == h->ptail → 队列只有1个节点（头、尾指针指向同一节点）。操作逻辑：free(h->phead)：释放唯一的节点内存（避免内存泄漏）。h->phead = h->ptail = NULL：将头、尾指针置空，标记队列为空。

4. 多节点队列的出队处理判断条件：队列有≥2个节点（头、尾指针不重合）。操作逻辑：QueueNode* p = h->phead->next：临时保存原队首节点的下一个节点（避免释放头节点后丢失后续节点的引用）。free(h->phead)：释放原队首节点的内存。h->phead = p：将头指针指向新的队首节点（即原队首的下一个节点）。

 5.取队首数据

• 目标：获取队列第一个元素的值，不改变队列结构。
• 记住：操作前需先判断队列是否为空，避免“空指针”或“越界访问”错误发生。

函数为：

type QueueHead(Queue* h);

代码：

type QueueHead(Queue* h) { if (!QueueEmpty(h)) { return h->phead->date; } }

讲解：

先判断队列是否为空，非空时返回队首节点的数据，函数功能简单易懂，不过多解释。

 6.队列取队尾数据

• 目标：取队尾数据的核心是直接访问队列的尾节点，且需确保队列非空

函数为：

type QueueTail(Queue* h)

代码：

type QueueTail(Queue* h) { if (!QueueEmpty(h)) { return h->ptail->date; } }

讲解：

先判断队列是否为空，非空时返回队尾节点的数据，函数功能简单易懂，所以也不过多解释。

7.队列值打印

• 目标：遍历队列的所有节点，依次输出每个节点的数据值。
• 注：需确保队列非空，且遍历过程不破坏队列结构。

函数为：

void QueuePrint(Queue* h);

代码：

void QueuePrint(Queue* h) { if (QueueEmpty(h)) { return; } QueueNode* q = h->phead; while (q) { printf("%d ", q->date); q = q->next; } printf("\n"); }

讲解：

该函数用于打印链式队列中的所有元素，遍历顺序从队首到队尾，输出每个节点的数据值。调用QueueEmpty(h)检查队列是否为空（通常判断h->phead == NULL），若为空则直接返回，避免无效遍历。q指向队列的头节点，作为遍历的起始点（队首是第一个入队的元素）。循环中依次打印每个节点的date值，直到q为空（遍历至队尾）。

换行收尾：

printf("\n"); 

遍历打印节点：

while (q) { // q不为空时继续循环 printf("%d ", q->date); // 输出当前节点的数据 q = q->next; // q移动到下一个节点 } 

初始化遍历指针：

QueueNode* q = h->phead; 

空队列判断：

if (QueueEmpty(h)) { return; } 

 8.队列的销毁

• 目标：释放队列占用的所有内存（包括队列结构体本身、节点存储空间），避免内存泄漏。

函数为：

void QueueDestory(Queue* h)

代码：

void QueueDestory(Queue* h) { if (QueueEmpty(h)) { return; } QueueNode* q = h->phead; while (q) { QueueNode* p = q; q = q->next; free(p); } h->phead = h->ptail = NULL; }

讲解：

销毁链式队列，核心逻辑是遍历释放所有节点，再重置队列的头/尾指针，避免内存泄漏。空队列判断：if (QueueEmpty(h)) return;调用QueueEmpty(h)检查队列是否为空，若为空则直接返回（无需销毁操作）。初始化遍历指针：QueueNode* q = h->phead;q指向队列的头节点，作为遍历的起始点。每次循环先保存当前节点，再移动指针，最后释放节点，避免“释放后无法访问下一个节点”的问题。重置队列状态：h->phead = h->ptail = NULL;将队列的头指针phead和尾指针ptail置空，标记队列已销毁。

综上，队列代码讲解完成。

三、队列代码测试

队列代码，我是通过创建多文件来实现的：

1.h

#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int type; typedef struct QueueNode { type date; struct QueueNode* next; }QueueNode; typedef struct Queue { struct QueueNode* phead; struct QueueNode* ptail; }Queue; void QueueInit(Queue* h); void QueuePush(Queue* h, type x); QueueNode* Creat(type x); bool QueueEmpty(Queue* h); void QueuePop(Queue* h); type QueueHead(Queue* h); void QueueDestory(Queue* h); void QueuePrint(Queue* h); 

1.c

#include"1.h" void QueueInit(Queue* h) { assert(h); h->phead = h->ptail = NULL; } QueueNode* Creat(type x) { QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode)); if (p == NULL) { printf("创建失败\n"); exit(-1); } p->date = x; p->next = NULL; return p; } void QueuePush(Queue* h, type x) { assert(h); QueueNode* p = Creat(x); if (h->phead == NULL) { h->phead = h->ptail = p; } else { h->ptail->next = p; h->ptail = h->ptail->next; } } bool QueueEmpty(Queue* h) { assert(h); return h->phead == NULL; } void QueuePop(Queue* h) { if (QueueEmpty(h)) { return; } if (h->phead == h->ptail) { free(h->phead); h->phead = h->ptail = NULL; } else { QueueNode* p = h->phead->next; free(h->phead); h->phead = p; } } type QueueHead(Queue* h) { if (!QueueEmpty(h)) { return h->phead->date; } } type QueueTail(Queue* h) { if (!QueueEmpty(h)) { return h->ptail->date; } } void QueueDestory(Queue* h) { if (QueueEmpty(h)) { return; } QueueNode* q = h->phead; while (q) { QueueNode* p = q; q = q->next; free(p); } h->phead = h->ptail = NULL; } void QueuePrint(Queue* h) { if (QueueEmpty(h)) { return; } QueueNode* q = h->phead; while (q) { printf("%d ", q->date); q = q->next; } printf("\n"); }

测试函数：main.cpp

#include"1.h" void test() { Queue h; QueueInit(&h); QueuePush(&h, 100); QueuePrint(&h); //100 QueuePush(&h, 10); QueuePrint(&h); //100 10 QueuePush(&h, 0); QueuePush(&h, 20); //100 10 0 20 QueuePrint(&h); QueuePop(&h); QueuePrint(&h); //10 0 20 printf("%d ",QueueHead(&h)); printf("%d ", QueueTail(&h)); QueueDestory(&h); } int main() { test(); }

结果：

  总结

  以上就是今天要讲的内容，本篇文章涉及的知识点为：讲解队列的概念和结构，队列的实现知识的相关内容的相关内容，为本章节知识的内容，希望大家能喜欢我的文章，谢谢各位，因为没有找到合适的队列题，深感抱歉，我会在以后的文章里补上。