Javascript 堆栈Stack

Stack是一种高效率的数据结构，相比List，它仅支持在一端（尾部）进行存取操作，即常说的后进先出LIFO。在计算机底层和编程语言内部实现中以及现实问题中都有广泛的应用。

堆栈的js实现

function Stack() {
   this.dataStore = [];
   this.top = 0;
   this.push = push;
   this.pop = pop;
   this.peek = peek; // 查看（瞥）栈顶元素
}

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

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

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

function length() {
        return this.top;
}

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

栈的应用1. x进位转换

使用堆栈可以方便的将一个10进位数n转换为b进位数，方法如下：

1. 将n%b的结果存入堆栈，即为对应b进位数的最低位
2. 用n/b替换n
3. 重复步骤1和2，只到n为0
4. 将堆栈中所有数字弹出，即得到完整的b进位数

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

// 验证mulBase的正确性
var num = 32;
var base = 2;
var newNum = mulBase(num, base);
print(num + " converted to base " + base + " is " + newNum);
num = 125;
base = 8;
var newNum = mulBase(num, base);
print(num + " converted to base " + base + " is " + newNum);