【数据结构 | 入门】堆栈与队列（问题引入&实现&算法优化）
【数据结构 | 入门】堆栈与队列（问题引入&实现&算法优化）
🤵♂️ 个人主页: @计算机魔术师 👨💻 作者简介：CSDN内容合伙人，全栈领域优质创作者。
文章目录
一、堆栈引入
计算机如何进行表达式求值
由于表达式符号是有优先级的，所以这是难点之一
有以下两个表达式
显然后缀表达式更加简单，不用考虑优先级，演示一个例子
对这种求值策略我们有以下启示
这其实便是这节我们要讲的堆栈
二、 堆栈的抽象数据类型描述
例如我们叠在一起的碗，在使用的清洗都和堆栈的规则
如下图是堆栈的变化图
其中
三、堆栈的顺序存储实现
3.1主要操作的实现
入栈
出栈
我们看一个例子
如果简单的将数组对半分，同时从左边往右边存放，那么会出现一个堆栈栈满，一个未满的情况，而此时数组还有空间，我们换一种思路，将两边往中间放
我们看看他们的操作
入栈
出栈
四、堆栈的链式存储结构
由于单链表的性质，我们将链表头作为堆栈指针Top，这样方便与插入删除操作，
push操作
pop操作
五、表达式求值
回到开头，我们再来 看表达式求值的问题，为了避免运算符中优先级的复杂性，我们使用后缀表达式，并使用堆栈来实现，我们把运算符和运算数丢进堆栈，当为运算符时，pop前两个运算数和运算符运算后再放入栈顶，最后栈顶的运算数便是结果
但我们平时所用的都是中缀表达式，所以我们如何把中缀表达式转换成后缀表达式，观察一个例子
其中存储运算符号的结构便是堆栈！那么如果有括号怎么办呢？ 看如下例子
其中运算数保留，遇到左括号时，直到遇到右括号才一直pop栈顶遇到左括号为止，并在括号内做优先级判断，总结如下
小练
除此之外，堆栈还有许多应用
比如函数调用，如果有一系列函数的调用，而我们要保留变量的状态和地址，要实现这些使用堆栈的，且递归函数也是如此，在回溯算法和深度优先搜索（递归）也是如此。
六、队列引入
如上可看到，队列顾名思义，像是平时排队一样，前头服务，后头排队，
七、队列的顺序存储实现
使用数组进行实现
有如下一个例子
我们以
作为队列为空的标志， 当添加一个工作时，Rear 加一，删除一个工作时，Front加一
此时队列末尾无法添加了，但实际前面还空着位置，那该如何处理呢？
我们把添加的队列放在Front前面的空位置上，这样就形成循环队列
但是这种方式在入队和出队会带来一个问题
我们观察如下：
数组长度为 n 那么Rear 和 Front 的距离为 0，1，2 ... n-1 总共n种可能，而作为队列装载元素有多少种情况呢？ 有 0,1,2,3,4...n 总共n个装载状态，而装载状态是由 Rear 和 Front 的距离所决定，n种状态无法表达n+1种状态，所以一定会矛盾
解决方法：
- 使用额外的标记：
Size或者tag域 - 仅使用
n-1个数组空间
1）入队列
这里的方法使用了求余方法，使得rear总在 0 ~ MaxSize 中，其中MaxSize是数组长度,当添加一个长度后求余得到结果与队头位置一样，则队列满，
2） 出队列
同样的，首先判断是否为空，不为空，则front往后移动
七、队列的链式存储实现
使用单链表进行实现
对应结构实现，其中队尾的队头指向对应链表首尾
不带头节点的出队操作
当队列只有一个元素，删除时则首位置空，多个元素删除释放空间， 按照这种规则，做入队操作也是如此，添加一个结点，让链表尾指针和rear指向
✨谢谢你的阅读，您的点赞和收藏就是我创造的最大动力！✨腾讯云开发者
