栈：如何去实现浏览器前进与后退的功能

  浏览器的前进与后退功能，大家肯定会熟悉吧。
  比如我在浏览器操作了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压入栈，这个时候，两个栈的数据就是这个样子：