导言：

在计算机发明之初是为了计算，所以叫计算机，对我们给定的一个算式，然后给定的一套规则 加，减，乘，除，等，它就可以自己进行计算了，然后返回一个结果给我们

对于一般的算式 ： 2+3+4 很显然，从左往右依次扫描，依次相加很简单的计算出来，因为它们是同级运算，可以很简单的做到

但是，常见的运算不只是 加法，还有乘除等，它们的优先级都是要高于加法的，如： 3+6*4/9  ，如果依次扫描，很显然6和4的乘法优先级更高，不能先3和6进行加法

当然，有问题的提出就有问题的解决：可以使用后缀表达式和栈结合来应对复杂的计算

一.简述栈

什么是栈？

栈 (Stack)是操作系统在建立某个进程时或者线程（在支持多线程的操作系统中是线程）为这个线程建立的存储区域，该区域具有FILO的特性，在编译的时候可以指定需要的Stack的大小

栈的特点：先进后出 ，即Frist IN Last Out（FILO）

栈这种数据结构就特别适合解决导言提出来的那种问题，对于复杂的计算，算式中带有优先级的符号，我们可以使用栈存储后缀表达式来计算

既然要用到后缀表达式，那么我们就需要把我们熟知的中缀表达式转换为后缀表达式才能计算

中缀表达式转后缀表达式

 我们这里使用的中缀表达式转后缀表达式的方法是，补填括号，如果运算有括号的部分就不需要自己添加了，要是无括号就需要添加

差不多有几个符号，最后填完括号后就是有几个括号，符号数和括号数对应

然后把符号移动到对应的括号外面，前缀和后缀表达式都是这样的，自己可以试试转换前缀表达式

最后要注意的就是，前后缀表达式是没有括号的，所以最后一步是去括号（即使中缀表达式自带的括号一样去掉）

栈和后缀表达式的结合计算

栈在这里是扮演的存储角色，我们在计算的时候会从左往右的依次进行入栈操作，是数字就入栈，是运算符号我们就需要从栈顶拿出两个元素计算，

但是记住，是有顺序的，栈顶的元素放右边，后面出来的元素放左边，符号放中间就可以计算了

栈的特点是先进的后出，后进的先出，不存在在栈中间的数据先出来的情况，所以依次出栈就能保证数据运算时逻辑顺序不会发生改变

我们接下来简单举例来看看这个运算：

 这就是我们使用栈结构来解决的导言中的比较复杂运算，这里我们就能很明显的知道栈的结构特点

栈结构使用最多的还是计算机底层的运算，比如，操作系统的中断系统中，操作系统做的断点记录是栈结构存储的，还有函数和主函数的调用方式，递归的实现，都是栈机制

对应的栈操作就两个：push （入栈），pop（入栈）

不管是出栈还是入栈它们都是原子操作，可以交叉的使用边出栈边入栈，也可以边入栈边出栈，但是在宏观上它们一定是有序的，不会有栈顶元素未出栈，栈底元素已出栈的情况

 二.栈的顺序存储实现

 第一种：基于结构体数组实现

栈的顺序存储通常是一个数组和一个记录栈顶元素的变量实现的

 这里我们使用的是int型数组，存储整型数据

top就是我们有数据数组的最大下标

 入栈的时候需要检查一下我们的栈是否为满的，如果不是满地还有空间那么就可以入栈，入栈的时候由于我们选用的数组存放，所以只需要把下标后移一个就够了

然后还要对记录栈顶的元素加一，这里代码中我们其实是两步一起做了的

 我们在出战的时候是有返回值的，一定要记得类型要和入栈的数据类型匹配上

然后就是出栈也需要判断栈是不是还有元素，没有就是出不了栈的

出栈完成了以后也需要把记录栈顶元素的变量减一

利用一个数组实现两个栈

 这是一个经典的栈空间划分问题，我们在拿到问题之后可能很多人都想到的是对半分，一半数组构成一个栈，理论上可以，但是实际上的开发不行，

因为两个栈的进入顺序其实是不一样的，那么就有可能会导致有一个栈已经满了，另外的一个栈还有大量空间，为了充分利用数组空间，对半分划分两个栈肯定是不合理的

后来我们想到可以使用数组的第一元素和最后一个元素作为两个栈的栈底，然后都向中间靠来存放数据，不在是对半分，当两个栈的栈顶指针相遇的时候就是栈满的时候

