栈：如何实现浏览器前进后退功能
如何理解栈
栈就是一个后入先出，先入后出的数据结构。
从操作特性上看，栈是一种操作受限的线性表，只允许在一端插入和删除数据。
虽然使用数组和链表能够替代栈这种数据结构，但是数组与链表向外暴露了太多的api接口，操作上面虽然自由，但是使用的时候就比较不可控，自然也就更容易出错。
当某个数据集合只涉及在一端插入和删除操作，并且满足先入后入，后入先出特性，我们应该选择栈这种数据结构。
如何实现一个栈？
栈总共就两个数据结构，一个是出栈，一个是入栈。我们只需要实现这两个即可。
栈可以使用数组或者链表来实现。
- 使用数组实现的栈叫做顺序栈
- 使用链表实现的栈叫做链式栈
顺序栈的实现如下图所示：
public class ArrayStack {
String[] arrayStack;
int count;
int n;
ArrayStack(int num) {
arrayStack = new String[num];
count = num;
n = 0;
}
public String pop() {
if (n == 0){
return null;
}
//先取值，然后再进行自减操作
return arrayStack[n--];
}
public boolean push(String item) {
if (n >= count){
return false;
}
//先赋值，然后再进行自增操作
arrayStack[n++] = item;
return true;
}
}
链式栈的实现如下图所示：
public class LinkedStack {
private Item dummy = new Item("dummy");
//作为栈中最后一个节点
private Item head;
LinkedStack() {
head = dummy;
}
boolean pop() {
if (dummy.next == null) {
return false;
} else {
head = head.before;
head.next = null;
return true;
}
}
boolean push(String val) {
Item item = new Item(val);
item.next = null;
item.before = head;
head.next = item;
head = head.next;
return true;
}
}
class Item {
String val;
//使用双向链表来处理pop
Item next;
Item before;
Item(String val) {
this.val = val;
}
}
其时间、空间复杂度都为。
支持动态扩容的顺序栈
上面所写的栈是不支持动态扩容的，如果增加的item的个数超过了栈的大小，则会报错。
我们使栈动态扩容的方法很简单，因为顺序栈的底层是数组，当超过数组的范围时，新建一个两倍原来大小的数组，然后将数据复制过去就可以了。
动态扩容的顺序栈
时间复杂度很好计算。只有在添加第n + 1个数据的时候才需要进行
方法栈帧
栈在表达式求值中的应用
编译器通过两个栈来实现表达式求值。
一个栈用来保存操作数，一个栈用来保存操作符。
从左往右遍历表达式的时候，遇到操作数则将其入栈，遇到操作符，则将其与操作符栈最顶端的元素进行比较，如果其比最顶端的操作度等级高（例如乘除比加减高），则将其入栈，如果比其低，将最顶端的元素取出来，然后操作数栈最顶端的两个元素也取出来进行计算，将得到的结果压入操作数栈，然后将操作符继续比较。
一图胜千言
栈在表达式求值中的应用
栈在括号匹配中的应用
同在表达式中的应用一样，我们使用一个栈来保存左括号。遇到左括号就添加到栈顶。如果遇到右括号，则从栈顶到栈底遍历，如果某一括号与右括号类型相同，则把这个括号移除，不再往下遍历，同时继续寻找字符串中的下一个括号。如果字符串遍历到底，栈中仍然有括号，说明该字符串括号不匹配，如果栈为空，则说明匹配。
如何实现前进后退功能
首先我们分析该功能需要实现的几个场景：
- A 点击进入 B， B能够返回到A， A能够前进到B
- A点击进入 B, B点击进入C， C返回到B后，B点击进入D，此时D返回到B，B返回到A。
我们可以使用两个栈，一个用来存储已经点击进入的网页叫后退栈，一个用来存储后退时网页栈pop掉的网页叫前进栈。
第一个场景只需要进行普通的push、pop操作就行了。
第二个场景则需要特殊处理，如果回退到某一网页然后点击新的网页的话，后退栈正常操作，但是前进栈需要清空，然后添加这个新网页。
