如何通过栈实现网页浏览器的后退和前进功能？
- 内容介绍
- 相关推荐
本文共计1629个文字，预计阅读时间需要7分钟。
浏览器的前进与后退功能，让用户轻松浏览历史页面。例如，我在浏览器操作了+a-b-c三个页面，点击后退按钮，就能查看之前浏览过的页面+b和a。
浏览器的前进与后退功能，大家肯定会熟悉吧。
比如我在浏览器操作了a->b->c三个页面，点击浏览器的后退按钮，就可以查看之前浏览器的浏览过的页面 b 和 a，当你后退到页面 a，点击前进时，你就可以拿到 b 跟 c。
如果你是谷歌工程师，你现在要如何实现这个功能？
"栈"其实很好理解，你就可以把他看做一叠盘子，你只能一个一个叠加盘子，或者是把盘子一个一个拿下来，而不能直接从中间抽出盘子（一不小心摔碎，就是家里人亲切的问候），这种就是典型的"栈"结构。
从栈的操作特性上来看， 栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。第一次接触栈的时候，总会觉得这些事情，数组和链表也能做到，那这个数据结构还有什么意义？事实上，从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。
从上面的描述来看，栈只有出栈和入栈两个操作，也就是在栈顶插入一个数据和从栈顶删除一个数据，所以实现相对简单。另外，用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。
// 数组实现
public class ArrayStack {
private String[] items; // 数组
private int count; // 栈中元素个数
private int n; //栈的大小
// 初始化数组，申请一个大小为n的数组空间
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
// 入栈操作
public boolean push(String item) {
// 数组空间不够了，直接返回false，入栈失败。
if (count == n) return false;
// 将item放到下标为count的位置，并且count加一
items[count] = item;
++count;
return true;
}
// 出栈操作
public String pop() {
// 栈为空，则直接返回null
if (count == 0) return null;
// 返回下标为count-1的数组元素，并且栈中元素个数count减一
String tmp = items[count-1];
--count;
return tmp;
}
}
// 链表结点
public class Node {
private static final String DEFAULT_VAL = "-1";
private String val;
private Node next;
public Node() {
}
public Node(String val) {
this(val, null);
}
public Node(Node node) {
this(DEFAULT_VAL, node);
}
public Node(String val, Node next) {
this.val = val;
this.next = next;
}
public String getVal() {
return val;
}
public void setVal(String val) {
this.val = val;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return Objects.equal(val, node.val) &&
Objects.equal(next, node.next);
}
@Override
public int hashCode() {
return Objects.hashCode(val, next);
}
@Override
public String toString() {
return "Node{" + val + "}";
}
}
// 链表实现
public class LinkedListStack {
private static final String DEFAULT_HEAD = "head";
private Node head;
public LinkedListStack() {
this.head = new Node(DEFAULT_HEAD);
}
public void push(Node node) {
node.setNext(head.getNext());
head.setNext(node);
}
public Node pop() {
if (head.getNext() == null) {
return null;
}
Node tmp = head.getNext();
head.setNext(tmp.getNext());
return tmp;
}
public void sout() {
Node next = this.head;
while (true) {
if (next.getNext() == null) {
System.out.println("遍历完成");
break;
}
System.out.println(next);
next = next.getNext();
}
}
public Node getHead() {
return head;
}
public void setHead(Node head) {
this.head = head;
}
}
栈在函数调用中的使用
前面我讲的都比较偏理论，我们现在来看下，栈在软件工程中的实际应用。栈作为一个比较基础的数据结构，应用场景还是蛮多的。其中，比较经典的一个应用场景就是函数调用栈。
&esmp;我们知道，操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。为了让你更好地理解，我们一块来看下这段代码的执行过程。
int main() {
int a = 1;
int ret = 0;
int res = 0;
ret = add(3, 5);
res = a + ret;
printf("%d", res);
reuturn 0;
}
int add(int x, int y) {
int sum = 0;
sum = x + y;
return sum;
}
从代码中我们可以看出， main()函数调用了add()函数，获取计算结果，并且与临时变量a相加，最后打印res的值。为了让你清晰地看到这个过程对应的函数栈里出栈、入栈的操作，我画了一张图。图中显示的是，在执行到add()函数时，函数调用栈的情况。
好了，我想现在你已经完全理解了栈的概念。我们再回来看看开篇的思考题，如何实现浏览器的前进、后退功能？其实，用两个栈就可以非常完美地解决这个问题。
我们使用两个栈， X和Y，我们把首次浏览的页面依次压入栈X，当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据依次放入栈Y。当我们点击前进按钮时，我们依次从栈Y中取出数据，放入栈X中。当栈X中没有数据时，那就说明没有页面可以继续后退浏览了。当栈Y中没有数据，那就说明没有页面可以点击前进按钮浏览了。
比如你顺序查看了a， b， c三个页面，我们就依次把a， b， c压入栈，这个时候，两个栈的数据就是这个样子：
本文共计1629个文字，预计阅读时间需要7分钟。
浏览器的前进与后退功能，让用户轻松浏览历史页面。例如，我在浏览器操作了+a-b-c三个页面，点击后退按钮，就能查看之前浏览过的页面+b和a。
浏览器的前进与后退功能，大家肯定会熟悉吧。
比如我在浏览器操作了a->b->c三个页面，点击浏览器的后退按钮，就可以查看之前浏览器的浏览过的页面 b 和 a，当你后退到页面 a，点击前进时，你就可以拿到 b 跟 c。
如果你是谷歌工程师，你现在要如何实现这个功能？
"栈"其实很好理解，你就可以把他看做一叠盘子，你只能一个一个叠加盘子，或者是把盘子一个一个拿下来，而不能直接从中间抽出盘子（一不小心摔碎，就是家里人亲切的问候），这种就是典型的"栈"结构。
从栈的操作特性上来看， 栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。第一次接触栈的时候，总会觉得这些事情，数组和链表也能做到，那这个数据结构还有什么意义？事实上，从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。
当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，我们就应该首选“栈”这种数据结构。
从上面的描述来看，栈只有出栈和入栈两个操作，也就是在栈顶插入一个数据和从栈顶删除一个数据，所以实现相对简单。另外，用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。
// 数组实现
public class ArrayStack {
private String[] items; // 数组
private int count; // 栈中元素个数
private int n; //栈的大小
// 初始化数组，申请一个大小为n的数组空间
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
// 入栈操作
public boolean push(String item) {
// 数组空间不够了，直接返回false，入栈失败。
if (count == n) return false;
// 将item放到下标为count的位置，并且count加一
items[count] = item;
++count;
return true;
}
// 出栈操作
public String pop() {
// 栈为空，则直接返回null
if (count == 0) return null;
// 返回下标为count-1的数组元素，并且栈中元素个数count减一
String tmp = items[count-1];
--count;
return tmp;
}
}
// 链表结点
public class Node {
private static final String DEFAULT_VAL = "-1";
private String val;
private Node next;
public Node() {
}
public Node(String val) {
this(val, null);
}
public Node(Node node) {
this(DEFAULT_VAL, node);
}
public Node(String val, Node next) {
this.val = val;
this.next = next;
}
public String getVal() {
return val;
}
public void setVal(String val) {
this.val = val;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return Objects.equal(val, node.val) &&
Objects.equal(next, node.next);
}
@Override
public int hashCode() {
return Objects.hashCode(val, next);
}
@Override
public String toString() {
return "Node{" + val + "}";
}
}
// 链表实现
public class LinkedListStack {
private static final String DEFAULT_HEAD = "head";
private Node head;
public LinkedListStack() {
this.head = new Node(DEFAULT_HEAD);
}
public void push(Node node) {
node.setNext(head.getNext());
head.setNext(node);
}
public Node pop() {
if (head.getNext() == null) {
return null;
}
Node tmp = head.getNext();
head.setNext(tmp.getNext());
return tmp;
}
public void sout() {
Node next = this.head;
while (true) {
if (next.getNext() == null) {
System.out.println("遍历完成");
break;
}
System.out.println(next);
next = next.getNext();
}
}
public Node getHead() {
return head;
}
public void setHead(Node head) {
this.head = head;
}
}
栈在函数调用中的使用
前面我讲的都比较偏理论，我们现在来看下，栈在软件工程中的实际应用。栈作为一个比较基础的数据结构，应用场景还是蛮多的。其中，比较经典的一个应用场景就是函数调用栈。
&esmp;我们知道，操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构,用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。为了让你更好地理解，我们一块来看下这段代码的执行过程。
int main() {
int a = 1;
int ret = 0;
int res = 0;
ret = add(3, 5);
res = a + ret;
printf("%d", res);
reuturn 0;
}
int add(int x, int y) {
int sum = 0;
sum = x + y;
return sum;
}
从代码中我们可以看出， main()函数调用了add()函数，获取计算结果，并且与临时变量a相加，最后打印res的值。为了让你清晰地看到这个过程对应的函数栈里出栈、入栈的操作，我画了一张图。图中显示的是，在执行到add()函数时，函数调用栈的情况。
好了，我想现在你已经完全理解了栈的概念。我们再回来看看开篇的思考题，如何实现浏览器的前进、后退功能？其实，用两个栈就可以非常完美地解决这个问题。
我们使用两个栈， X和Y，我们把首次浏览的页面依次压入栈X，当点击后退按钮时，再依次从栈X中出栈，并将出栈的数据依次放入栈Y。当我们点击前进按钮时，我们依次从栈Y中取出数据，放入栈X中。当栈X中没有数据时，那就说明没有页面可以继续后退浏览了。当栈Y中没有数据，那就说明没有页面可以点击前进按钮浏览了。
比如你顺序查看了a， b， c三个页面，我们就依次把a， b， c压入栈，这个时候，两个栈的数据就是这个样子：