上面就是使用一个数组实现双栈的伪代码，主要是多了一个tag标记，它的意思是用来选择要操作那个栈的，我们现在不是有了两个栈嘛

包括入栈和出栈都要选择，如果选择错了很显然拿不到我们想要的结果的

使用这种方式构建的双栈有很高的利用率，不存在有内碎片的情况。 

 第二种：基于链式存储实现

栈的链式存储其实就是一个单链表，叫做链栈，插入和删除只能在栈顶实现，那么链表的top指针指向那一头呢？

我们可以先构造从链表的尾部开始做 top指针，插入的时候就在尾部连接链表的新结点，但是删除就有问题了，我们知道链表实现的栈是单链表它是没有回头指针的

也就是说，它只能找到它的下一个结点，但是找不到它的上一个结点，单链表有 Next指针，但是没有 last指针，在删除的时候肯定要回到上一个结点做尾结点，所以链表的尾部被pass掉

再来看看使用链表的头部做top指针，每新来的结点都直接连接到已有的链表的后面，可以实现，删除一个结点也就是头部结点的next不需要了，连接到下下个结点去，可以实现

所以我们选用头部结点来做top指针，这里我们需要注意的是我们要专门构造一个头部结点，它不存放数据，只用来连接新数据和删除数据，它不管怎么更改始终是链表的第一个结点，使用这个结点来做 top指针

 这里的head头结点就可以充当top指针

我们再来看看对链表结构体的定义，由于链表是动态申请，故而没有固定大小

 从结构体种我们可以看到，有装数据的Data类型，还有一个结构体指针，指向的是下一个结构体，利用链表来做栈结构首先要申请一个头结点用于做top指针，这一步也可以叫初始化，

 这里式伪代码实现的链式栈结构实现入栈和出栈

入栈的时候要注意每次申请一个新的结点，链表的插入实际上是结点的插入，结点上带了数据和下一个结点的位置

因为链式存储，它的大小是在不断地申请中产生的所以它是没有栈满这个问题的，可以说只要操作系统给你多少内存，你可以一直申请到撑爆它。

然后就是出栈，出栈是需要检查一下有没有结点的，可能没有插入，在出栈的时候需要释放刚刚的内存，所以需要一个指针还没执行断链的时候就指向它

等断链以后，数据也备份到返回的临时变量了，就可以释放出栈元素原来所占用的内存了，有申请有释放，主打一个规范

 入栈图示：

 出栈图示：

 三.栈的简单应用

我们在简述栈的时候就已经了解过了，对于中缀表达式转后缀表达式的方法，当时我们使用的是加括号，然后通过我们人可理解的方式来解决的，

加括号可以快速的把中缀表达式转换为前后缀表达式，但是这是我们人才能做到这么快，但是机器呢？

对于计算机，他无法根据此规则加上相应的括号，然后移动符号，最后去掉括号，但是计算机它有一套自己的实现方法，也是通过栈来实现的

 通过上面的计算，利用栈的转存就可以很轻松的计算出后缀表达式，当然他必须要满足相应的一些规则：

中缀表达式从左向右扫描

• 遇到运算数字就直接输出
• 左括号在栈外的时候优先级最高，直接压入栈中，在栈内优先级最低
• 遇到右括号后，直接把左括号上的符号依次出栈，但是左右括号不需要再带上了
• 其它运算符，只要优先级高的就入栈，比栈内的低的，栈内的弹出，然后与栈内继续比较，同级的也是栈内的先弹出，然后栈外的入栈
• 对象扫描完以后，需要把栈内的残余的运算符顺序输出

小结：

上面的操作并不是栈最常用的操作，栈作为最早出现的数据结构之一，其特点被大量的用在了底层中，操作系统中栈内存是不可或缺的一份子，它对断点的记录有着离奇好的效果，

广泛用于操作系统的断点记录，函数回溯参数还原

包括整个递归思想都是在栈机制上建立起来的，如果没有栈机制，递归的思想可能很难被实现出来

图的深度优先探索，都需要栈来记录它刚刚经过的地方，在道路不可达的时候，需要回到栈记录原来的地方

回溯算法等等

-

-

-

-

-

-

博客编辑于

---------------------浙江大学陈越老师《数据结构与算法》