…

本文已收录至：数据结构 | C语言
更多知识尽在此专栏中!

文章目录

前言
正文
- 栈
- - 结构
  - 初始化
  - 销毁
  - 入栈、出栈
  - 查看栈顶元素
  - 查看栈内有效元素
  - 判断栈是否为空
- 队列
- - 结构
  - 初始化
  - 销毁
  - 入队、出队
  - 查看队头、队尾元素
  - 查看队内有效元素
  - 判断队是否为空
- 源码区
- - 栈
  - 队列
- 相关OJ试题推荐
总结

前言

栈（Stack）又名堆栈，它是一种运算受限的线性表，限定仅在表尾进行插入和删除操作的线性表。队列（Queue）也是一种特殊的线性表，特殊之处在于它只允许在表的前端（Front）进行删除操作，而在表的后端（Rear）进行插入操作，和栈一样，队列 的部分操作也会受到限制。栈 的特点是先进后出（FILO），队列 则是先进先出（FIFO），本文将会通过顺序存储的方式模拟实现 栈，以及链式存储的方式模拟实现 队列，两种数据结构都比较简单，一起来看看吧！

正文

栈

首先介绍 栈 的实现，栈 非常适合通过 顺序表 来模拟实现，因为 顺序表 尾插、尾删的复杂度是O(1)，并且 栈 的插入、删除都是在 栈顶 完成的，因此我们可以去除 顺序表 的部分功能，这样就可以得到一个 栈

有人将栈形象的比作弹匣，装弹是在入栈，而将子弹射出则是在出栈，显然最先进入弹匣的子弹，将会在最后才被射出，准备的动图发不出来，可以自行百度查看

结构

既然可以通过 顺序表 实现 栈 ，那么 栈 的结构自然就和 顺序表 差不多了，都有一个 负责指向存储数据的指针 ，一个 下标(栈顶) 和容量，因为 顺序表要求空间必须是连续的，因此后续需要进行动态内存开辟，而容量是不能少的

typedef int STDataType;//栈的元素类型typedef struct StackInfo{STDataType* data;//数据int top;//栈顶int capacity;//容量}Stack;

初始化

初始化需要把 指针 data 置空，栈顶值 top 和 容量值 capacity 归0

当然这里的栈顶也可以置为-1，当我们取栈顶元素时，取的就是当前栈顶处的元素
如果是归0，那么取的就是栈顶-1处的元素
推荐归0，因为在后续操作中比较省事

void StackDestroy(Stack* ps)//栈的销毁{assert(ps);//只有为栈开辟空间了，才能正常销毁if (ps->data){free(ps->data);ps->data = NULL;ps->top = ps->capacity = 0;}}

销毁

销毁 栈 需要明白一点：是否可以销毁 ，因为可能会出现不插入元素的情况下，结束程序，此时如果继续执行销毁，就会发生空指针的解引用情况

void StackDestroy(Stack* ps)//栈的销毁{assert(ps);//只有为栈开辟空间了，才能正常销毁if (ps->data){free(ps->data);ps->data = NULL;ps->top = ps->capacity = 0;}}

入栈、出栈

顺序 栈 的 入栈、出栈 很简单，可以放一起介绍

入栈
- 确保有空间可以使用，因此需要借助扩容程序段
- 直接将目标值插入到栈顶处
- 最后栈顶+1，此时的栈顶代表着 栈 中的有效元素个数

void StackPush(Stack* ps, STDataType x)//入栈{assert(ps);//判断栈是否满if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 " />
 
 出栈   出栈需要确保 栈 内有元素可出
如果 栈 为空，是不能执行出栈的
出栈不需要将元素抹掉，直接栈顶-1，无法访问到此元素就行了
 
 void StackPop(Stack* ps)//出栈{assert(ps);assert(ps->top > 0);//有元素才能出栈//出栈，直接栈顶-1ps->top--;}
