队列入门基础详解

文章目录

• • 一、什么是队列❓
  • 二、队列的核心术语与必备操作🔯
  • • 核心术语表📖
    • 队列的必备基础操作⚔️
  • 三、⚓队列的第一种实现：循环队列
  • • 3.1 循环队列的核心原理⚙️
    • 3.2 循环队列的核心设计🪛
    • 3.3 核心函数实现🚀
    • • 1. 初始化队列
      • 2. 判空&判满
      • 3. 入队（队尾添加元素）& 出队（队头删除元素）
      • 4. 获取队头元素
      • 5. 计算当前队列有效元素个数
      • 6. 清空队列 & 销毁队列
      • 7. 动态扩容队列
  • 四、⚓队列的第二种实现：链式队列
  • • 4.1 链式队列的核心原理⚙️
    • 4.2 链式队列的核心设计（带头节点）🪛
    • 4.3 核心函数实现🚀
    • • 1. 初始化队列
      • 2. 入队（队尾添加元素）& 出队（队头删除元素）
      • 3. 获取队头元素
      • 4. 清空队列 & 销毁队列
      • 5. 遍历打印队列所有元素
  • 五、循环队列vs链式队列⚖️
  • 六、完整测试示例📌
  • 七、🏁结尾

一、什么是队列❓

1. 定义：

队列是一种操作受限的线性表，核心规则是先进先出（FIFO,First in First Out）：

• 仅允许在队尾（Rear） 执行插入操作（入队）
• 仅允许在队头（Front） 执行删除操作（出队）
• 不允许在中间插入/删除，严格遵循“先进先出”

2. 生活类比：

• 排队打饭：先排队的人先打饭，后来的人只能排在队尾，不能插队
• 银行叫号：先取号的先办理业务

3. 队列与栈的核心区别

4. 队列的两种实现方式：

• 顺序存储： 循环队列（解决普通顺序队列的“假溢出”问题）
• 链式存储： 链式队列（无容量限制，动态扩容）

二、队列的核心术语与必备操作🔯

核心术语表📖

队列的必备基础操作⚔️

• 初始化（__init__）：定义存储元素的列表和最大容量（支持有界 / 无界队列），是所有操作的基础。
• 入队（enqueue）：先判断队列是否已满，再将元素添加到队尾（列表append），避免 “超容添加”。
• 出队（dequeue）：先判断队列是否为空，再移除并返回队头元素（列表pop(0)），避免 “空队列删除”。
• 查看队头（peek）：仅返回队头元素，不移除，适合 “只看不取” 的场景（比如查看排队第一个人的信息）。
• 判空 / 判满（is_empty/is_full）：队列操作的 “前置检查”，避免异常操作，是健壮性的核心。
• 获取大小（size）：返回当前元素数量，用于了解队列状态（比如统计排队人数）。

三、⚓队列的第一种实现：循环队列

为什么不用普通顺序队列？

• 普通顺序队列用数组存储，入队时rear++，出队时front++，但会出现”假溢出“：数组前面空着一大片，但因为rear到了数组末尾，没法再入队。

• 循环队列的思路：把数组“首尾相连”，用取模运算实现指针的循环移动，同时牺牲1个数组单元区分“空”和“满”，彻底解决“假溢出”。

3.1 循环队列的核心原理⚙️

取模运算%的核心作用🎯 取模运算是实现循环的关键： 当front或rear走到数组最后一个下标时，再往后走就需要自动回到数组开头（下标0），使用(指针 + 1) % 数组总长度，就可以实现首尾循环，不用使用if判断，简洁高效

3.2 循环队列的核心设计🪛

先定义队列的结构体和错误码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// 错误码定义，便于调试
#define QUEUE_OK 0 // 操作成功
#define QUEUE_ERR_NULL_PTR –1 // 空指针错误
#define QUEUE_ERR_FULL –2 // 队列已满
#define QUEUE_ERR_EMPTY –3 // 队列为空
#define QUEUE_ERR_MALLOC –4 // 内存分配失败
#define QUEUE_ERR_INVALID_PARAM –5 // 无效参数

// 队列元素类型，可按需修改（如char、结构体、指针）
typedef int ElemType;

