关键词：
栈和队列
文章很长,如有需要,请先收藏哟❤❤❤❤❤❤
前言
栈和队列在数据结构中也是重要的一部分，他们都是特殊的线性表，许多需要用到我们的栈和队列，回想一下，我们以前写过的递归，其实都是可以通过我们的栈去模拟实现，而队列的使用也是十分多的，让我们一起学习学习他们的实现
一、栈
1.栈的结构
我们模拟实现栈的结构非常简单，只是在我们的线性表的基础上更改，不允许了我们的随机访问，而是得通过接口来实现数据的插入和删除，
我们的数据都是得从栈顶入栈，从栈顶出栈
注释：
压栈/进栈/入栈：栈的插入操作，入数据在栈顶
出栈： 站的删除操作，出数据也在栈顶
来看看下面这个动图加深理解吧：
代码展示栈的结构:
typedef int STDataType;
typedef struct Stack
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
Stack;
解释：这上面_a数组表示我们要的是一个动态开辟的数组，_top表示我们图中所示的数组，_capacity表示我们的容量大小，当_top与_capacity相同的时候我们就可以进行扩容操作了
首先我们创建一个stack.h,stack.c,和一个用来测试接口的test_stack_queue.c文件
常见接口：
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
2.初始化栈
听过我之前讲的函数栈帧的同学肯定知道我要写的第一个接口是什么
–初始化，不清楚的同学点击跳转函数栈帧
看完之后你就能明白为什么要初始化？不初始化的后果？
void StackInit(Stack* ps)
assert(ps);
ps->_a = NULL;
ps->_capacity = ps->_top = 0;
3.压栈操作
每次只是需要将top位置更新，因为是底层实现用的数组，所以说内存不够需要扩容，我们就分开一个函数CheckCapacity（），每次检测容量是否用完，
这里的增容是可以1.5或者2倍，但是增容意味着空间开太大会造成浪费，增容太少又造成频繁增容效率低下，所以我们一般选择适中的2倍。
void CheckCapacity(Stack* ps)
assert(ps);
if (ps->_capacity == ps->_top)
int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
STDataType* tmp= (STDataType*)realloc(ps->_a,sizeof(STDataType) * newcapacity);
if (tmp == NULL)
printf("增容失败\\n");
exit(-1);
ps->_a = tmp;
ps->_capacity = newcapacity;
void StackPush(Stack* ps, STDataType data)
assert(ps);
CheckCapacity(ps);
ps->_a[ps->_top] = data;
ps->_top++;
4.出栈操作
出栈的时候需要检测是否栈内有无元素，没有元素的话我们就报错处理 ，当然这里判断栈是否为空我们也可以封装一个函数
栈是否为空
int StackEmpty(Stack* ps)
assert(ps);
return ps->_top ==0;//0为空
void StackPop(Stack* ps)
assert(ps);
assert(!StackEmpty(ps));
ps->_top--;
5.获取栈顶元素
也是要判断一下是否在栈内有无元素
STDataType StackTop(Stack* ps)
assert(ps);
assert(!StackEmpty(ps));
return ps->_a[ps->_top-1];
6.获取栈中有效元素个数
_top的位置就是元素的总数
int StackSize(Stack* ps)
assert(ps);
return ps->_top;
7.销毁栈
销毁栈的过程，销毁栈是重要的过程，我们的_a数组是动态开辟的，没有释放会造成内存泄漏
当然，注意看这里的ps指针是不能置空的，在之前的详解指针这一节的常见错误中有提及！
void StackDestroy(Stack* ps)
assert(ps);
free(ps->_a);
ps->_a = NULL;
//free(ps); 错误
ps->_capacity = ps->_top = 0;
二、队列
1.队列的结构
队列的结构会比栈的难懂一些，因为队列的属性就是先入先出，所以采用顺序表的话我们的头删就要去移动数据覆盖第一个位置，或者用一个指针记录头的位置，头删的时候用移动头节点来表示，但是这都不如链表来的方便，链表在我们的头部删除是O（1）的时间复杂度，并且不用删除队尾元素，所以我们这里使用我们的单链表结构来实现队列！
链表的初阶
链表的进阶
// 链式结构：表示队列
typedef int QDataType;
typedef struct QListNode
struct QListNode* _next;
QDataType _data;
QNode;//队列中结点的结构
// 队列的结构
typedef struct Queue
QNode* _front;//头指针
QNode* _rear;//尾指针
Queue;
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
动图：
我们先封装队列中的一个结点，结点中有指向下一个元素的指针，和自身的值，然后因为我们的队列是用单链表实现的，而队列有一个获取队尾元素的接口，所以我们设置尾指针_rear能够是我们不用每次遍历找到尾在进行插入
2.队列的初始化
void QueueInit(Queue* q)
assert(q);
q->_front = NULL;
q->_rear = NULL;
3.队列的插入
队列的插入就和单链表的头插一模一样，就是记得判断一开始我们的队头和队尾都是NULL，后续只需要移动_rear(队尾指针)！！！
动图：
void QueuePush(Queue* q, QDataType data)
assert(q);
QNode* tmp = (QNode*)malloc(sizeof(QNode));
tmp->_next = NULL;
tmp->_data = data;
if (q->_rear == NULL)
q->_front = q->_rear = tmp;
else
q->_rear->_next = tmp;
q->_rear = tmp;
4.队列的删除
动图:(当删除最后一个结点时易忽略处理_front 指针)
尾删需要注意是否队列中存在元素！！这里
的逻辑比较简单，但要注意当队列元素只剩一个的时候我们的队尾指针也要置成NULL，不然就会造成野指针
void QueuePop(Queue* q)
assert(q);
assert(!QueueEmpty(q));
QNode* first = q->_front->_next;
if (first == NULL)
q->_rear = NULL;//处理这一步
free(q->_front);
q->_front = first;
5.获取队列头/尾部元素
这个就很简单啦!!
QDataType QueueFront(Queue* q)
assert(q);
assert(!QueueEmpty(q));
return q->_front->_data;
QDataType QueueBack(Queue* q)
assert(q);
assert(!QueueEmpty(q));
return q->_rear->_data;
6.获取队列中有效元素个数
int QueueSize(Queue* q)
assert(q);
int n = 0;
QNode* cur = q->_front;
while (cur)
n++;
cur = cur->_next;
return n;
7.检测队列是否为空
如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
assert(q);
return q->_front == NULL;
8.销毁队列
这里要遍历队列,因为每一个结点都是我们从堆上开辟的,我们就要一个个的释放
void QueueDestroy(Queue* q)
assert(q);
while (!QueueEmpty(q))
QNode* tmp = q->_front->_next;//保存下一个结点
free(q->_front);
q->_front = tmp;
q->_front = q->_rear = NULL;
从上面的图我们就能看出来，出栈的时候我们只能从栈顶出，出来的结果刚好与入的值相反，其实同一组数据入栈在出栈顺序不同的时候是有不同的结果的，
三、循环队列
解释:
循环队列的使用场景:当我们在去打疫苗的时候排队,注射疫苗的位置有限,我们前面排队的先打,后面的后进去的后打.
循环队列就是固定了队列的大小空间
设计循环队列
题目分析:这道题目是让我们设计一个循环队列,先说结论我们这里的循环队列所用的是循序表实现,因为我们在这个场景下不需要扩容,顺序表随机访问率高.其次如果使用单链表,在进行删除头部元素的时候我们需要找到上一个指针,为了效率就得有双向链表,但有简单又高效的结构我们优先去使用顺序表.
循环链表的结构
typedef struct
int *a;//指向我们的数组
int front;//队头
int rear;//队尾,指向的位置是我们存放的位置
int k;
MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
MyCircularQueue* obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a =(int*)malloc(sizeof(int)*(k+1));
obj->front =obj->rear=0;
obj->k = k;
return obj;
循环链表的实现
题目看起来并不难,但有一个点确实需要琢磨,我们用顺序表的时候,一开始我们的队头元素的指针和队首元素的指针是指向同一处的,这个时候我们是认为他是题目看起来并不难,但有一个点确实需要琢磨,我们用顺序表的时候,一开始我们的队头元素的指针和队首元素的指针是指向同一处的,
这个时候是整个数组我们都已经放满了呢还是一个元素都没放入,这就会出现分歧
解决方案:
方案1.
聪明的同学可能一下子就想着说我们可能可以开一个标记矩阵,放过元素的我们标记一下,删除的时候我们把他的状态也标记一下,这个方案毫无疑问是可行的,但是空间开的就比较多了,下面有一种更好的
方案2.
我们在原来的基础上多开一个数组,当我们的队头指针与队尾指针相遇时是我们的数组还没元素,当_rear的下一个元素是我们的_front时才是我们整个数组放满了,下图为放满的情况
然后这题要对下标进行判断,下标若走到-1,则更新成k,若走到k+1则更新成0
typedef struct
int *a;//指向我们的数组
int front;//队头
int rear;//队尾,指向的位置是我们存放的位置
int k;
MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k)
MyCircularQueue* obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->a =(int*)malloc(sizeof(int)*(k+1));
obj->front =obj->rear=0;
obj->k = k;
return obj;
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
if(((obj->rear+1)%(obj->k+1)) ==obj->front)
return false;
//插入元素
obj->a[obj->rear] = value;
++obj->rear;
obj->rear %= (obj->k+1);
return true;
bool myCircularQueueDeQueue(MyCircularQueue* obj)
if(obj->front == obj->rear)//删除元素front指针往前走
return false;
obj->front++;
if(obj->front == obj->k+1)
obj->front =0;
return true;
int myCircularQueueFront(MyCircularQueue* obj)
if(obj->front == obj->rear)
return -1;
return obj->a[obj->front];
int myCircularQueueRear(MyCircularQueue* obj)
if(obj->front ==obj->rear)
return -1;
int x = obj->rear -1;
if(x ==-1)
x= obj->k;
return obj->a[x];
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
return obj->rear ==obj->front;
bool myCircularQueueIsFull(MyCircularQueue* obj)
return ((obj->rear+1)%(obj->k+1)) ==obj->front;
void myCircularQueueFree(MyCircularQueue* obj)
free(obj->a);
obj->a =NULL;
free(obj);
四、一些习题
1.有效的括号
链接:有效的括号
这题要用到我们的栈,对于C语言的学习者,我们并没有库,大家可以用下面我在码云发布的栈的代码来写
思路:我们遇到左括号的时候就入栈,遇到右括号的时候就拿栈顶数据比较,只要不符合就返回false,若字符遍历完且栈里的数据都出完了,则括号都能一一匹配
class Solution
public:
bool isValid(string s)
//只要是左括号我们就入栈，遇到右括号我们就从栈顶pop一个数据看与他是否匹配
stack<char> st;
int len =s.size();
for(int i =0;i<len;i++)
char ch =s[i];
if(ch =='('||ch ==''||ch=='[')
st.push(ch);
else
if(st.empty())
return false;
else
char ch2 = st.top();
st.pop();
if((ch ==')'&&ch2 !='(')
|| (ch ==''&&ch2 !='')
|| (ch ==']'&&ch2!='['))
return false;
if(st.empty())
return true;
return false;
;
2. 用队列实现栈
看到前面的不要慌,只是队列的实现而已,我们为了练习队列可以就用我们实现的队列
思路:用两个队列分别为q1,q2,每次push数据往其中为有数据的入,都没有就随便选一个入,pop数据的时候就将有数据的导入到没数据的,在判断是否为最后一个,是的话我们就pop掉且不用入有空的队列了
myStackPush数据的时候只用往nonempty(不为空)的队列入,动图:
myStackPop都要导到另一个为空的队列在pop掉最后一个数据,动图:
typedef int QDataType;
typedef struct QListNode
struct QListNode* _next;
QDataType _data;
QNode;//队列中结点的结构
// 队列的结构
typedef struct Queue
QNode* _front;
QNode* _rear;
Queue,queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
void QueueInit(Queue* q)
assert(q);
q->_front = NULL;
q->_rear = NULL;
void QueuePush(Queue* q, QDataType data)
assert(q);
QNode* tmp = (QNode*)malloc(sizeof查看详情
python数据分析电商用户行为，看完这一篇就够了(代码片段)
本文分析主要内容分为下四个部分：一.项目背景二.数据集介绍三.数据清洗四.分析模型构建五.总结一.项目背景项目对京东电商运营数据集进行指标分析以了解用户购物行为特征，为运营决策提供支持建议。本文采用了My... 查看详情
简直无敌！最全springboot学习教程，看完这一篇就够了！
前言Spring 是一个非常流行和成功的Java应用开发框架。Spring Security 是 Spring 家族中的一个安全管理框架，提供了一套Web应用安全性的完整解决方案。在用户认证方面，SpringSecurity框架支持主流的认证方式，包括HTTP... 查看详情
我们为什么需要云原生？看完这一篇就够了
作者|侯淼淼出品|CSDN（ID：CSDNnews）云原生这个词对于业内大多数人来说都不陌生，伴随着云计算的蓬勃发展，大有愈演愈烈之势，已经赫然成为企业数字化转型的重要基石。与此同时，无数的新兴词汇... 查看详情
我们为什么需要云原生？看完这一篇就够了
作者|侯淼淼出品|CSDN（ID：CSDNnews）云原生这个词对于业内大多数人来说都不陌生，伴随着云计算的蓬勃发展，大有愈演愈烈之势，已经赫然成为企业数字化转型的重要基石。与此同时，无数的新兴词汇... 查看详情
黑客入门教程（非常详细）从零基础入门到精通，看完这一篇就够了。
...往下看了.2.多练多想,不要离开了教程什么都不会了.最好看完教程自己独立完成技术方面的开发.3.有时多google,baidu,我们往往都遇不到好心的大神,谁会无聊天天给你做解答.4.遇到实在搞不懂的,可以先放放,以后再来解决.基本方向:1... 查看详情
网络安全基础入门教程（非常详细）从零基础入门到精通，看完这一篇就够了
...。2.多练多想，不要离开了教程什么都不会，最好看完教程后自己独立完成技术方面的开发。3.有问题多google、baidu…我们往往都遇不到好心的大神，谁会无聊到天天给你做解答。4.遇到实在搞不懂的，可以先暂时... 查看详情
强化学习入门这一篇就够了！！！万字长文
强化学习强化学习入门这一篇就够了万字长文带你明明白白学习强化学习...强化学习入门这一篇就够了强化学习前言一、概率统计知识回顾1.1随机变量和观测值1.2概率密度函数1.3期望1.4随机抽样二、强化学习的专业术语2.1Stateanda... 查看详情
2022版超详细python+pycharm安装保姆级教程，python环境配置和使用指南，看完这一篇就够了
这两年被Python初学小白问到最多的问题就是，该用什么代码编辑工具？说实话，我个人是用JupyterNotebook最多，主要是经常做数据可视化，方便些。但对于初学者来说，PyCharm仍是不二的选择，甚至我建议... 查看详情
2023年黑客零基础从入门到精通学习成长路线（超多图非常详细），看完这一篇就够了。
怎样规划学习路线？如果你是一个安全行业新人，我建议你先从网络安全或者Web安全/渗透测试这两个方向先学起，一是市场需求量高，二则是发展相对成熟入门比较容易。值得一提的是，学网络安全，是... 查看详情
网络安全零基础入门教程（非常详细）从零基础入门到精通，看完这一篇就够了。(代码片段)
...多想，不要离开了教程就什么都不会，最好能在看完教程后自己独立地完成技术方面的开发。3.学习过程中遇到问题多google、baidu…我们往往都遇不到好心的大神，谁会无聊天天给你做解答呢？4.遇到实在搞不懂的&... 查看详情
androidaudio知识梳理看完这一篇就够了！(代码片段)
...f0c;看不懂的地方可以反复琢磨，多多动脑思考。坚持看完哦！一、Audio基础1.音频基础属性音频指人耳可以听到的声音频率在20HZ~20kHz之间的声波。声音的三要素：1、音量（Volume）也叫做响度（Loudness）&... 查看详情
2021超全大数据面试宝典，吐血总结十万字，大数据面试收藏这一篇就够了
本文最新版已发布至公众号【五分钟学大数据】获取此套面试题最新pdf版，请搜索公众号【五分钟学大数据】，对话框发送 面试宝典扫码获取最新PDF版：版本时间描述V1.02020-02-18创建V1.22020-06-17新增spark、flink相关面... 查看详情
想了解数据库领域的“世界杯”tpc-c,看完这一篇就够了
引子两个多月前的一则消息刷爆朋友圈：阿里数据库OceanBase刷新尘封九年的世界纪录并赢得冠军。那这个数据库的世界纪录TPC-C到底是啥？TPC-C到底是个啥？要说TPC-C，得先了解一下TPC。TPC即国际事务处理性能委员会（TPC，Transacti... 查看详情
万字长文系统讲解模型特征选择方法，这一篇就够了！(代码片段)
上个月扫读完《阿里云天池大赛赛题解析》[1]后，看到书中对特征选择的讲述，于是便打算借此机会，系统梳理下各种特征选择方法。今天正好有时间进行梳理，内容较长建议慢慢品读，欢迎收藏、喜欢点赞... 查看详情
python虚拟环境和包管理工具pipenv的使用详解--看完这一篇就够了(代码片段)
前言Python虚拟环境是一个虚拟化，从电脑独立开辟出来的环境。在这个虚拟环境中，我们可以pip安装各个项目不同的依赖包，从全局中隔离出来，利于管理。传统的Python虚拟环境有virtualenv，使用pipfreeze→requirements.txt导出依赖... 查看详情
学习numpy这一篇就够了!含泪硬肝万字总结~(代码片段)
高效学习NumPy基础创建数组numpy.array(object，dtype，copy，order，subox，ndmin)numpy.arange(start，stop，step，dtype)numpy.linspace(start，stop，num)nu 查看详情
c语言入门到精通，这一篇就够了（13万字笔记）(代码片段)
友情提示：先关注收藏，再查看，13万字保姆级C语言从入门到精通教程。文章目录计算机常识什么是计算机程序?什么是计算机语言?常见的计算机语言类型有哪些?什么是C语言?C语言历史C语言标准C语言现状为什么要学... 查看详情