栈

• 特点：先进后出，后进先出

• 数组实现叫顺序栈，链表实现叫链式栈

-复杂度

• 出栈：时间复杂度是O(1)
• 栈入：固定大小栈时间复杂度是O(1)，支持动态扩容栈的平均复杂度是O(1)
• 空间都是O(n)

应用

编辑器利用栈实现表达式求值

编辑器通过两个栈实现，一个保存操作数，一个保存运算符，如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算，再把计算完的结果压入操作数栈，继续比较。

image.png

栈在括号匹配中的应用

我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。

浏览器的前进和后退

用两个栈实现，一个栈保存前进页面，一个栈保存后退页面