// 循环队列结构体
typedef struct {
ElemType* data; // 动态数组，存储队列元素
int front; // 队头下标（指向队头元素）
int rear; // 队尾下标（指向队尾元素的下一个位置）
int maxSize; // 数组总大小（= 可用容量+1，牺牲1个单元）
} CircularQueue;

关键设计说明📝

• maxSize = 可用容量 + 1：比如要存 5 个元素，数组要开 6 个空间，牺牲 1 个单元区分空 / 满；
• front：永远指向队头元素；
• rear：永远指向队尾元素的下一个空闲位置。

3.3 核心函数实现🚀

1. 初始化队列

//usableCapacity 实际需要的最大存储元素个数（不用自己-1）
CircularQueue* CircularQueue_Init(int usableCapacity) {
// 1. 校验入参：容量必须大于0
if (usableCapacity <= 0) {
printf("初始化失败,队列容量必须大于0\\n");
return NULL;
}

// 2. 分配队列结构体内存
CircularQueue* queue = (CircularQueue*)malloc(sizeof(CircularQueue));
if (queue == NULL) {
printf("结构体内存分配失败\\n");
return NULL;
}

// 3. 分配数据数组（多开1个空间，解决空/满判断）
queue->maxSize = usableCapacity + 1;
queue->data = (ElemType*)malloc(queue->maxSize * sizeof(ElemType));
if (queue->data == NULL) {
printf("数据数组内存分配失败\\n");
free(queue); // 防止内存泄漏
return NULL;
}

// 4. 初始化队头/队尾指针（空队列时front=rear=0）
queue->front = 0;
queue->rear = 0;
printf("循环队列初始化成功，实际可存储元素个数：%d\\n", usableCapacity);
return queue;
}

2. 判空&判满

// 判断队列是否为空
bool CircularQueue_IsEmpty(CircularQueue* queue) {
if (queue == NULL) return true;
// 空队列核心条件：front和rear重合
return queue->front == queue->rear;
}

// 判断队列是否为满
bool CircularQueue_IsFull(CircularQueue* queue) {
if (queue == NULL) return false;
// 满队列核心条件：rear的下一个位置是front（只剩1个牺牲单元）
return (queue->rear + 1) % queue->maxSize == queue->front;
}

敲黑板💥 判满的取模运算(rear+1)%maxSize是循环的关键：比如 maxSize=6，rear=5 时，(5+1)%6=0，刚好指向 front=0，说明队列满了。

3. 入队（队尾添加元素）& 出队（队头删除元素）

//入队（队尾添加元素）
int CircularQueue_Enqueue(CircularQueue* queue, ElemType elem) {
if (queue == NULL) {
printf("入队失败，队列指针不能为空\\n");
return QUEUE_ERR_NULL_PTR;
}

if (CircularQueue_IsFull(queue)) { // 防止数组越界
printf("队列已满，无法入队\\n");
return QUEUE_ERR_FULL;
}

// 核心操作：元素存入rear指向的空闲位置
queue->data[queue->rear] = elem;
// 队尾指针循环后移，取模实现循环
queue->rear = (queue->rear + 1) % queue->maxSize;
printf("元素%d入队完成\\n", elem);
return QUEUE_OK;
}

//出队（队头删除元素）
//pOutElem 出参：用于接收出队元素的指针，不需要返回值时可传NULL
int CircularQueue_Dequeue(CircularQueue* queue, ElemType* pOutElem) {
if (queue == NULL) {
printf("出队失败，队列指针不能为空\\n");
return QUEUE_ERR_NULL_PTR;
}

if (CircularQueue_IsEmpty(queue)) {
printf("队列为空，无元素可出队\\n");
return QUEUE_ERR_EMPTY;
}

// 核心操作：取出front指向的队头元素
ElemType frontElem = queue->data[queue->front];
// 若用户传了接收指针，就把元素值返回
if (pOutElem != NULL) {
*pOutElem = frontElem;
}
// 队头指针循环后移，取模实现循环，完成出队
queue->front = (queue->front + 1) % queue->maxSize;
printf("元素%d出队完成\\n", frontElem);
return QUEUE_OK;
}

4. 获取队头元素

