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

栈的特点是先进先出，只允许在一端插入和删除数据。

栈顶：栈的最后一个元素
栈底：栈的第一个元素
出栈：从栈顶删除最后一个元素
入栈：向栈顶压入新的元素

如何实现一个栈？

栈可以用数组实现，也可以用链表来实现。

function Stack(){
    var items = [];
    //入栈
    this.push = function(elem){
        items.push(elem);
    }
    //出栈
    this.pop = function(){
        return items.pop();
    }
    //返回栈顶元素
    this.peek = function(){
        return items[items.length -1];
    }
    //是否是空栈
    this.isEmpty = function(){
        return items.length;
    }
    //栈的长度
    this.size = function(){
        return items.length;
    }
    //清空栈
    this.clear = function(){
        items = [];
    }
    //打印栈
    this.print = function(){
        console.log(items.toString());
    }
}

栈的应用

栈在函数调用中的应用

函数被调用时，会被加入到调用栈顶部，执行结束后，就会从调用栈顶移除该函数。

function a (){
    b();
}
function b(){
    c();
};
a();

上图表示函数调用执行过程栈的变化。

栈在表达式求值中的应用

表达式求值是通过两个栈来实现，一个栈保存操作数，另一个栈保存运算符。

从左向右遍历表达式，当遇到数字时，将数字压入操作数栈；当遇到操作符时，与运算符栈的栈顶元素比较。

如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；
如果比运算符栈顶元素的优先级低或者相同，从运算符中取栈顶运算符，从操作数栈的栈顶取2个操作数，然后进行计算，再把计算结果压入操作数栈，继续比较。

课程例子：

栈在括号匹配中的应用

用来检测括号的嵌套是否合法

解答开篇

实现浏览器的前进和后退功能，使用两个栈（X和Y）实现。

• 首次浏览的页面依次压入栈X

• 当点击后退时，再依次从栈X中出栈，并将出栈的数据依次压入栈Y

• 当点击前进时，依次从栈Y中出栈，并将出栈的数据依次压入X

• 当栈X中没有数据时，说明没有页面可以继续后退浏览

• 当栈Y中没有数据时，说明没有页面可以继续前进浏览

课后思考

1.为什么函数调用要用“栈”来保存临时变量？用其他数据结构不行吗？

参考答案：