【算法和数据结构】—栈

312 阅读3分钟

上一篇我们说了"列表",是个相对简单的结构,如果数据存储的顺序不重要,也不必对数据进行查找,列表就很合适,但如果有特定的要求,“列表”就显得简陋了,本文开始,介绍一系列"真正"的结构。

栈是什么

关于“栈”有个经典的比喻,就是“放盘子”,我们平时在家吃饭洗盘子,都是先放最底下一个,然后一个一个往上摞,拿盘子也是从上面拿,即“存、取”都是从最上面进行操作——“LIFO(last in first out)”,这样的操作就很快,也方便实现。

在讲JS的时候,不会很经常地提及“栈”这个东西,但它却默默地在背后发挥作用,比如:表达式求值、处理函数调用等。

栈的实现

存储数据的底层结构这里还是选择“数组”。

    function Stack(){
      this.dataStore = [],  //  初始化一个空栈
      this.top = 0,  //  记录栈顶位置,有元素加入则发生变化
      this.push = push,   //  入栈
      this.pop = pop,   //  出栈
      this.getTop = getTop    //  获取栈顶元素
      this.length = length    //  获取元素个数
      this.clear = clear    //  清空栈
    }

方法

push()

    function push(ele){
      this.dataStore[this.top++] = ele;
    }

这里特别注意 top++ 的位置,放在了后面,这样新入栈的元素就放在了top代表的当前位置,然后top指向下一个位置。

pop()

pop方法和push相反。

    function pop(ele){
      return this.dataStore[--this.top];
    }

直接将长度减1,便将栈顶元素剔除了

getTop()

    function getTop(){
      return this.dataStore[this.top-1];
    }

length()

有时需要获取长度,知道有多少元素

    function length(){
      return this.top;
    }

clear()

清空栈

    function clear(){
      delete this.dataStore;
      this.top = 0;
      this.dataStore = [];
    }

试一试

    var plates = new Stack();
    plates.push("瓷的");
    plates.push("红的");
    plates.push("我的");
    console.log("个数:"+ plates.length());  //  个数:3
    console.log(plates.getTop());  // “我的”
    console.log(plates.clear());  

demo顺利运行,得到我们想要的结果。

栈的应用

那么栈可以应用在哪类需求里?

递归

“栈”经常被用于实现编程语言,递归便是其中一种,我们尝试实现。

递归有很多典型使用场景,有一种叫“阶乘”。

可以是这样:

    function factorial(n){
      if(n == 0){
        return 1;
      } else {
        return n*factorial(n-1);
      }
    }

用“栈”就是这样

    function fact(n){
      var s = new Stack();
      while(n>1){
        s.push(n--);
      }
      var result = 1;
      while(s.length() > 0){
        result*=s.pop();
      }
      return result;
    }

我们来试一下

    fact(5);  // 120

OK。

虽然从代码量来看,第二种反而更多,不如前面简洁,但这只是一个很简单的例子,而且二者算法不同,栈仍然有着它更加强大的用途。

函数设计

我们知道,函数的定义就是为了封装一个可复用的代码块。那么在重复应用的时候,参数是怎样传入的呢?

函数内一般都会定义局部变量,而不是单使用全局变量,那么局部变量存在哪里合适,而且能够在各种情况下都不发生冲突?

“栈”就可以解决这些问题,函数调用的时候,将参数和变量都压到一个栈中,这样避免产生太多的空间占用,也可以利用栈指针的偏移来完成存取,只要对应的函数栈指针是不同的,就不会发生冲突。

小结

关于“栈”的介绍到此告一段落,为便于理解,并没有很高深的东西,但不代表它不强大,相反,如果能够在合适的场景加以利用,就会帮到大忙,大家在实践中共同摸索吧~

这篇同样比较简单,但学习就是要由简到繁,由浅入深嘛,下篇见!~

博客链接:【算法和数据结构】—栈