int CircularQueue_GetFront(CircularQueue* queue, ElemType* pOutElem) {
if (queue == NULL|| pOutElem == NULL) {
printf("参数不能为空\\n");
return QUEUE_ERR_NULL_PTR;
}

if (CircularQueue_IsEmpty(queue)) {
printf("队列为空\\n");
return QUEUE_ERR_EMPTY;
}

//直接读取front指向的队头元素
*pOutElem = queue->data[queue->front];
return QUEUE_OK;
}

5. 计算当前队列有效元素个数

int CircularQueue_GetLength(CircularQueue* queue) {
if (queue == NULL) {
printf("获取失败，队列指针不能为空\\n");
return QUEUE_ERR_NULL_PTR;
}

//长度核心计算公式
//加上maxSize是为了避免 rear < front时，结果为负数
return (queue->rear – queue->front + queue->maxSize) % queue->maxSize;
}

6. 清空队列 & 销毁队列

//清空队列
int CircularQueue_Clear(CircularQueue* queue) {
if (queue == NULL) {
printf("队列指针不能为空\\n");
return QUEUE_ERR_NULL_PTR;
}

//清空队列只需要重置 front 和 rear，无需逐个清空元素
//因为队列的有效元素只由front和rear界定，新入队会自动覆盖旧数据
queue->front = 0;
queue->rear = 0;
return QUEUE_OK;
}

//销毁队列
int CircularQueue_Destroy(CircularQueue** pQueue) {
// 二级指针：修改外部的队列指针，避免野指针
if (pQueue == NULL || *pQueue == NULL) {
printf("销毁失败，队列指针不能为空\\n");
return QUEUE_ERR_NULL_PTR;
}

CircularQueue* queue = *pQueue;
// 先释放数组，再释放结构体（顺序不能反）
//如果先释放结构体，就找不到数据数组的地址了，会导致内存泄露
if (queue->data != NULL) {
free(queue->data);
queue->data = NULL;
}
free(queue);
// 核心：把外部指针置空
//一级指针无法修改外部原指针的值，必须使用二级指针
*pQueue = NULL;
printf("队列销毁完成\\n");
return QUEUE_OK;
}

7. 动态扩容队列

//newUsableCapacity 新的实际可用容量
int CircularQueue_Resize(CircularQueue* queue, int newUsableCapacity) {
if (queue == NULL) {
printf("扩容失败，队列指针不能为空\\n");
return QUEUE_ERR_NULL_PTR;
}

if (newUsableCapacity <= 0) {
printf("扩容失败，容量必须大于0\\n");
return QUEUE_ERR_INVALID_PARAM;
}

//校验新容量不能小于当前已有元素个数，否则会丢失数据
int currentLen = CircularQueue_GetLength(queue);
if (newUsableCapacity < currentLen) {
printf("扩容失败，新容量小于当前元素个数\\n");
return QUEUE_ERR_INVALID_PARAM;
}

//1.分配新的数组内存
int newMaxSize = newUsableCapacity + 1;
ElemType* newData = (ElemType*)malloc(newMaxSize * sizeof(ElemType));
if (newData == NULL) {
printf("新数组内存分配失败\\n");
return QUEUE_ERR_MALLLOC;
}

//2.按顺序复制原队列的有效元素到新数组（从下标0开始存，消除循环）
for (int i = 0; i < currentLen; i++) {
newData[i] = queue->data[(queue->front + i) % queue->maxSize];
}

//3.释放旧数组，更新队列的核心成员
free(queue->data);
queue->data = newData;
queue->front = 0; //新数组队头从0开始
queue->rear = currentLen; //队尾在最后一个元素的下一个位置
queue->maxSize = newMaxSize;
printf("队列扩容完成，新的实际可存容量：%d\\n", newUsableCapacity);
return QUEUE_OK;
}

四、⚓队列的第二种实现：链式队列

循环队列的缺点是容量固定，若提前不知道队列大小，就需要链式队列 —— 用链表实现，每个节点动态分配，无容量限制，也没有假溢出问题。

4.1 链式队列的核心原理⚙️

4.2 链式队列的核心设计（带头节点）🪛

为什么要带头节点？ 统一空队列和非空队列的操作逻辑，避免边界处理的麻烦（比如空队列时rear不用单独判断）。

