如何使用栈来浏览器的前进和后退功能？

栈是什么？

堆栈（英语：stack）又称为栈或堆叠，是计算机科学中的一种抽象数据类型，只允许在有序的线性数据集合的一端（称为堆栈顶端，英语：top）进行加入数据（英语：push）和移除数据（英语：pop）的运算。因而按照后进先出（LIFO, Last In First Out）的原理运作。

在这种数据结构中，数据像积木那样一层层堆起来，后面加入的数据就放在最上层。使用的时候，最上层的数据第一个被用掉，这就叫做"后进先出"。

堆栈使用两种基本操作：推入（压栈，push）和弹出（弹栈，pop）：

推入：将数据放入堆栈顶端，堆栈顶端移到新放入的数据。

弹出：将堆栈顶端数据移除，堆栈顶端移到移除后的下一笔数据。

堆栈的基本特点：

• 先入后出，后入先出。

• 除头尾节点之外，每个元素有一个前驱，一个后继。

通俗来讲：我们平时放盘子的时候，都是从下往上一个一个放；取的时候，我们也是从上往下一个一个地依次取，不能从中间任意抽出。

堆栈的实现

堆栈可以用数组和链表两种方式实现，一般为一个堆栈预先分配一个大小固定且较合适的空间并非难事，所以较流行的做法是Stack结构下含一个数组。如果空间实在紧张，也可用链表实现，且去掉表头。

栈在表达式求值中的应用

利用栈（stack）计算加减乘除四则运算，比如34+13*9+44-12/3。

计算流程

• 新建x,y两个空栈，x存储数字，y存储运算符号

• 从左到右遍历表达式，遇到数字时，直接push到x栈；

• 遇到运算符，和y栈的栈顶元素进行比较。

• 如果y栈栈顶元素为空，直接压入栈，

• 如果比y栈栈顶元素的优先级高，直接压入栈，

• 如果比y栈栈顶低或者相同，从y栈取栈顶运算符，从x栈的栈顶取2个操作数，然后进行计算，把计算完的结果压入到x栈，继续比较。

栈在括号匹配中的应用

除了用栈来实现表达式求值，我们还可以借助栈来检查表达式中的括号是否匹配。

我们同样简化一下背景。我们假设表达式中只包含三种括号，圆括号 ()、方括号 [] 和花括号{}，并且它们可以任意嵌套。如：

• {[{}]}或 [{()}([])] 等都为合法格式

• {[}()] 或 [({)] 为不合法的格式。

那我现在给你一个包含三种括号的表达式字符串，如何检查它是否合法呢？

使用栈解决方法：

•  新建一个空栈x，保存未匹配的左括号（包括 [{( ）

• 从左到右依次扫描字符串，当扫描到左括号时，则压入x栈中

• 当扫描到右括号时，从x栈顶去除一个左括号，进行判断，如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。

• 在扫描过程中，遇到不能配对的括号，或者是x栈中没有数据，那么该数据为非法数据。

• 字符串扫描结束后，如果栈为空，则说明字符串为合法字符串；否则，说明有未匹配的左括号，为非法格式。

如何实现浏览器的前进和后退功能？

• 新建两个栈，x和y；x 负责存储打开过的网址，后退的网址，y负责存储点击前进时浏览的网址。

• 当浏览器浏览的网址依次压入栈x，当点击后退按钮时，依次从栈x出栈，同时并将出栈的数据依次放入栈y.

• 当我们点击前进按钮时，依次从栈Y中取出数据，同时放入栈x中。

• 当栈x没有数据时，代表页面没有可以继续后退浏览

• 当栈Y没有数据时，代表页面没有可以点击前进按钮浏览

leetcode上关于栈的题目

20,155,232,844,224,682,496.

参考：

https://www.ruanyifeng.com/blog/2013/11/stack.html

https://zh.wikipedia.org/zh-hans/%E5%A0%86%E6%A0%88
https://time.geekbang.org/column/article/41222