《数据结构初阶》【顺序栈 + 链式队列 + 循环队列】

技术文档

《数据结构初阶》【顺序栈 + 链式队列 + 循环队列】

前言：
- 什么是栈？
- 栈有哪些实现方式？我们要选择哪种实现方式？
- --------------------------------
- 什么是队列？
- 队列有哪些实现方式？我们要选择哪种实现方式？
- --------------------------------
- 什么是循环队列？
- 循环队列有哪些实现方式？我们要选择哪种实现方式？
----------------顺序栈----------------
栈的动态数组实现
- 顺序栈初始化时该如何初始化top？
- 头文件
- 实现文件
- 测试文件
- 运行结果
栈的oj练习
- [20. 有效的括号](https://leetcode.cn/problems/valid-parentheses/)
- - 题目介绍
  - 方法一：
- [232. 用栈实现队列](https://leetcode.cn/problems/implement-queue-using-stacks/)
- 题目介绍
- 方法一：
----------------链式队列----------------
队列的链表实现
- 头文件
- 实现文件
- 测试文件
- 运行结果
队列的oj练习
- [225. 用队列实现栈](https://leetcode.cn/problems/implement-stack-using-queues/)
- 题目介绍
- 方法一：
----------------循环队列----------------
循环队列的数组实现
- 循环队列要怎么进行判空or判满？
- 头文件
- 实现文件
- 测试文件
- 运行结果
循环队列的oj练习
- [622. 设计循环队列](https://leetcode.cn/problems/design-circular-queue/)
- 题目介绍
- 方法一：

在这里插入图片描述

往期《数据结构初阶》回顾：
【时间复杂度 + 空间复杂度】
【顺序表 + 单链表 + 双向链表】
【顺序表/链表精选15道OJ练习】

前言：

Hi~ o(￣▽￣)ブ小伙伴们今天是五一小长假的最后一天了，大家假期玩的开心吗？~~（🎮）~~

今天也是立夏哦~🌞，不知不觉夏天就要到了🍉

🚩我们也终于要学习新的数据结构——“栈 和 队列” 了，相信大家在此之前已经学习了《数据结构初阶》前面的内容并进行相应的练习了，接下来就让我们像夏天一样热情满满地开启新篇章吧！🔥

🎯 先来个剧透：

栈就像自动贩卖机的出货口 🥤 → 最后塞进去的饮料总是最先滚出来超不公平！

队列就像奶茶店排队🧋 → 先来的人总能先尝到甜蜜超公平！

循环队列就像旋转餐厅🍽️ → 餐盘转完一圈又能重新使用超省空间！

温馨提示：📢 博客内容总共1万两千多字，请耐心看完☕！！！

相信当你认真读完这篇博客后，一定会收获满满的知识和启发！✨

什么是栈？

栈：是一种只能在一端进行插入和删除操作的特殊线性表。

它按照后进先出（LIFO, Last In First Out） 的原则存储数据。

栈的操作只允许在 一端（称为栈顶） 进行，另一端称为 栈底，需要读数据的时候从栈顶开始弹出数据。

先进入的数据被压入栈底，最后的数据在栈顶。

在这里插入图片描述

栈有哪些实现方式？我们要选择哪种实现方式？

栈的实现一般可以使用数组或者链表实现，这两种栈分别被称为：

顺序栈（Array Stack）：基于数组实现，使用连续的内存空间存储栈元素。

链式栈（Linked Stack）：基于链表实现，每个节点包含数据域和指向下一个节点的指针。

栈的实现方式选择上，没有绝对的最优，而是取决于具体应用场景的需求。

相对而言使用折中方案：动态数组栈的结构实现更优一些，并且大部分现代语言标准库的栈实现也是使用这种方式实现的。

在这里插入图片描述

typedef int STKDateType; //使用typedf重新定义栈中数据的类型，方便后续修改中的数据的类型typedef struct Stack{//1.记录栈的栈顶指针 ---> 一个int变量//2.记录栈的容量 ---> 一个int变量//3.动态数组 ---> 一个指针int top;int capacity;STKDateType* a;}STK;

--------------------------------

什么是队列？

队列：是一种只能在一端进行插入操作，在另一端进行删除操作的线性表。

它按照 先进先出（FIFO, First In First Out） 的原则存储和处理数据。

队列的操作在两端进行：队列中允许删除元素的一端是 队头，队列中允许插入元素的一端是 队尾

最早进入队列的元素位于队头，新元素总是插入到队尾，随着元素的插入，队尾位置会向后移动。

在这里插入图片描述

队列有哪些实现方式？我们要选择哪种实现方式？

注：由于队列本身的种类比较多，例如：循环队列、双端队列、优先队列……，我们这里只实现普通的队列。

和栈一样，普通队列的实现方式也可以使用数组或者链表实现，这两种队列分别被称为：

顺序队列（Array Queue）：基于数组实现，使用固定大小的数组存储队列元素。

链式队列（Linked Queue）：基于链表实现，每个节点包含数据域和指向下一个节点的指针。

这两种实现方式各有应用场景，但链式队列更优一些并且现代系统开发中，链式队列也更通用。

在这里插入图片描述

typedef int QDateType; //使用typedf重新定义队列中的变量的数据类型，方便后续进行修改//队列节点的结构体typedef struct QueueNode{//1.队列节点中存储的数据 ---> 一个int变量//2.队列节点中存储下一个节点的位置 ---> 一个指针QDateType val;struct QueueNode* next; }QNode;//队列的结构体（使用带头尾指针的结构）typedef struct Queue{//1.记录当前队列中元素的个数 ---> 一个int变量//2.指向头部的指针 ---> （用于：头删/取队头的元素）//3.指向尾部的指针 ---> （用于：尾插/取队尾的元素） int size;QNode* queHead;QNode* queTail;}Que;

--------------------------------

什么是循环队列？

循环队列（Circular Queue）：是将顺序队列的存储空间的最后一个位置绕到第一个位置，形成一个环形的结构。

通过环形缓冲区的方式解决普通顺序队列的\"假溢出\"问题，实现循环利用存储空间的目的。

其核心特点是将数组的首尾逻辑相连，使得当队列尾部到达数组末端时能够绕回到数组开头继续存储数据。

循环队列有哪些实现方式？我们要选择哪种实现方式？

从循环队列的定义中我们可以看出来循环队列是基于数组实现的队列，其实呢也可以使用链表来实现，但是较少使用。（有很多的缺陷）

综上：数组是循环队列的标准实现方式（90%的常见场景都是使用数组实现的）

在这里插入图片描述

typedef int CQDataType;typedef struct CircularQueue{//1.使用动态数组模拟实现循环队列 ---> 定义一个int*类型的指针//2.记录队列中队头元素的位置 ---> 定义一个int类型的变量//3.记录队列中队尾元素的位置 ---> 定义一个int类型的变量//4.记录队列中当前元素的数量 ---> 定义一个int类型的变量//5.记录队列的容量 ---> 定义一个int类型的变量CQDataType* a;int front;int rear;int size;int capacity;}CQ;

----------------顺序栈----------------

栈的动态数组实现

顺序栈初始化时该如何初始化top？

方案一：将top初始化为-1
方案二：将top初始化为0（推荐）

在这里插入图片描述

头文件

---------------------------------Stack.h---------------------------------#pragma once//任务1：定义头文件#include #include #include //任务2：定义栈的结构体typedef int STKDateType; //使用typedf重新定义栈中数据的类型，方便后续修改中的数据的类型typedef struct Stack{//1.记录栈的栈顶指针 ---> 一个int变量//2.记录栈的容量 ---> 一个int变量//3.动态数组 ---> 一个指针int top;int capacity;STKDateType* a;}STK;//任务3：定义栈要实现的接口//1.栈的初始化//2.栈的销毁//3.栈的入栈操作//4.栈的出栈操作//5.栈的取栈顶元素操作//6.栈的判空操作//7.栈的求栈中元素数量的操作void STKInit(STK* pstk);void STKDestroy(STK* pstk);void STKPush(STK* pstk,STKDateType x);void STKPop(STK* pstk);STKDateType STKTop(STK* pstk);bool STKEmpty(STK* pstk);int STKSize(STK* pstk);

实现文件

----------------------------------Stack.c--------------------------------- #include \"Stk.h\"//1.实现：“栈的初始化”的函数void STKInit(STK* pstk){assert(pstk); //确保指针非空pstk->top = 0;pstk->capacity = 0;pstk->a = NULL;}//2.实现：“栈的销毁”的函数void STKDestroy(STK* pstk){assert(pstk);pstk->top = 0;pstk->capacity = 0;free(pstk->a);pstk->a = NULL;}//3.实现：“栈的入栈操作”的函数void STKPush(STK* pstk,STKDateType x){//第一部分：确保指针非空assert(pstk);//第二部分：检查是否需要进行扩容if (pstk->top == pstk->capacity){//1.需要进行扩容 ---> 新容量是多少？int newCapacity = pstk->capacity == 0 ? 4 : pstk->capacity * 2;//2.开始进行扩容STKDateType* tmp = (STKDateType*)realloc(pstk->a, newCapacity * sizeof(STKDateType));//3.检查扩容是否成功if (tmp == NULL){perror(\"realloc false\");return;}//4.更新指向动态数组的指针pstk->a = tmp;//5.更新栈的容量pstk->capacity = newCapacity;}//第三部分：实现入栈操作pstk->a[pstk->top] = x;pstk->top++;}//4.实现：“栈的出栈操作”的函数void STKPop(STK* pstk){assert(pstk);//确保指针不为空assert(pstk->top > 0);//确保栈不为空pstk->top--;}//5.实现：“栈的取栈顶元素的操作”的函数STKDateType STKTop(STK* pstk){assert(pstk);assert(pstk->top > 0);return pstk->a[pstk->top-1]; // 注意：千万别写成这个样子pstk->a[pstk->top--];，这样会先会修改top值}//6.实现：“栈的判空操作”的函数bool STKEmpty(STK* pstk){assert(pstk);//if (pstk->top = 0) return true;//else return false;//1.栈为空 --> 返回true//2.栈不为空 ---> 返回falsereturn pstk->top == 0; }//7.实现：“栈的求栈中元素数量的操作”的函数int STKSize(STK* pstk){assert(pstk);return pstk->top;}

测试文件

-------------------------------Test.c--------------------------------#include \"Stack.h\"void TestStack() { STK stack; STKInit(&stack); printf(\"===== 栈测试开始 =====\\n\\n\"); /*--------------------“入栈测试”--------------------*/ printf(\"--- 测试1: 入栈测试 ---\\n\"); printf(\"入栈 1, 2, 3, 4\\n\"); STKPush(&stack, 1); STKPush(&stack, 2); STKPush(&stack, 3); STKPush(&stack, 4); printf(\"栈大小: %d, 栈顶元素: %d\\n\", STKSize(&stack), STKTop(&stack)); printf(\"\\n\"); /*--------------------“扩容测试”--------------------*/ printf(\"--- 测试2: 扩容测试 ---\\n\"); printf(\"当前容量: %d\\n\", stack.capacity); printf(\"入栈 5 触发扩容\\n\"); STKPush(&stack, 5); printf(\"扩容后容量: %d\\n\", stack.capacity); printf(\"栈大小: %d, 栈顶元素: %d\\n\", STKSize(&stack), STKTop(&stack)); printf(\"\\n\"); /*--------------------“出栈测试”--------------------*/ printf(\"--- 测试3: 出栈测试 ---\\n\"); printf(\"出栈前栈顶: %d\\n\", STKTop(&stack)); STKPop(&stack); printf(\"出栈后栈顶: %d\\n\", STKTop(&stack)); printf(\"栈大小: %d\\n\", STKSize(&stack)); printf(\"\\n\"); /*--------------------“取栈顶元素测试”--------------------*/ printf(\"--- 测试4: 取栈顶元素测试 ---\\n\"); printf(\"当前栈顶: %d\\n\", STKTop(&stack)); STKPush(&stack, 6); printf(\"入栈6后栈顶: %d\\n\", STKTop(&stack)); printf(\"\\n\"); /*--------------------“栈空测试”--------------------*/ printf(\"--- 测试5: 栈空测试 ---\\n\"); printf(\"连续出栈直到栈空...\\n\"); while (!STKEmpty(&stack)) { printf(\"出栈: %d, 剩余大小: %d\\n\", STKTop(&stack), STKSize(&stack) - 1); STKPop(&stack); } printf(\"栈是否为空? %s\\n\", STKEmpty(&stack) ? \"是\" : \"否\"); printf(\"\\n\"); /*--------------------“销毁测试”--------------------*/ printf(\"--- 测试6: 销毁测试 ---\\n\"); STKDestroy(&stack); printf(\"栈已销毁\\n\"); printf(\"销毁后访问指针: %p\\n\", (void*)stack.a); printf(\"\\n\"); printf(\"===== 栈测试结束 =====\\n\");}int main() { TestStack(); return 0;}

运行结果

在这里插入图片描述

栈的oj练习

20. 有效的括号

题目介绍

在这里插入图片描述

方法一：

//任务2：定义栈的结构体typedef char STKDateType; //使用typedf重新定义栈中数据的类型，方便后续修改中的数据的类型typedef struct Stack{//1.记录栈的栈顶指针 ---> 一个int变量//2.记录栈的容量 ---> 一个int变量//3.动态数组 ---> 一个指针int top;int capacity;STKDateType* a;}STK;//任务3：定义栈要实现的接口//1.栈的初始化//2.栈的销毁//3.栈的入栈操作//4.栈的出栈操作//5.栈的取栈顶元素操作//6.栈的判空操作//7.栈的求栈中元素数量的操作void STKInit(STK* pstk);void STKDestroy(STK* pstk);void STKPush(STK* pstk,STKDateType x);void STKPop(STK* pstk);STKDateType STKTop(STK* pstk);bool STKEmpty(STK* pstk);int STKSize(STK* pstk);//1.实现：“栈的初始化”的函数void STKInit(STK* pstk){assert(pstk); //确保指针非空pstk->top = 0;pstk->capacity = 0;pstk->a = NULL;}//2.实现：“栈的销毁”的函数void STKDestroy(STK* pstk){assert(pstk);pstk->top = 0;pstk->capacity = 0;free(pstk->a);pstk->a = NULL;}//3.实现：“栈的入栈操作”的函数void STKPush(STK* pstk,STKDateType x){//第一部分：确保指针非空assert(pstk);//第二部分：检查是否需要进行扩容if (pstk->top == pstk->capacity){//1.需要进行扩容 ---> 新容量是多少？int newCapacity = pstk->capacity == 0 ? 4 : pstk->capacity * 2;//2.开始进行扩容STKDateType* tmp = (STKDateType*)realloc(pstk->a, newCapacity * sizeof(STKDateType));//3.检查扩容是否成功if (tmp == NULL){perror(\"realloc false\");return;}//4.更新指向动态数组的指针pstk->a = tmp;//5.更新栈的容量pstk->capacity = newCapacity;}//第三部分：实现入栈操作pstk->a[pstk->top] = x;pstk->top++;}//4.实现：“栈的出栈操作”的函数void STKPop(STK* pstk){assert(pstk);//确保指针不为空assert(pstk->top > 0);//确保栈不为空pstk->top--;}//5.实现：“栈的取栈顶元素的操作”的函数STKDateType STKTop(STK* pstk){assert(pstk);assert(pstk->top > 0);return pstk->a[pstk->top-1]; // 注意：千万别写成这个样子pstk->a[pstk->top--];，这样会先会修改top值}//6.实现：“栈的判空操作”的函数bool STKEmpty(STK* pstk){assert(pstk);//if (pstk->top = 0) return true;//else return false;//1.栈为空 --> 返回true//2.栈不为空 ---> 返回falsereturn pstk->top == 0; }//7.实现：“栈的求栈中元素数量的操作”的函数int STKSize(STK* pstk){assert(pstk);return pstk->top;}//实现：解决这道题的函数isValidbool isValid(char* s) { //1.创建一个栈 STK stk; //2.初始化栈 STKInit(&stk); //处理数据: while(*s) //遍历整个字符串的方法 { //3.如果碰到是左括号就将左括号入栈 if(*s==\'(\'||*s==\'[\'||*s==\'{\') STKPush(&stk,*s); //4.如果碰到是右括号:1)判断栈是否为空 2)判断右括号是否和栈顶的元素匹配 if(*s==\')\'||*s==\']\'||*s==\'}\') { //1)如果栈为空 --> 也就是说字符串的前面并没有和它匹配的左括号 if(STKEmpty(&stk)) { STKDestroy(&stk); return false; } //2)判断右括号是否和栈顶有的元素匹配 --> 先判断不匹配时，再判断匹配时 char top=STKTop(&stk); if(*s==\')\'&&top!=\'(\'||*s==\']\'&&top!=\'[\'||*s==\'}\'&&top!=\'{\')//匹配失败 { STKDestroy(&stk); return false; } else//匹配成功 { STKPop(&stk); } } s++; } //5.判断栈是否为空 ---> 这才是判断字符串是不是有括号的标准（如果栈中最后还元素：说明这个字符中的左右括号数量是不匹配的） bool result=STKEmpty(&stk); //6.销毁栈 STKDestroy(&stk); return result;}

232. 用栈实现队列

题目介绍

在这里插入图片描述

方法一：

//任务1：定义头文件#include #include #include //任务2：定义栈的结构体typedef int STKDateType; //使用typedf重新定义栈中数据的类型，方便后续修改中的数据的类型typedef struct Stack{//1.记录栈的栈顶指针 ---> 一个int变量//2.记录栈的容量 ---> 一个int变量//3.动态数组 ---> 一个指针int top;int capacity;STKDateType* a;}STK;//任务3：定义栈要实现的接口//1.栈的初始化//2.栈的销毁//3.栈的入栈操作//4.栈的出栈操作//5.栈的取栈顶元素操作//6.栈的判空操作//7.栈的求栈中元素数量的操作void STKInit(STK* pstk);void STKDestroy(STK* pstk);void STKPush(STK* pstk,STKDateType x);void STKPop(STK* pstk);STKDateType STKTop(STK* pstk);bool STKEmpty(STK* pstk);int STKSize(STK* pstk);//1.实现：“栈的初始化”的函数void STKInit(STK* pstk){assert(pstk); //确保指针非空pstk->top = 0;pstk->capacity = 0;pstk->a = NULL;}//2.实现：“栈的销毁”的函数void STKDestroy(STK* pstk){assert(pstk);pstk->top = 0;pstk->capacity = 0;free(pstk->a);pstk->a = NULL;}//3.实现：“栈的入栈操作”的函数void STKPush(STK* pstk,STKDateType x){//第一部分：确保指针非空assert(pstk);//第二部分：检查是否需要进行扩容if (pstk->top == pstk->capacity){//1.需要进行扩容 ---> 新容量是多少？int newCapacity = pstk->capacity == 0 ? 4 : pstk->capacity * 2;//2.开始进行扩容STKDateType* tmp = (STKDateType*)realloc(pstk->a, newCapacity * sizeof(STKDateType));//3.检查扩容是否成功if (tmp == NULL){perror(\"realloc false\");return;}//4.更新指向动态数组的指针pstk->a = tmp;//5.更新栈的容量pstk->capacity = newCapacity;}//第三部分：实现入栈操作pstk->a[pstk->top] = x;pstk->top++;}//4.实现：“栈的出栈操作”的函数void STKPop(STK* pstk){assert(pstk);//确保指针不为空assert(pstk->top > 0);//确保栈不为空pstk->top--;}//5.实现：“栈的取栈顶元素的操作”的函数STKDateType STKTop(STK* pstk){assert(pstk);assert(pstk->top > 0);return pstk->a[pstk->top-1]; // 注意：千万别写成这个样子pstk->a[pstk->top--];，这样会先会修改top值}//6.实现：“栈的判空操作”的函数bool STKEmpty(STK* pstk){assert(pstk);//if (pstk->top = 0) return true;//else return false;//1.栈为空 --> 返回true//2.栈不为空 ---> 返回falsereturn pstk->top == 0; }//7.实现：“栈的求栈中元素数量的操作”的函数int STKSize(STK* pstk){assert(pstk);return pstk->top;}--------------------------------------------------------------------------------------typedef struct { //使用双栈实现队列 ---> 队列的结构体中的成员：两个栈 STK pushStk; STK popStk;} MyQueue;int myQueuePeek(MyQueue* pque);//myQueuePeek会先被myQueuePop函数使用，这里先声明一下MyQueue* myQueueCreate() { //实现：“队列的创建+初始化”操作 //1）创建操作 //1.分配队列的结构体的内存 MyQueue*pque=(MyQueue*)malloc(sizeof(MyQueue)); //2）初始化栈 STKInit(&pque->pushStk); STKInit(&pque->popStk); //3）返回队列的结构体指针 return pque;}void myQueuePush(MyQueue* pque, int x) { //实现：“队列的入队”操作 ---> 向pushStak栈中添加元素 STKPush(&pque->pushStk,x);}int myQueuePop(MyQueue* pque) { //实现：“队列的出队”操作  //1.如果popStk栈中没有元素,需要先从pushStk栈中导入元素 int front=myQueuePeek(pque); //2.弹出popStk栈中的栈顶的元素 STKPop(&pque->popStk); return front;}int myQueuePeek(MyQueue* pque) { //实现：“队列的取队头元素”操作 //1.如果popStk栈中没有元素,需要先从pushStk栈中导入元素 if(STKEmpty(&pque->popStk)) { //1.1:将栈pushStk栈中的元素添加到popStk栈中 while(!STKEmpty(&pque->pushStk)) { int top=STKTop(&pque->pushStk); STKPop(&pque->pushStk); STKPush(&pque->popStk,top); } } //2.取出popStk栈中的栈顶元素 int front=STKTop(&pque->popStk); //3.返回popStk栈的栈顶元素即可 return front;}bool myQueueEmpty(MyQueue* pque) { //实现：“队列的判空”操作 ---> 两个栈都为空的时候说明队列为空 return STKEmpty(&pque->pushStk)&&STKEmpty(&pque->popStk);}void myQueueFree(MyQueue* pque) { //实现：“队列的销毁”操作 //从内向外进行销毁 //1.先销毁两个栈 STKDestroy(&pque->popStk); STKDestroy(&pque->pushStk); //2.在销毁队列的结构体 free(pque);}

----------------链式队列----------------

队列的链表实现

头文件

--------------------------------Queue.h--------------------------------#pragma once//任务1：声明需要使用的头文件//任务2：定义队列的结构体//任务3：声明队列的接口函数//任务1：#include #include #include #include //任务2：typedef int QDateType; //使用typedf重新定义队列中的变量的数据类型，方便后续进行修改//队列节点的结构体typedef struct QueueNode{//1.队列节点中存储的数据 ---> 一个int变量//2.队列节点中存储下一个节点的位置 ---> 一个指针QDateType val;struct QueueNode* next; //注意这里next的类型可千万不要使用QNode哦，因为这时你还没有定义QNode，要先使用QueueNode进行代替 //（如果这是一个.c文件的话必须写成struct QueueNode，而如果这是一个.cpp文件的话写成QueueNode即可，因为在.cpp文件中这里你相当于定义的是“类”，而不是“结构体”） //总结：//C语言：struct QueueNode* next; 解释：struct 结构体名 =类型名 ---> 类型名* next :结构体指针 //C++：QueueNode* next; 解释：类名* next ---> 类指针}QNode;//队列的结构体（使用带头尾指针的结构）typedef struct Queue{//1.记录当前队列中元素的个数 ---> 一个int变量//2.指向头部的指针 ---> （用于：头删/取队头的元素）//3.指向尾部的指针 ---> （用于：尾插/取队尾的元素）int size;QNode* queHead;QNode* queTail;}Que;//任务3：//1.队列的初始化//2.队列的销毁//3.队列的入队//4.队列的出队//5.队列的取队头元素//6.队列的取队尾元素//7.队列的判空//8.队列的求队列中元素的数量void QueInit(Que* pque);void QueDestroy(Que* pque);void QuePush(Que* pque, QDateType x);void QuePop(Que* pque);QDateType QueFront(Que* pque);QDateType QueBack(Que* pque);bool QueEmpty(Que* pque);int QueSize(Que* pque);

实现文件

--------------------------------Queue.c--------------------------------#include \"Queue.h\"//1.实现：“队列的初始化”操作void QueInit(Que* pque){assert(pque);//1.将队列结构体中“元素的数量”置为0pque->size = 0;//2.将队列结构体中“指向队头/队尾的指针”置为空指针pque->queHead = NULL;pque->queTail = NULL;}//2.实现：“队列的销毁”操作void QueDestroy(Que* pque){assert(pque);//1.将队列结构体中“元素的数量”置为0pque->size = 0;//2.将队列中的所有的节点都释放掉//1）创建临时指针代替queHead进行遍历队列的节点QNode* tmp = pque->queHead;//2）使用tmp遍历所有的节点while (tmp != NULL){//3）创建后继指针存储当前遍历到的节点的下一位置QNode* next = tmp->next;//4)释放当前遍历到的节点free(tmp);//5)更新tmp指针tmp = next;}//将队列结构体中“指向队列头部/尾部的指针”置为空指针pque->queHead = NULL;pque->queTail = NULL;}//3.实现：“队列的入队”操作void QuePush(Que* pque, QDateType x){assert(pque);//思路：使用链表的尾插法实现入队的操作//1）先创建出来一个队列的节点QNode* newNode = (QNode*)malloc(sizeof(QNode));//1.1:判断新开辟的空间是否开辟成功哦if (newNode == NULL){perror(\"malloc fail\");return;}//2）为这个节点进行赋值newNode->val = x;//3）将这个节点链接到队列链表的后面//3.1：将新开辟的节点的next指针域置空newNode->next = NULL;//3.2：将新开辟的节点链接到队列链表的尾部//3.3.1：如果当前的队列链表中没有节点if (pque->queTail == NULL){pque->queHead = pque->queTail = newNode;}//3.3.2：如果当前的队列链表中有节点else{pque->queTail->next = newNode;pque->queTail = newNode;}//4）队列中的元素的数量增加pque->size++;}//4.实现：“队列的出队”操作void QuePop(Que* pque){assert(pque);assert(pque->size > 0);//注意：当我们：1.删除某个数据结构中的元素时 2.从某个数据结构中取出元素的时//---> 需要判断当前的数据结构中是否还有元素//思路：使用链表的头删法实现出队操作//1）如果当前队列中只有一个元素if (pque->queHead->next == NULL){//1.1：将这一个节点删除掉free(pque->queHead);//1.2：将指向队头和队尾的指针都置为空pque->queHead = NULL;pque->queTail = NULL;}//2）如果队列中的元素有多个else{//2.1：创建一个临时的指针来存放queHead指针的下一个位置QNode* next = pque->queHead->next;//2.2：释放掉queHead指针指向的节点free(pque->queHead);//2.3：将queHead指针移动到下一个节点的位置pque->queHead = next;}//3）队列中的元素的数量减少pque->size--;}//5.实现：“队列的取出队头元素”操作QDateType QueFront(Que* pque){assert(pque);assert(pque->size > 0);return pque->queHead->val;}//6.实现：“队列的取出队尾元素”操作QDateType QueBack(Que* pque){assert(pque);assert(pque->size > 0);return pque->queTail->val;}//7.实现：“队列的判空”bool QueEmpty(Que* pque){assert(pque);return pque->size == 0; //队列中没有元素返回真；队列中有元素返回假}//8.实现：“队列的求出队列中元素的个数”操作int QueSize(Que* pque){assert(pque);return pque->size;}

测试文件

--------------------------------Test.c--------------------------------#include \"Queue.h\"void TestQueue() { Que queue; QueInit(&queue); printf(\"===== 队列测试开始 =====\\n\\n\"); /*--------------------“入队测试”--------------------*/ printf(\"--- 测试1: 入队测试 ---\\n\"); printf(\"入队 1, 2, 3\\n\"); QuePush(&queue, 1); QuePush(&queue, 2); QuePush(&queue, 3); printf(\"队列大小: %d\\n\", QueSize(&queue)); printf(\"队头元素: %d, 队尾元素: %d\\n\", QueFront(&queue), QueBack(&queue)); printf(\"\\n\"); /*--------------------“出队测试”--------------------*/ printf(\"--- 测试2: 出队测试 ---\\n\"); printf(\"出队前队头: %d\\n\", QueFront(&queue)); QuePop(&queue); printf(\"出队后队头: %d\\n\", QueFront(&queue)); printf(\"队列大小: %d\\n\", QueSize(&queue)); printf(\"\\n\"); /*--------------------“混合操作测试”--------------------*/ printf(\"--- 测试3: 混合操作测试 ---\\n\"); printf(\"入队 4, 5, 6\\n\"); QuePush(&queue, 4); QuePush(&queue, 5); QuePush(&queue, 6); printf(\"出队: %d\\n\", QueFront(&queue)); QuePop(&queue); printf(\"入队 7\\n\"); QuePush(&queue, 7); printf(\"当前队列: 队头=%d, 队尾=%d, 大小=%d\\n\", QueFront(&queue), QueBack(&queue), QueSize(&queue)); printf(\"\\n\"); /*--------------------“销毁测试”--------------------*/ printf(\"--- 测试4: 销毁测试 ---\\n\"); QueDestroy(&queue); printf(\"队列已销毁\\n\"); printf(\"销毁后头指针: %p, 尾指针: %p\\n\", (void*)queue.queHead, (void*)queue.queTail); printf(\"\\n\"); printf(\"===== 队列测试结束 =====\\n\");}int main() { TestQueue(); return 0;}

运行结果

在这里插入图片描述

队列的oj练习

225. 用队列实现栈

题目介绍

在这里插入图片描述

方法一：

//任务2：typedef int QDateType; //使用typedf重新定义队列中的变量的数据类型，方便后续进行修改//队列节点的结构体typedef struct QueueNode{//1.队列节点中存储的数据 ---> 一个int变量//2.队列节点中存储下一个节点的位置 ---> 一个指针QDateType val;struct QueueNode* next; //注意这里next的类型可千万不要使用QNode哦，因为这时你还没有定义QNode，要先使用QueueNode进行代替}QNode;//队列的结构体（使用带头尾指针的结构）typedef struct Queue{//1.记录当前队列中元素的个数 ---> 一个int变量//2.指向头部的指针 ---> （用于：头删/取队头的元素）//3.指向尾部的指针 ---> （用于：尾插/取队尾的元素）int size;QNode* queHead;QNode* queTail;}Que;//任务3：//1.队列的初始化//2.队列的销毁//3.队列的入队//4.队列的出队//5.队列的取队头元素//6.队列的取队尾元素//7.队列的判空//8.队列的求队列中元素的数量void QueInit(Que* pque);void QueDestroy(Que* pque);void QuePush(Que* pque, QDateType x);void QuePop(Que* pque);QDateType QueFront(Que* pque);QDateType QueBack(Que* pque);bool QueEmpty(Que* pque);int QueSize(Que* pque);//1.实现：“队列的初始化”操作void QueInit(Que* pque){assert(pque);//1.将队列结构体中“元素的数量”置为0pque->size = 0;//2.将队列结构体中“指向队头/队尾的指针”置为空指针pque->queHead = NULL;pque->queTail = NULL;}//2.实现：“队列的销毁”操作void QueDestroy(Que* pque){assert(pque);//1.将队列结构体中“元素的数量”置为0pque->size = 0;//2.将队列中的所有的节点都释放掉//1）创建临时指针代替queHead进行遍历队列的节点QNode* tmp = pque->queHead;//2）使用tmp遍历所有的节点while (tmp != NULL){//3）创建后继指针存储当前遍历到的节点的下一位置QNode* next = tmp->next;//4)释放当前遍历到的节点free(tmp);//5)更新tmp指针tmp = next;}//将队列结构体中“指向队列头部/尾部的指针”置为空指针pque->queHead = NULL;pque->queTail = NULL;}//3.实现：“队列的入队”操作void QuePush(Que* pque, QDateType x){assert(pque);//思路：使用链表的尾插法实现入队的操作//1）先创建出来一个队列的节点QNode* newNode = (QNode*)malloc(sizeof(QNode));//1.1:判断新开辟的空间是否开辟成功哦if (newNode == NULL){perror(\"malloc fail\");return;}//2）为这个节点进行赋值newNode->val = x;//3）将这个节点链接到队列链表的后面//3.1：将新开辟的节点的next指针域置空newNode->next = NULL;//3.2：将新开辟的节点链接到队列链表的尾部//3.3.1：如果当前的队列链表中没有节点if (pque->queTail == NULL){pque->queHead = pque->queTail = newNode;}//3.3.2：如果当前的队列链表中有节点else{pque->queTail->next = newNode;pque->queTail = newNode;}//4）队列中的元素的数量增加pque->size++;}//4.实现：“队列的出队”操作void QuePop(Que* pque){assert(pque);assert(pque->size > 0);//注意：当我们：1.删除某个数据结构中的元素时 2.从某个数据结构中取出元素的时//---> 需要判断当前的数据结构中是否还有元素//思路：使用链表的头删法实现出队操作//1）如果当前队列中只有一个元素if (pque->queHead->next == NULL){//1.1：将这一个节点删除掉free(pque->queHead);//1.2：将指向队头和队尾的指针都置为空pque->queHead = NULL;pque->queTail = NULL;}//2）如果队列中的元素有多个else{//2.1：创建一个临时的指针来存放queHead指针的下一个位置QNode* next = pque->queHead->next;//2.2：释放掉queHead指针指向的节点free(pque->queHead);//2.3：将queHead指针移动到下一个节点的位置pque->queHead = next;}//3）队列中的元素的数量减少pque->size--;}//5.实现：“队列的取出队头元素”操作QDateType QueFront(Que* pque){assert(pque);assert(pque->size > 0);return pque->queHead->val;}//6.实现：“队列的取出队尾元素”操作QDateType QueBack(Que* pque){assert(pque);assert(pque->size > 0);return pque->queTail->val;}//7.实现：“队列的判空”bool QueEmpty(Que* pque){assert(pque);return pque->size == 0; //队列中没有元素返回真；队列中有元素返回假}//8.实现：“队列的求出队列中元素的个数”操作int QueSize(Que* pque){assert(pque);return pque->size;}----------------------------------------------------------------------------------------typedef struct { Que q1; Que q2;} MyStack;MyStack* myStackCreate() { MyStack* pstk=(MyStack*)malloc(sizeof(MyStack)); QueInit(&(pstk->q1)); QueInit(&(pstk->q2)); return pstk;}// psrk：是指向结构体Mystack的指针void myStackPush(MyStack* pstk, int x) { // & 结构成员 ：（得到结构体MyStack的成员变量队列q1的地址） if(!QueEmpty(&(pstk->q1))) { QuePush(&(pstk->q1),x); } else { QuePush(&(pstk->q2),x); }}int myStackPop(MyStack* pstk) { //假设法：得到“空/非空”队列，之后直接对“空/非空”队列进行操作，而不需要使用q1或q2进行操作 Que*empty=&(pstk->q1); //这里的empty是结构体指针，而pstk->q1是结构体 Que*noempty=&(pstk->q2); if(!QueEmpty(&(pstk->q1))) { noempty=&(pstk->q1); empty=&(pstk->q2); } while(QueSize(noempty)>1) { QuePush(empty,QueFront(noempty)); QuePop(noempty); } int front=QueFront(noempty); QuePop(noempty); return front;}int myStackTop(MyStack* pstk) { if(!QueEmpty(&(pstk->q1))) return QueBack(&(pstk->q1)); else return QueBack(&(pstk->q2));}bool myStackEmpty(MyStack* pstk) { return (QueEmpty(&(pstk->q1))&&QueEmpty(&(pstk->q2))); }void myStackFree(MyStack* pstk) { //销毁栈时注意销毁的顺序：1.先销毁栈结构体中的元素队列 2.再销毁栈的结构体 //销毁顺序：“从内往外”进行销毁 QueDestroy(&(pstk->q1)); QueDestroy(&(pstk->q2)); free(pstk);}

----------------循环队列----------------

循环队列的数组实现

循环队列要怎么进行判空or判满？

循环队列（Circular Queue）：判空和判满的实现需要考虑 队头（front） 和 队尾（rear） 指针的位置关系。

由于循环队列会重复利用存储空间，当队头和队尾指针相遇时，既可能表示队列已满，也可能表示队列已空，因此需要特殊处理。

常见的实现方式：预留空位法、计数器法、标志位法

三种方法的比较：

方法优点缺点适用场景 预留空位法 实现简单，效率高浪费一个存储空间大多数常规情况 计数器法 不浪费空间需要维护额外变量需要最大化利用空间 标志位法 不浪费空间逻辑稍复杂对内存要求严格的场景方法 判空条件 判满条件 预留空位法 front == rear (rear + 1) % capacity == front 计数器法 count == 0 count == capacity 标志位法 !isFull && front == rear isFull && front == rear

总结：预留空位法最常用，并且C++ STL中也是使用的预留空位法解决的如何判断循环队列空or满？

所以下面我们实现的循环队列的两个判空和判满的接口函数也是使用的这种方式进行的判断。

在这里插入图片描述

头文件

-----------------------------CircularQueue.h-----------------------------#pragma once//任务1：包含要使用的头文件#include #include #include #include //任务2：定义循环队列的存储结构typedef int CQDataType;typedef struct CircularQueue{//1.使用动态数组模拟实现循环队列 ---> 定义一个int*类型的指针//2.记录队列中队头元素的位置 ---> 定义一个int类型的变量//3.记录队列中队尾元素的位置 ---> 定义一个int类型的变量//4.记录队列中当前元素的数量 ---> 定义一个int类型的变量//5.记录队列的容量 ---> 定义一个int类型的变量CQDataType* a;int front;int rear;int size;int capacity;}CQ;//任务3：声明要使用的辅助函数//1.用于循环链表的扩容（辅助函数）//2.用于打印循环队列（辅助函数）void CQCheckCapacity(CQ* pcque);void CQPrint(CQ* pcque);//任务4：声明循环队列的接口函数//1.循环队列的初始化//2.循环队列的销毁//3.循环队列的判空//4.循环队列的判满//5.循环队列的入队（指的是：尾部入队，因为尽管是循环队列，但是它还是要严格遵循队列的FIFO（先进先出）原则，毕竟它还不是双端队列）//6.循环队列的出队//7.循环队列的取队头的元素//8.循环队列的取队尾的元素void CQInit(CQ* pcque);void CQDestroy(CQ** ppcque);bool CQEmpty(CQ* pcque);bool CQFull(CQ* pcque);void CQPush(CQ* pcque, CQDataType x);void CQPop(CQ* pcque);CQDataType CQFront(CQ* pcque);CQDataType CQRear(CQ* pcque);

实现文件

-----------------------------CircularQueue.c----------------------------- #include \"CircularQueue.h\"/*-----------------------------------------辅助工具函数-----------------------------------------*//** * @brief 检查并扩容循环队列的存储空间 * * @param pcque 指向循环队列的指针 * * @note 该函数完成以下工作： * 1. 检查队列是否已满 * 2. 计算新容量（初始为0时设为4，否则2倍扩容） * 3. 使用realloc扩容存储数组 * 4. 更新队列的容量字段 * * @warning 扩容后不处理元素位置的调整（循环队列可能需要特殊处理） *///1.实现：“循环队列的扩容”辅助函数void CQCheckCapacity(CQ* pcque){if (pcque->capacity == 0) //特殊处理初始情况{int newCapacity = 4;CQDataType* tmp = (CQDataType*)malloc(newCapacity * sizeof(CQDataType));if (!tmp) {perror(\"malloc fail\");exit(EXIT_FAILURE);}pcque->a = tmp;pcque->capacity = newCapacity;}else if (pcque->size == pcque->capacity-1) //容量为capacity的循环队列最多只能存储capacity-1个元素{//1.1：判断需要扩容的容量的大小int newCapacity = pcque->capacity * 2;//1.2：使用realloc进行扩容CQDataType* tmp = (CQDataType*)realloc(pcque->a, newCapacity*sizeof(CQDataType));if (tmp == NULL){perror(\"realloc fail\");return;}//更新数组的指针 + 循环队列的容量pcque->a = tmp;pcque->capacity = newCapacity;}}//2.实现：“打印循环队列”的辅助函数void CQPrint(CQ* pcque){assert(pcque); //断言检查：确保队列指针有效，防止对空指针进行解引用//情况1：循环队列为空队列if (CQEmpty(pcque)) return;//情况2：循环队列非空队列//2.1：定义一个变量记录打印循环队列中的元素的数量int count = 0;//2.2：循环打印队列中的元素int pcur = pcque->front; //注意：这里一定要使用一个临时的指针进行遍历循环队列，防止pcque指针的移动导致队列结构错乱while (count < pcque->size) {printf(\"%d \", pcque->a[pcur]);pcur = (pcur + 1) % pcque->capacity;count++;}printf(\"\\n\");}/*-----------------------------------------核心功能函数-----------------------------------------*//** * @brief 初始化循环队列 * * @param pcque 指向需要初始化的循环队列结构体的指针 * * @note 该函数完成以下工作： * 1. 检查指针有效性（断言保护） * 2. 初始化队列的基本状态： * - 当前元素数量(size)置为0 *- 当前队列容量(capacity)置为0 * - 队头指针(front)置为0 * - 队尾指针(rear)置为0 * - 数据存储数组指针(a)置为NULL * * @warning * - 使用前必须确保pcque指针有效 * - 该初始化不会分配存储空间，首次插入元素时会自动扩容 *///1.实现：“循环队列的初始化”操作void CQInit(CQ* pcque){assert(pcque); //断言检查：确保队列指针有效，防止对空指针进行解引用pcque->size = 0;pcque->capacity = 0;pcque->front = 0;pcque->rear = 0;pcque->a = NULL;}//2.实现：“循环队列的销毁”操作void CQDestroy(CQ** ppcque){assert(ppcque); //断言检查1：确保传入的指针是非空指针，防止对空指针进行解引用assert(*ppcque); //断言检查2：确保队列指针有效，防止对空指针进行解引用（建议加上）/*----------第一步：释放动态数组内存----------*/free((*ppcque)->a);(*ppcque)->a = NULL;/*----------第一步：重置队列状态----------*/(*ppcque)->size = (*ppcque)->capacity = 0;(*ppcque)->front = (*ppcque)->rear = 0;/*----------第一步：释放队列结构体内存----------*/free(*ppcque);*ppcque = NULL; //真正修改外部指针//（函数的形参需要是二级指针，如果使用的是一级指针，参数是值传递，在函数内部将ppcque置空，对外部指针无影响，外部指针将变为野指针）}/** * @brief 判断循环队列是否为空 * * @param pcque 指向循环队列结构体的指针（需确保非NULL） * @return bool 返回true表示队列为空，false表示非空 * * @note 该函数实现循环队列的判空逻辑： * 1. 使用断言确保指针有效性（调试阶段捕获空指针） * 2. 直接比较队头指针(front)和队尾指针(rear) * 3. 当front == rear时判定为空队列 */ //3.实现：“循环队列的判空”操作bool CQEmpty(CQ* pcque){assert(pcque); //断言检查：确保队列指针有效，防止对空指针进行解引用//判满的核心逻辑：队尾指针和队头指针指向同一个位置return pcque->front == pcque->rear; //循环队列：空为true；非空为false}/** * @brief 判断循环队列是否已满 * * @param pcque 指向循环队列结构体的指针 * @return bool 返回true表示队列已满，false表示未满 * * @note 该函数实现循环队列的判满逻辑： * 1. 使用取模运算实现循环指针计算 * 2. 通过(rear+1) % capacity == front判断队列满 * 3. 预留一个空位区分队列空和满的状态 * * @details 循环队列判满的数学原理： * - 队列容量为capacity时，实际可以使用的是capacity-1个空间 * - 当(rear+1) % capacity == front时： * a) 若front == rear，队列为空 * b) 否则，队列已满 * - 这样设计避免了使用额外标志位 *///4.实现：“循环队列的判满”操作bool CQFull(CQ* pcque){assert(pcque);//断言检查：确保队列指针有效，防止对空指针进行解引用//判满的核心逻辑：队尾指针的下一个位置（取模后）等于队头指针return (pcque->rear + 1) % (pcque->capacity) == pcque->front; //循环队列：满为true；不满为false /* 示例说明：* 假设capacity=4（实际可使用的是3个位置）：** 情况1：队列满* front=0, rear=3* (3+1)%4 = 0 == front → 满** 情况2：队列未满* front=0, rear=1* (1+1)%4 = 2 != front → 未满** 情况3：队列空* front=0, rear=0* (0+1)%4 = 1 != front → 未满（与判空条件区分）*/}/** * @brief 向循环队列尾部插入一个元素 * * @param pcque 指向循环队列的指针（需确保非NULL） * @param x 要插入的元素值 * * @note 该函数执行以下操作： * 1. 检查队列指针有效性（调试阶段断言保护） * 2. 检查并扩容队列容量（通过CQCheckCapacity） * 3. 在队尾位置存入元素 * 4. 更新队尾指针（实现循环移动） *///5.实现：“循环队列的入队”操作void CQPush(CQ* pcque, CQDataType x){assert(pcque); //断言检查：确保队列指针有效，防止对空指针进行解引用CQCheckCapacity(pcque);//1.将入队的元素的存储在动态数组中pcque->a[pcque->rear] = x;//2.将循环队列的尾指针向后移动pcque->rear++;//3.更新尾指针指向的正确的位置（处理越界的情况）pcque->rear = pcque->rear % (pcque->capacity);//4.更新当前循环队列中元素的数量pcque->size++;}/** * @brief 从循环队列头部移除一个元素（出队操作） * * @param pcque 指向循环队列的指针（需确保非NULL） * * @note 该函数执行以下操作： * 1. 检查队列指针有效性（断言保护） * 2. 检查队列是否为空（空队列直接返回） * 3. 移动队头指针实现出队 * 4. 处理指针越界（循环修正） *///6. 实现：“循环队列的出队”操作void CQPop(CQ* pcque){assert(pcque);//断言检查：确保队列指针有效，防止对空指针进行解引用//情况1：循环队列为空if (CQEmpty(pcque)) return;//情况2：循环队列非空//1.将循环队列的头指针向后移动pcque->front++;//2.更新头指针指向正确的位置（处理越界的情况）pcque->front = pcque->front % (pcque->capacity);//3.更新当前循环队列中元素的数量pcque->size--;}//7.实现：“循环队列的获取队头的元素”操作CQDataType CQFront(CQ* pcque){assert(pcque); //断言检查：确保队列指针有效，防止对空指针进行解引用//情况1：循环队列为空if (CQEmpty(pcque)) return -1;//情况2：循环队列非空return pcque->a[pcque->front];}/** * @brief 获取循环队列的队尾元素 * * @param pcque 指向循环队列的指针（需确保非NULL） * @return CQDataType 返回队尾元素的值，队列为空时返回-1（需根据实际数据类型调整） * * @note 该函数执行以下操作： * 1. 检查队列指针有效性（断言保护） * 2. 检查队列是否为空（空队列返回-1） * 3. 计算队尾元素的实际位置 * 4. 返回队尾元素值 *///8.实现：“循环队列的获取队尾的元素”操作CQDataType CQRear(CQ* pcque){assert(pcque); //断言检查：确保队列指针有效，防止对空指针进行解引用//情况1：循环队列为空if (CQEmpty(pcque)) return -1;//情况2：循环队列非空//返回队尾的元素比返回队头的元素要复杂：//原因：front指针指向的是队头的元素的位置；rear指针指向的是队尾的元素的后一个位置//怎么让队尾指针指向它的前一个位置？真的是pcirque->tail--;这么简单吗？//情况1：rear指向数组索引为0的位置（特殊情况-->rear应该指向的是capacity的位置，而不是数组下标为-1的位置）//情况2：rear指向数组索引的其他位置（正常情况）return pcque->a[(pcque->rear - 1 + pcque->capacity) % (pcque->capacity)];/* 关键计算：获取队尾元素的实际位置 1. pcque->rear - 1 ：理论上队尾元素在前一个位置 2. + pcque->capacity ：防止负数（当rear=0时） 3. % pcque->capacity ：确保结果在合法范围内 示例： - 当capacity=5, rear=0时：(0-1+5)%5=4 - 当capacity=5, rear=3时：(3-1+5)%5=2*/}

测试文件

----------------------------------Test.c----------------------------------#include \"CircularQueue.h\"void TestCircularQueue(){ CQ cque; CQInit(&cque); printf(\"===== 循环队列测试开始 =====\\n\\n\"); /*--------------------“入队测试”--------------------*/ printf(\"--- 测试1: 入队操作 ---\\n\"); for (int i = 1; i <= 3; i++) { printf(\"入队 %d\\n\", i); CQPush(&cque, i); CQPrint(&cque); } /*--------------------“判满测试”--------------------*/ printf(\"--- 测试2: 队列满检查 ---\\n\"); printf(\"队列是否已满? %s\\n\", CQFull(&cque) ? \"是\" : \"否\"); printf(\"\\n\"); /*--------------------“获取队头和队尾元素的测试”--------------------*/ printf(\"--- 测试3: 访问队首/队尾元素 ---\\n\"); printf(\"队首元素: %d\\n\", CQFront(&cque)); printf(\"队尾元素: %d\\n\", CQRear(&cque)); printf(\"\\n\"); /*--------------------“出队测试”--------------------*/ printf(\"--- 测试4: 出队操作 ---\\n\"); for (int i = 0; i < 3; i++) { printf(\"出队%d 得到：\\n\", CQFront(&cque)); CQPop(&cque); CQPrint(&cque); } /*--------------------“再次入队测试”（测试循环特性）--------------------*/ printf(\"--- 测试5: 循环特性测试 ---\\n\"); for (int i = 6; i <= 8; i++) { printf(\"入队 %d\\n\", i); CQPush(&cque, i); CQPrint(&cque); } /*--------------------“判空测试”--------------------*/ printf(\"--- 测试6: 队列空检查 ---\\n\"); printf(\"队列是否为空? %s\\n\", CQEmpty(&cque) ? \"是\" : \"否\"); printf(\"\\n\"); /*--------------------“销毁测试”--------------------*/ printf(\"--- 测试7: 队列销毁 ---\\n\"); CQ* pQueue = (CQ*)malloc(sizeof(CQ)); CQInit(pQueue); for (int i = 10; i <= 12; i++) { CQPush(pQueue, i); } printf(\"销毁前:\\n\"); CQPrint(pQueue); CQDestroy(&pQueue); printf(\"销毁后，指针状态为 %s\\n\", pQueue == NULL ? \"空\" : \"非空\"); printf(\"\\n===== 所有测试完成 =====\\n\");}int main(){ TestCircularQueue(); return 0;}

运行结果

在这里插入图片描述

循环队列的oj练习

622. 设计循环队列

题目介绍

在这里插入图片描述

方法一：

typedef struct { //使用数组实现循环队列 //1.定义队列的头指针 ---> 一个int变量（数组的下标） //2.定义队列的尾指针 ---> 一个int变量（数组下标，指向下一个插入位置） //3.记录队列中元素的数量 --> 一个int变量（实际可用空间为k，数组大小为k+1） //4.存储队列元素的数组 --> 一个int指针（动态分配） int head; int tail; int size; int* a;} MyCircularQueue;// 函数前置声明bool myCircularQueueIsFull(MyCircularQueue* pcirque);bool myCircularQueueIsEmpty(MyCircularQueue* pcirque);MyCircularQueue* myCircularQueueCreate(int k) { //实现：“循环队列的创建+初始化”操作 //1）创建 //1.1：分配队列结构体内存 MyCircularQueue*pcirque=(MyCircularQueue*)malloc(sizeof(MyCircularQueue)); //1.2：分配储存元素数组的内存 pcirque->a=(int*)malloc((k+1)*sizeof(int)); //2）初始化 pcirque->head=0; pcirque->tail=0; pcirque->size=k; //3）返回队列的结构体指针 return pcirque;}bool myCircularQueueEnQueue(MyCircularQueue* pcirque, int value) { //实现：“循环队列的入队”操作 //0.需要注意的是：循环队列中插入数据时需要先判断队列是否已经满了 if(myCircularQueueIsFull(pcirque)) return false; //1.将入队的元素的值存入循环队列中 pcirque->a[pcirque->tail]=value; //2.将循环队列的尾指针向后进行移动 pcirque->tail++; //3.更新尾指针指向的位置使其指向合法 pcirque->tail%=(pcirque->size+1); return true;}bool myCircularQueueDeQueue(MyCircularQueue* pcirque) { //实现：“循环队列的出队”操作 //0.出队操作要先判断队列是否为空 if(myCircularQueueIsEmpty(pcirque)) return false; //将1和2步合成一步 pcirque->head=(pcirque->head+1)%(pcirque->size+1); return true;}int myCircularQueueFront(MyCircularQueue* pcirque) { //实现：“循环队列的获取队头的元素”操作 //0.需要先判断队列是否为空 if(myCircularQueueIsEmpty(pcirque)) return -1; return pcirque->a[pcirque->head];}int myCircularQueueRear(MyCircularQueue* pcirque) { //0.需要先判断队列是否为空 if(myCircularQueueIsEmpty(pcirque)) return -1; //返回队尾的元素比返回队头的元素要复杂， //原因：head指针指向的是队头的元素的位置；tail指针指向的时队尾的元素的后一个位置 //怎么让队尾指针指向它的前一个位置？真的是pcirque->tail--这么简单吗？ //情况1：tail指向数组索引为0的位置（特殊情况-->tail应该指向的是size+1的位置） //情况2：tail指向数组索引的其他位置（正常情况） return pcirque->a[(pcirque->tail-1+pcirque->size+1)%(pcirque->size+1)];}bool myCircularQueueIsEmpty(MyCircularQueue* pcirque) { //实现：“循环队列的判空”操作 //空：true；不空：false return pcirque->head==pcirque->tail;}bool myCircularQueueIsFull(MyCircularQueue* pcirque) { //实现：“循环队列的判满”操作 //满：true；不满：false return (pcirque->tail+1)%(pcirque->size+1)==pcirque->head;}void myCircularQueueFree(MyCircularQueue* pcirque) { //从内向外进行销毁 //1.内部销毁：将动态数组销毁掉 //2.外部销毁：将循环队列销毁掉 free(pcirque->a); free(pcirque);}

在这里插入图片描述

《数据结构初阶》【顺序栈 + 链式队列 + 循环队列】

《数据结构初阶》【顺序栈 + 链式队列 + 循环队列】

前言：

什么是栈？

栈有哪些实现方式？我们要选择哪种实现方式？

--------------------------------

什么是队列？

队列有哪些实现方式？我们要选择哪种实现方式？

--------------------------------

什么是循环队列？

循环队列有哪些实现方式？我们要选择哪种实现方式？

----------------顺序栈----------------

栈的动态数组实现

顺序栈初始化时该如何初始化top？

头文件

实现文件

测试文件

运行结果

栈的oj练习

20. 有效的括号

题目介绍

方法一：

232. 用栈实现队列

题目介绍

方法一：

----------------链式队列----------------

队列的链表实现

头文件

实现文件

测试文件

运行结果

队列的oj练习

225. 用队列实现栈

题目介绍

方法一：

----------------循环队列----------------

循环队列的数组实现

循环队列要怎么进行判空or判满？

头文件

实现文件

测试文件

运行结果

循环队列的oj练习

622. 设计循环队列

题目介绍

方法一：

相关问题

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载