//链式队列节点结构体
typedef struct QueueNode {
ElemType data; //节点存储的有效数据
struct QueueNode* next; //指向下一个节点的指针
}QueueNode;

//链式队列结构体（带头节点）
typedef struct {
QueueNode* front; //队头指针，永远指向头节点，不存有效数据
QueueNode* rear; //队尾指针，永远指向队尾的有效数据节点
int length; //队列当前元素个数，O(1)获取长度，无需遍历
}LinkQueue;

关键设计说明📝

• 头节点：不存有效数据，front永远指向它
• 空队列时：rear也指向头节点
• length：记录元素个数，避免每次遍历链表统计

4.3 核心函数实现🚀

1. 初始化队列

LinkQueue* LinkQueue_Init(void) {
//1.分配队列结构体内存
LinkQueue* queue = (LinkQueue*)malloc(sizeof(LinkQueue));
if (queue == NULL) {
printf("队列结构体内存分配失败\\n");
return NULL;
}

//2.创建头节点（核心：统一空/非空队列的操作逻辑）
QueueNode* headNode = (QueueNode*)malloc(sizeof(QueueNode));
if (headNode == NULL) {
printf("头节点内存分配失败\\n");
free(queue); //分配失败，释放已申请的队列结构体，防止内存泄露
return NULL;
}
headNode->next = NULL; //头节点初始next为空，代表队列无有效元素
//3.初始化队列核心成员
queue->front = headNode; //front永远指向头节点，永不改变
queue->rear = headNode; //空队列时，rear和front都指向头节点
queue->length = 0;
printf("链表队列初始化完成\\n");
return queue;
}

2. 入队（队尾添加元素）& 出队（队头删除元素）

//入队（队尾添加元素）
int LinkQueue_Enqueue(LinkQueue* queue, ElemType elem) {
if (queue == NULL) {
printf("入队失败，队列指针不能为空\\n");
return QUEUE_ERR_NULL_PTR;
}

// 1. 创建新节点
QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
if (newNode == NULL) {
printf("新节点内存分配失败\\n");
return QUEUE_ERR_MALLOC;
}
newNode->data = elem;
newNode->next = NULL; // 队尾节点next为NULL

// 2. 核心操作：新节点挂到队尾
queue->rear->next = newNode;
// 3. 队尾指针后移
queue->rear = newNode;
// 4. 长度+1
queue->length++;
printf("元素%d入队完成\\n", elem);
return QUEUE_OK;
}

//出队（队头删除元素）
//pOutElem 出参，存储出队元素（不需要元素值可传NULL）
int LinkQueue_Dequeue(LinkQueue* queue, ElemType* pOutElem) {
if (queue == NULL) {
printf("出队失败，队列不能为空\\n");
return QUEUE_ERR_NULL_PTR;
}

if (queue->length == 0) { // 空队列
printf("队列为空，无元素可出队\\n");
return QUEUE_ERR_EMPTY;
}

// 1. 找到待删除的队头节点（头节点的下一个节点）
QueueNode* delNode = queue->front->next;
ElemType outElem = delNode->data;

// 2. 给用户返回出队元素
if (pOutElem != NULL) {
*pOutElem = outElem;
}

// 3. 核心操作：摘除待删除节点
queue->front->next = delNode->next;
// 4. 边界处理：若删除的是最后一个节点，重置rear到表头
if (queue->rear == delNode) {
queue->rear = queue->front;
}

// 5. 释放节点内存
free(delNode);
delNode = NULL;
queue->length—;
printf("元素%d出队完成\\n", outElem);
return QUEUE_OK;
}

3. 获取队头元素

//pOutElem 出参，存储队头元素（不可为NULL）
int LinkQueue_GetFront(LinkQueue* queue, ElemType* pOutElem) {
if (queue == NULL || pOutElem == NULL) {
printf("获取队头失败，队列指针或接收指针不能为空\\n");
return QUEUE_ERR_NULL_PTR;
}

if (LinkQueue_IsEmpty(queue)) {
printf("队列为空\\n");
return QUEUE_ERR_EMPTY;
}

//队头有效元素是头节点的下一个节点的数据
*pOutElem = queue->front->next->data;
return QUEUE_OK;
}

