数据结构——栈

[yangxy6]

栈数据结构

栈是遵循后进先出（LIFO）原则的有序集合。新元素靠近栈顶，旧元素靠近栈底。生活中例如一摞书或者堆放的盘子。

创建栈

function Stack() {
  this.items = [];
}
Stack.prototype.push = function(ele) {
  this.items.push(ele);
  this.min = this.min > ele ? ele : this.min;
};
Stack.prototype.pop = function() {
  return this.items.pop();
};
Stack.prototype.top = function() {
  return this.items[this.items.length - 1];
};
Stack.prototype.isEmpty = function() {
  return this.items.length === 0;
};
Stack.prototype.getMin = function() {
  let min = this.items[0];
  for (let i = 0; i < this.items.length; i++) {
    if (min > this.items[i]) min = this.items[i];
  }
  return min;
};
Stack.prototype.clear = function() {
  this.items = [];
};
Stack.prototype.print = function() {
  console.log(this.items.toString());
};

let stack = new Stack();
stack.push(1);
stack.push(-4);
console.log(stack.top()); //-4
stack.push(-2);
stack.print(); //-1,-4,-2
console.log(stack.getMin()); //-4
console.log(stack.isEmpty()); //false
stack.pop();
stack.print(); // 1 -4
console.log(stack.getMin()); //-4
stack.pop();
console.log(stack.getMin()); //-4

应用——十进制转换二进制

function divideBy2(num) {
  let stack = new Stack(),
    item,
    result = '';
  while (num > 0) {
    item = Math.floor(num % 2);
    stack.push(item);
    num = Math.floor(num / 2);
  }
  while (!stack.isEmpty()) {
    result += stack.pop().toString();
  }
  return result;
}
console.log(divideBy2(10));

应用——平衡圆括号

// 思路：遇到{入栈，遇到}出栈，最后判断栈中元素是否是0

function isBalancle(str) {
  let info = str.split('');
  let stack = new Stack();
  for (let i = 0; i < info.length; i++) {
    if (info[i] === '(') {
      stack.push('(');
    } else {
      if (stack.isEmpty()) {
        return false;
      } else {
        stack.pop();
      }
    }
  }
  return stack.isEmpty();
}
console.log(isBalancle('(()'));

应用-汉诺塔（栈和递归）

let n = 3;
let stack1 = new Stack();
let stack2 = new Stack();
let stack3 = new Stack();
for (var i = n; i >= 1; i--) {
  stack1.push(i);
}
let obj = {
  a: stack1,
  b: stack2,
  c: stack3
};
/**
 * @param {number} n - 盘子数量
 * @param {string} a - 初始盘子位置
 * @param {string} b - 辅助轴
 * @param {string} c - 目标位置轴
 */
function haoni(n, a, b, c) {
  if (n > 0) {
    haoni(n - 1, a, c, b);
    console.log(`移动${n}号盘子，从 ${a} 移到 ${c}`);
    obj[c].push(obj[a].pop());
    haoni(n - 1, b, a, c);
  }
}
// 移动前
stack1.print();
stack2.print();
stack3.print();
haoni(3, 'a', 'b', 'c');
// 移动后
stack1.print();
stack2.print();
stack3.print();