查看栈顶元素
前面说过，栈顶值 top-1 代表的就是当前栈顶元素，前提是有元素存在，因此这个函数就很简单了，直接先判断 栈 是否为空，如果不为空，返回 栈顶-1 处的元素值就行了
STDataType StackTop(Stack* ps)//查看栈顶元素{assert(ps);assert(ps->top > 0);//有元素才能看//栈顶元素，在栈顶-1处，因为栈顶是从0开始的return ps->data[ps->top - 1];}
查看栈内有效元素
所谓栈内有效元素，就是顺序 栈 的长度，也就是 栈顶值 top ，此时就体现出 栈顶值 从0开始的好处了，做什么都很方便，比如这里，直接返回 栈顶值 就行了
int StackSize(Stack* ps)//查看栈的有效元素个数{assert(ps);//栈的大小就是当前栈的有效元素个数return ps->top;}
判断栈是否为空
判断栈是否为空，太简单了，一行代码解决
返回的是布尔值，需要引头文件 stdbool.h
因为判断式返回值是布尔类型如果栈顶值为0，说明栈空，判断式为真，返回 true
否则说明栈不空。判断式为假，返回 false
bool StackEmpty(Stack* ps)//判断栈是否为空{assert(ps);//栈顶为0.说明栈空return ps->top == 0;}
顺序 栈 也就这点东西，我愿称之为顺序表青春版，所有源码放在gitee上了，可以跳转到源码区传送过去
下面是程序运行图(测试的时候手速太快了，所以有的地方可能看不太清楚)
 这是一张动图，时长56秒
 
队列
队列 的特点是先进先出，主要功能是头部删除和尾部插入，因为队列比较特殊，如果采用 顺序表 的形式实现的话，容易出现 假溢出 问题（后续解决 循环队列 问题会用 顺序表 模拟实现），因此我们这里采取 链表 的形式模拟实现 队列
分析得出队列的 需求 如下
单链表就足够了，多加一个队尾指针，可以有效避免效率问题
哨兵位（可要可不要），因为待会实现时，是结构体嵌套结构体的形式
使用非循环的链表，没必要使用双向带头循环链表（小题大做）
结论
最简单的单链表就可以实现
因为有队头、队尾两个指针，因此需要使用结构体嵌套的方式
 
结构
单链表 最大的缺陷就是不好找尾，为此我们直接通过结构体嵌套定义的方式，定义 队头指针 front 、队尾指针 rear 和 队列长度 size，这样一来，所有涉及队列的操作，都是在以 O(1) 效率执行，灰常高效，就是比较难理解
帮助理解
假设队列中的节点是一个个链接的小球
存在一个大外壳装着这些小球
并且有两个警卫分别守着球头和球尾，还有一个秘书帮忙记录球数
当然它们的作用是为了更好的管理小球
显然，front 和 rear 就是两个警卫，而 size 是秘书
typedef int QListDataType;//队列的数据类型//这是队列中，单个节点的信息typedef struct QListNode{QListDataType data;struct QListNode* next;}QNode;//这是整个队列的信息，包含了队头和队尾两个指针typedef struct QueueNode{QNode* front;//队头指针QNode* rear;//队尾指针size_t size;//队列长度}Queue;
初始化
队列 的初始化很直接，把 队尾、队头指针 置空，长度 置0就行了
void QueueInit(Queue* pq)//队列的初始化{assert(pq);//初始化状态：队头、队尾指针都指向空，队列大小为0pq->front = pq->rear = NULL;pq->size = 0;}
销毁
队列 销毁原理，和 单链表 的销毁差不多，需要借助一个 临时指针 cur ，指向当前队头，然后 队头指针 front 移向下一个位置，销毁 临时指针 cur ，如此循环，直到 临时指针 cur 指向 NULL ，此时整个 队列 都会被销毁
队列 不需要像 栈 那样做特殊处理，因为当队空时，cur 一开始就为空，循环是进不去的
当然销毁后，两个指针都要置空，size 也要归零
void QueueDestroy(Queue* pq)//队列的销毁{assert(pq);//销毁思路：利用临时指针进行销毁QNode* cur = pq->front;while (cur){QNode* tmp = cur->next;free(cur);cur = tmp;}pq->front = pq->rear = NULL;pq->size = 0;}
入队、出队
有了 队头、队尾 两个指针，入队、出队就很简单了，直接易如反掌
入队
即单链表的尾插
买一个新节点，存放目标值，将 队尾指针 与新节点链接起来注意：如果是第一次入队，直接赋值，而不是链接
更新 队尾指针 ，队尾指针 变成了新节点
队列长度 + 1
void QueuePush(Queue* pq, QListDataType x)//入队{assert(pq);//先买一个节点QNode* newnode = buyNode(x);//分情况：如果队头为空，说明队空，此时直接将新节点赋值给队头、队尾if (pq->front == NULL){pq->front = pq->rear = newnode;pq->size++;}else{//否则就是将新节点，链接到队尾，然后更新队尾pq->rear->next = newnode;//链接pq->rear = newnode;//更新队尾pq->size++;}}
出队
即单链表的头删
利用临时指针，存储当前 队头指针 的信息
队头向后移动，即更新 队头指针
释放临时指针
队列长度 - 1
void QueuePop(Queue* pq)//出队{assert(pq);assert(!QueueEmpty(pq));//如果队空，是不能出队的//出队思想：有元素才能出队，更新队头，销毁原队头QNode* cur = pq->front;pq->front = pq->front->next;//更新队头指针free(cur);cur = NULL;pq->size--;}
查看队头、队尾元素
这两个都是甜品函数，直接一行代码解决
查看队头
判断队列是否为空
不为空才能查看，队头元素为 队头指针 的指向值
QListDataType QueueFront(Queue* pq)//查看队头元素{assert(pq);assert(!QueueEmpty(pq));return pq->front->data;}
查看队尾
同样需要判断队列是否为空
不为空才能查看，队尾元素为 队尾指针 的指向值
QListDataType QueueRear(Queue* pq)//查看队尾元素{assert(pq);assert(!QueueEmpty(pq));return pq->rear->data;}
查看队内有效元素
队列中的有效元素数，就是之前一直默默工作的 队列长度 size，直接返回它的值就好了，没什么技巧
至于为何不通过遍历的方式确定有效元素数
时间成本太高，如果队列中有10w个元素，那么在调用此函数时，会很浪费时间
结构设计时 size 的加入，能很好的避免这个问题，因为 size 在改变时，总是伴随着入队或出队，默默记录，效率是很高
int QueueSize(Queue* pq)//当前队列的有效元素数{assert(pq);return pq->size;//直接返回就行了}
判断队是否为空
此时判断队列是否为空，有多种方法
通过 size 判断，为0，说明队列为空
通过 队头指针 或 队尾指针 判断，为空说明队空
这里使用第二种方法，通过 队头指针 进行判断
 当然，返回值是 布尔值 ，同样是利用了判断式的返回值
