[第四章] 栈

注：此专栏内容主要参考极客时间-数据结构与算法之美

1. 概念

• 后进者先出，先进者后出，这就是典型的“栈”结构；
• 栈是一种“操作受限”的线性表，只允许在一端插入和删除数据；
• 栈主要包含两个操作，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据；
• 用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈；
• 时间复杂度、空间复杂度都是O(1)；
  

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

• 编译器就是通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符
  的栈。我们从左向右遍历表达式，当遇到数字，我们就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。
• 如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；
• 如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。
  

3. 如何实现浏览器前进、后退

• 我们使用两个栈，X 和 Y，X存放访问过-待后退的页面，Y存放访问过-待前进的页面；
• 每次浏览新页面的时候，将之前浏览过的页面压入栈 X
• 点击后退按钮时，从栈 X 中出栈并浏览，并把当前页面放入栈 Y。
• 点击前进按钮时，从栈 Y 中出栈并浏览，并把当前页面放入栈 X。
• 当栈 X 中没有数据时，说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，说明没有页面可以点击前进按钮浏览了。