js中模拟栈详解编程语言

栈是一种特殊的列表，栈内的元素只能通过栈顶来访问。对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈，入栈使用push方法，出栈使用pop方法。另一个方法peek是查询返回栈顶元素。

    function Stack(){ 
      //底层存储为一个数组 
      this.dataStore = []; 
      this.top = 0; 
      this.push = push; 
      this.pop = pop; 
      this.peek = peek; 
    }

这里存储数据的底层数据结构选择数组，虽然js中强大的数组对象有很多方法可以使用，但是我们来自定义栈的方法。

方法实现

构造函数将栈初始化为一个空数组，栈顶top对应数组的起始位置0。首先实现push方法，push方法接受一个参数element

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

this.top++执行的顺序是

   this.dataStore[this.top] = element; 
   this.top = this.top + 1;

因为此时栈顶指向的元素为空，所以新入栈的元素放在top当前值对应的位置，然后再将变量top的值加1。
pop方法的实现与push方法相反，它返回栈顶元素，同时将top的值减1

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

当然我们这里没有将栈顶的元素从数组中去除掉，我们更关心top的值的指向，至于数组中是否还存储其他元素都无关紧要，只要top指向0，那么我们的栈就是一个空栈。
peek的方法实现如下，当对一个空栈使用peek会返回undefined

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

length方法通过返回变量top值的方式返回栈内的元素个数

   function length(){ 
       return this.top; 
   }

通过将变量top值设为0来清空一个栈

   function clear(){ 
       this.top = 0; 
   }

具体应用

利用栈将转化数字的进制，假设将数字n转换为以b为基数的数字，方法如下:
1. 最高位为n % b，将此位压入栈
2. 使用n/b代替n
3. 重复步骤1和2，直到n等于0，且没有余数
4. 持续将栈内元素弹出，直到栈为空
实现方法如下：

   function mulBase(num, base){ 
       var stack = new Stack(); 
       do { 
          stack.push(num % base); 
          num = Math.floor(num /= base) 
       } while(num > 0) 
       var str = ''; 
       while(stack.length() > 0){ 
           str += stack.pop(); 
       } 
       return str 
   }

利用栈，可以轻松判断一个字符串是否是回文(回文指一个字符串从前往后写和从后往前写都一样)

   function isPalindrome(word){ 
       var stack = new Stack(); 
       for(var i = 0, len = word.length; i++){ 
           stack.push(word[i]); 
       } 
       var rword = ''; 
       while(stack.length() > 0){ 
           rword += stack.pop(); 
       } 
       return rword == word; 
   }

当然正常我们直接使用

    var arr = Array.prototype.slice.call(word); 
    return arr.reverse().join('') == word

直接暴力解决问题，但是这边的重点不在于数组对象的强大方法，如果想了解js中的数组对象，可以参考我的另一篇博文js数组方法分析