共计 1737 个字符，预计需要花费 5 分钟才能阅读完成。
简介
基本概念
从栈的操作个性来看，栈是一种操作受限的线性表，只容许在一端插入和删除数据。
事实上，从性能上来说，数组和链表齐全能够代替栈的应用。然而，从某种角度来说，数组和链表裸露太多的操作接口，实现起来比较复杂，也很容易出错。
因而，当数据汇合只波及在一端插入和删除数据，并且满足先进后出、后进先出的个性，能够首选“栈”这种数据结构。
操作
栈是容许在同一端进行插入和删除操作的非凡线性表。以下是栈的一些概念：
- 容许进行插入和删除操作的一端称为 栈顶，栈顶会依据插入、删除操作进行浮动
- 不容许进行插入和删除操作的一端称为 栈底，栈底是固定不变的
- 栈中元素个数为零时称为 空栈
- 往栈中插入元素称作 进栈
- 删除栈顶的元素称作 出栈
栈的实现
实际上，栈既能够用数组实现，也能够用链表实现。应用数组实现的栈被称为程序栈，应用链表实现的栈被称为链式栈。
程序栈
应用数组作为栈存储数据的物理存储构造，须要先申请一个大小为 n 的数组。
将数组尾部作为栈顶，应用一个变量示意数组存储的元素个数，这样入栈、出栈的操作都能达到 $O(1)$ 的工夫复杂度。
基于数组实现的栈存在一个限度，即数组在申明之后是固定大小的，当栈满的时候，则无奈再次往数组中增加数据。这样就波及到对数组进行动静扩容，当数组空间不够的时候，须要从新申请一块更大的内存，将原来数组中数据通通拷贝过来。
事实上，反对动静扩容的程序栈，在理论开发中并不常见。个别应用到程序栈这种数据结构的状况，都是一些规模比拟小的数据，有时候晓得数据的最大规模时也能够防止爆栈。
链式栈
对于数据规模比拟大的状况，应用链表实现栈则会更加不便。这时候，不须要提前申请内存空间，而是创立一个哨兵结点指向头结点。
链式栈个别会应用头插法创立链表。将头结点作为栈顶，每次入栈都当作链表在头结点插入元素，每次出栈都当作链表删除头结点，这些操作都只须要解决好哨兵结点的指向即可。链式栈个别都能达到 $O(1)$ 的工夫复杂度。
基于链表实现的栈不须要像数组一样要动静扩容，链表是天生反对动静扩容的。
利用场景
栈作为一个比拟根底的数据结构，利用场景还是蛮多的。
函数调用栈
函数调用栈是一个十分经典的利用场景。
操作系统给每个线程调配了一块独立的内存空间，这块内存被组织成“栈”这种构造，用来存储函数调用时的长期变量。每进入一个函数，就会将长期变量作为一个栈帧入栈，当被调用函数执行实现，返回到下层函数之后，再将这个函数对应的栈帧出栈。
直到函数栈为空，则示意最外层的函数曾经执行结束。
逆波兰表达式
编译器还会利用栈来实现表达式求值，这部分也有十分成熟的四则运算算法——逆波兰表达式。
通常的四则运算表达式写成 (1 + 2) x (3 + 4)，加减乘除等运算符写在两头，因而也被称作“中断表达式”；逆波兰表达式的写法是 1 2 + 3 4 + x，运算符被写在前面，因此也被称作“后缀表达式”；除此之外，还有波兰表达式，其写法是 x + 1 2 + 3 4，也被称作“前缀表达式”。
如果将表达式画出一棵语法树，就能以树的概念来直观了解前缀、中断、后缀的含意，前缀表达式对应树的前序遍历，中断表达式对应树的中序遍历，后缀表达式对应树的后序遍历，如下图所示：
首先，须要先将中断表达式转换成逆波兰表达式，波及到操作数栈和运算符栈：
- 从左向右遍历中断表达式；
- 若读取的是操作数，将操作数存入到操作数栈中；
若读取的是运算符，还须要依据运算符类型进一步判断：
- 如果是
(运算符，则间接存入运算符栈中； - 如果是
)运算符，则输入运算符栈中的运算符到操作数栈，直到遇到(运算符，在这里放弃(和)运算符； 如果是非括号运算符，还须要与运算符栈栈顶的运算符比拟优先级：
- 如果运算符栈栈顶的运算符是括号，则间接存入运算符栈中；
- 如果此运算符比运算符栈栈顶的运算符优先级更高时，则间接存入运算符栈中；
- 如果此运算符比运算符栈栈顶的运算符优先级更低或相等时，则输入栈顶运算符到操作数栈，而后将以后运算符压入操作符栈；
- 如果是
- 当表达式读取完后，将运算符栈顺次取出到操作数栈中，直到运算符栈为空。
而后对失去的逆波兰表达式计算，失去表达式的后果：
- 从左向右遍历逆波兰表达式；
- 若读取的是操作数，将操作数存入栈中；
- 若读取的是运算符，则对栈顶的两个操作数执行该运算，而后将运算后果存入栈中；
- 反复上述的步骤 1~3，最终栈中即为后果值。