4. 清空队列 & 销毁队列

//清空队列
int LinkQueue_Clear(LinkQueue* queue) {
if (queue == NULL) {
printf("清空失败，队列指针不能为空\\n");
return QUEUE_ERR_NULL_PTR;
}

//遍历释放所有有效元素节点
QueueNode* currNode = queue->front->next;
while (currNode != NULL) {
QueueNode* nextNode = currNode->next; //先保存下一个节点，释放后就找不到了
free(currNode);
currNode= nextNode;
}
//重复队列状态，恢复空队列
queue->front->next = NULL;
queue->rear = queue->front;
queue->length = 0;
printf("队列清空完成\\n");
return QUEUE_OK;
}

//销毁队列
//pQueue 传入队列指针的地址（二级指针，用于置空外部指针，避免野指针）
int LinkQueue_Destroy(LinkQueue** pQueue) {
if (pQueue == NULL || *pQueue == NULL) {
printf("销毁失败，队列指针不能为空\\n");
return QUEUE_ERR_NULL_PTR;
}

LinkQueue* queue = *pQueue;
// 1. 清空所有有效节点
QueueNode* currNode = queue->front->next;
while (currNode != NULL) {
QueueNode* nextNode = currNode->next;
free(currNode);
currNode = nextNode;
}

// 2. 释放头节点
free(queue->front);
// 3. 释放队列结构体
free(queue);
// 4. 置空外部指针，避免野指针
*pQueue = NULL;
printf("链式队列已销毁，内存全部释放\\n");
return QUEUE_OK;
}

5. 遍历打印队列所有元素

void LinkQueue_Print(LinkQueue* queue) {
if (queue == NULL || LinkQueue_IsEmpty(queue)) {
printf("队列为空或指针无效，无元素可打印\\n");
return;
}

QueueNode* currNode = queue->front->next;
while (currNode != NULL) {
printf("%d ", currNode->data);
currNode = currNode->next;
}
}

五、循环队列vs链式队列⚖️

六、完整测试示例📌

void Test_CircularQueue() {
// 1. 初始化（可存5个元素）
CircularQueue* queue = CircularQueue_Init(5);

// 2. 入队
for (int i = 1; i <= 5; i++) {
CircularQueue_Enqueue(queue, i);
}
CircularQueue_Enqueue(queue, 6); // 测试队列满

// 3. 出队
ElemType elem;
CircularQueue_Dequeue(queue, &elem);

// 4. 获取长度
printf("当前队列长度：%d\\n", CircularQueue_GetLength(queue));

// 5. 扩容
CircularQueue_Resize(queue, 8);

// 6. 销毁
CircularQueue_Destroy(&queue);
}

void Test_LinkQueue() {
// 1. 初始化
LinkQueue* queue = LinkQueue_Init();

// 2. 入队
LinkQueue_Enqueue(queue, 10);
LinkQueue_Enqueue(queue, 20);
LinkQueue_Enqueue(queue, 30);

// 3. 打印队列
printf("队列元素：");
LinkQueue_Print(queue);
printf("\\n");

// 4. 出队
ElemType elem;
LinkQueue_Dequeue(queue, &elem);

// 5. 清空队列
LinkQueue_Clear(queue);

// 6. 销毁
LinkQueue_Destroy(&queue);
}

int main() {
printf("===== 测试循环队列 =====\\n");
Test_CircularQueue();

printf("\\n===== 测试链式队列 =====\\n");
Test_LinkQueue();

return 0;
}

七、🏁结尾

核心要点：

• 队列的本质是 “先进先出”，操作仅限队尾入、队头出；
• 循环队列用数组 + 取模实现，牺牲 1 个单元区分空 / 满；
• 链式队列用链表实现，带头节点简化边界处理；
• 销毁队列时必须释放所有内存，避免泄漏（尤其链式队列要遍历释放节点）。

以上就是本次内容的全部分享，感谢你在茫茫人海中点开这篇文章，如果觉得这篇博客对你有帮助，欢迎点赞👍→收藏🔖→关注👀，后续我会继续更新二叉树、AVL树等数据结构的详细讲解……