数据结构与算法：栈的应用场景

一、概念

先进后出，后进先出。只允许在一段插入和删除操作。
**栈的实现：**用数组实现的栈叫顺序栈，用链表实现的栈是链式栈。
大部分情况下，入栈操作的时间复杂度 O 都是 O(1)，只有在个别时刻才会退化为 O(n)，出栈时间复杂度为O(1)

二、应用

1、函数调用中的应用

操作系统会给每个线程分配一块内存空间，这块内存被组织成栈结构，每进入一个函数，都会将临时变量作为栈帧入栈；
当被调用函数执行完成返回后，将这个函数对应的栈帧出栈。

2、栈在表达式求值中的应用

编译器通过两个栈来实现，一个栈用来保存操作数，一个栈用来保存运算符。
从左到右遍历表达式，当遇到数字，压入操作数栈，当遇到运算符，与运算符栈栈顶进行比较
如果比运算符栈顶元素优先级高，就将当前运算符压入栈。否则从运算符栈中取栈顶运算符，从操作符栈中取两个数进行计算，把运算结果压入操作数栈，继续比较。

三、栈在括号匹配中的应用

假设表达式中只包含三种括号，圆括号 ()、方括号[]和花括号{}，并且它们可以任意嵌套。比如，{[] ()[{}]}或[{()}([])]等都为合法格式，而{[}()]或[({)]为不合法的格式。
我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。

四、如何实现浏览器前进和后退

比如顺序看了abc三个页面，一次把abc压入栈x

当你后退，从c页面退到a，我们依次把cb取出，放入到y栈

当你又想看页面b时，将b从y栈弹出，放入x栈

这时候你通过d页面访问新页面d，页面c就不可以通过前进后退进行访问，需要清空y栈