【数据结构 | 入门】堆栈与队列（问题引入&实现&算法优化）

在这里插入图片描述

🤵‍♂️ 个人主页: @计算机魔术师 👨‍💻 作者简介：CSDN内容合伙人，全栈领域优质创作者。

文章目录

• 一、堆栈引入
• 二、 堆栈的抽象数据类型描述
• 三、堆栈的顺序存储实现
• • 3.1主要操作的实现
• 四、堆栈的链式存储结构
• 五、表达式求值
• 六、队列引入
• 七、队列的顺序存储实现
• • 1）入队列
  • 2） 出队列
• 七、队列的链式存储实现

一、堆栈引入

计算机如何进行表达式求值

在这里插入图片描述

由于表达式符号是有优先级的，所以这是难点之一

在这里插入图片描述

有以下两个表达式

在这里插入图片描述

显然后缀表达式更加简单，不用考虑优先级，演示一个例子

在这里插入图片描述

对这种求值策略我们有以下启示

在这里插入图片描述

这其实便是这节我们要讲的堆栈

在这里插入图片描述

二、 堆栈的抽象数据类型描述

在这里插入图片描述

例如我们叠在一起的碗，在使用的清洗都和堆栈的规则

在这里插入图片描述

如下图是堆栈的变化图

在这里插入图片描述

其中

在这里插入图片描述

三、堆栈的顺序存储实现

在这里插入图片描述

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种状态，所以一定会矛盾

解决方法：

1. 使用额外的标记：Size或者tag域
2. 仅使用n-1个数组空间

1）入队列

这里的方法使用了求余方法，使得rear总在 0 ~ MaxSize 中，其中MaxSize是数组长度,当添加一个长度后求余得到结果与队头位置一样，则队列满，

在这里插入图片描述

2） 出队列

同样的，首先判断是否为空，不为空，则front往后移动

在这里插入图片描述

七、队列的链式存储实现

使用单链表进行实现

在这里插入图片描述

对应结构实现，其中队尾的队头指向对应链表首尾

在这里插入图片描述

不带头节点的出队操作

在这里插入图片描述

当队列只有一个元素，删除时则首位置空，多个元素删除释放空间， 按照这种规则，做入队操作也是如此，添加一个结点，让链表尾指针和rear指向

  ✨谢谢你的阅读，您的点赞和收藏就是我创造的最大动力！✨