js数据结构-栈

栈

栈是一种遵循后进先出(LIFO)的数据结构，其总共就两个主要的操作，分别是push和pop。

屏幕快照 2018-12-28 下午2.54.16.png

看上面这张图可以大致的知道，栈的几个特点：

• 初始化：

  • 有一块连续的存储空间
  • 栈顶
  • 栈的长度

• push操作：

  • 向栈中添加新的元素
  • 栈顶向后挪动一个位置，指向最新的数据地址
  • 如果栈满了继续push的化，会抛出overflow的错误

• pop操作：

  • 返回栈顶数据
  • 栈顶向前挪动一个位置，指向前一个数据地址
  • 如果栈中没有数据继续pop的话，会抛出underflow的错误

通过上面的几个特点，来看一看js如何用代码实现一个栈

    class Stack {
       /**
        * 初始化
        */
        constructor(max = 100) {
            // 存储空间
            this.data = new Array(max);
            // 栈在最初是化的时候里面没有任何数据,所以栈顶指向-1
            this.top = -1;
            // 栈空间的大小
            this.max = max;
        }
        
       /**
        * push操作
        */
        push(x) {
            if(this.top === this.max - 1){
                throw 'overflow';
            }
            // push一个新的数据，栈顶的指向也同时像后挪动一位，指向最新的数据地址
            this.top++;
            // 将新的数据添加进栈
            this.data[this.top] = x;
        }
        
       /**
        * pop操作
        */
        pop() {
            if(this.top === -1){
                throw 'underflow'
            }
            // 获得栈顶数据
            const x = this.data[this.top];
            this.top--;
            return x;
        }
        
       /**
        * 获取栈的长度
        */
        get length(){
            return this.top + 1
        }
    }

通过上面的代码演示，对于栈应该会有一个大致的了解，后面会继续介绍其他的数据结构，并且可能会介绍如何使用栈来实现其他的数据结构，以及数据结构的一些应用。
学习前端的同学可能对于数据结构和算法复杂度相对于其他语言的工程师会稍弱一些，但是这些对于一个向深入学习前端的来说还是非常重要。

最后如果文章有讲错或讲的不对的地方，请大家留言更正哈。