bool QueueEmpty(Queue* pq)//判断当前队空情况{assert(pq);return pq->front == NULL;}
至此，队列 结束，结构体嵌套 也就是个纸老虎，实际还没有 二级指针 复杂，可以把 链队列 看作 单链表 的青春版
下面是程序运行图，同样是动图，可以耐心看完
 
源码区
注意：为了避免文章过长，现采取 Gitee 仓库分享代码的形式，秉持开源精神，所有代码都可参考!
栈
这是属于栈的文件夹
队列
这是属于队列的文件夹
相关OJ试题推荐
一如既往的OJ试题推荐环节，这次是 栈和队列 专场
20.有效的括号
225.用队列实现栈
232.用栈实现队列
622.设计循环队列(中等)
总结
栈和队列 是两种比较特殊的数据结构，在实际中往往很少单独去使用，都是用来配合实现其他数据结构，比如 二叉树 的 层序遍历 中会用到 队列 ，很多OJ试题也会爱考这两种数据结构，因此学好它们还是很重要的
如果你觉得本文写的还不错的话，期待留下一个小小的赞，你的支持是我分享的最大动力！
如果本文有不足或错误的地方，随时欢迎指出，我会在第一时间改正
…
 相关文章推荐
 数据结构 | 顺序表
 数据结构 | 时间复杂度与空间复杂度
 数据结构 | 单链表

数据结构 | 栈和队列

文章目录

前言

正文

栈

结构

初始化

销毁

入栈、出栈

查看栈顶元素

查看栈内有效元素

判断栈是否为空

队列

结构

初始化

销毁

入队、出队

查看队头、队尾元素

查看队内有效元素

判断队是否为空

源码区

栈

队列

相关OJ试题推荐

总结

`最新关注`

`热文推荐`

`关于Warning：Implicit declaration of function “xxx” is invalid in C99警告！`

`MongoDB和MongoDB Compass的安装配置教程`

`VScode使用clang format文档自动代码格式化（C语言）`

`区块链安全入门基础`

`【 Vue3 + Vite + setup语法糖 + Pinia + VueRouter + Element Plus 第三篇】(持续更新中)`

`实时聊天系统`