栈
大约 1 分钟
栈
先进后出，只允许在一端插入和删除数据的线性表
当某个数据集只涉及在一端插入和删除数据，并且满足后进先出，先进后出的特性，首选栈
如何实现一个栈
- 顺序栈： 数组实现栈
- 链式栈：用链表实现
栈在函数调用中的应用
例如栈帧
栈在表达式求值中的应用
通过两个栈来实现，一个保存操作数的栈，另一个保存运算符的栈。从左到右遍历表达式，当遇到数字直接压入操作数栈，遇到运算符就与运算符栈的栈顶元素比较，如果比运算符栈顶元素的优先级高，就将当前运算符入栈；如果比栈顶元素的优先级低或者相同，就从运算符栈中取栈顶运算符，从操作数栈的栈顶取两个操作数，然后进行计算，再把计算完的结果压入操作数栈。
栈中括号匹配中的应用
当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，则继续扫描剩下的字符串，如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。当所有的括号都扫描完成之后，如果栈为空，则字符串合法，否则非法