03.md

栈

栈是什么

1. 栈是一种先入后出的数据结构
2. 栈中的数据只能在栈顶添加或删除，任何不在栈顶的元素都无法访问
3. 栈一般有 3 个方法：push（进栈）、pop（出栈）、peek（返回栈顶元素）

栈的实现

function Stack() {
  this.dataStore = [];
  this.top = 0;
  this.push = push;
  this.pop = pop;
  this.peek = peek;
  this.length = length;
}

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

var pop = function() {
  var result = this.dataStore[this.top - 1];
  --this.top;
  return result;
};

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

var length = function() {
  return this.top;
};

栈的使用

• 数制之间相互转换

// 1. 最高位是number % base，依次入栈
// 2. 重写number/base替代number
// 3. 重复1 2 步骤 直到n等于0 没有余数
// 4. 栈内元素依次出栈，直到栈为空，依次排列，得到结果
function mulBase(number, base) {
  var s = new Stack();
  while (number > 0) {
    s.push(number % base);
    number = Math.floor((number /= base));
  }
  var result = "";
  while (s.length() > 0) {
    result += s.pop();
  }
  return result;
}
console.log(mulBase(32, 2));

• 回文

function isCanBackText(value) {
  var s = new Stack();
  for (var i = 0; i < value.length; i++) {
    s.push(value[i]);
  }
  var newValue = "";
  while (s.length() > 0) {
    newValue += s.pop();
  }
  if (newValue === value) {
    return true;
  } else {
    return false;
  }
}
console.log(isCanBackText("10000001"));

• 10 的阶乘用栈实现

function recursive(value) {
  var s = new Stack();
  while (value > 1) {
    s.push(value--);
  }
  var result = 1;
  while (s.length() > 0) {
    result *= s.pop();
  }
  return result;
}
console.log(recursive(10));