栈

1. 栈数据结构

• 栈是一种遵从后进先出原则的有序集合。
• 新添加或待删除的元素保存在栈的同一端，称为栈顶，另一端称为栈底。
• 新元素靠近栈顶，旧元素接近栈底。
• 栈常用于编译器和内存中保存变量、方法调用，也被用于浏览器历史记录。

1.1 创建一个基于数组的栈

Stack 类：

class Stack {
  constructor() {
    this.items = [];
  }
}

栈的一些方法：

• push(elements)：添加一个或几个新元素到栈顶。
• pop()：移除栈顶元素，同时返回被移除的元素。
• peek()：返回栈顶元素，不对栈做任何修改。
• isEmpty()：栈里没有元素返回 true，否则返回 false。
• clear()：移除栈里所有元素。
• size()：返回栈里的元素个数。

1.2 向栈添加元素

使用数组保存栈元素，直接使用数组的 push() 方法：

push(element) {
  this.items.push(element)
}

1.3 从栈移除元素

直接使用数组的 pop 方法：

pop() {
  return this.items.pop();
}

1.4 查看栈顶元素

直接访问数组最后一个元素即可：

peek() {
  return this.items[this.items.length - 1];
}

1.5 检查是否为空和大小

isEmpty() {
  return this.items.length === 0;
}

size() {
  return this.items.length;
}

1.6 清空栈元素

clear() {
  this.items = [];
}

1.7 使用 Stack 类

const stack = new Stack();
stack.isEmpty() // true

stack.push(5);
stack.push(8); 
stack.peek(); // 8

stack.push(11);
stack.size(); // 3

stack.push(15);
stack.pop(); // 15
stack.pop(); // 11
stack.size(); // 2

2. 创建一个基于 JavaScript 对象的栈

Stack类：

class Stack() {
  constructor() {
    this.count = 0;
    this.items = {};
  }
}

2.1 向栈中插入元素

一次只允许插入一个元素：

push(element) {
  this.items[this.count++] = element;
}

2.2 验证一个栈是否为空和它的大小

size() {
  return this.count;
}

isEmpty() {
  return this.count === 0;
}

2.3 从栈中弹出元素

如果栈为空则返回 undefined，否则保存栈顶元素，通过 delete 操作符删除，并返回保存的值。

pop() {
  if(this.isEmpty()) {
    return undefined;
  }
  this.count--;
  const res = this.items[this.count];
  delete this.items[this.count];
  return res;
}

2.4 查看栈顶的元素并将栈清空

peek() {
  if(this.isEmpty()) {
    return undefined;
  }
  return this.items[this.count - 1];
}

clear() {
  this.count = 0;
  this.items = {};
}

2.5 创建 toString() 方法

toString() {
  if(this.isEmpty()) {
    return '';
  }
  let res = `${this.items[0]}`
  for(let i = 1; i < this.count; i++) {
    res = `${res}, ${this.items[i]}`
  }
  return res;
}

在数组版本中，可以使用数组自身的 toString() 方法，而在对象版本中，需要自定义 toString() 来打印栈的内容。

3. 用栈解决实际问题

栈的应用非常广泛。在回溯问题中，用栈存储访问过的任务或路径，在多数编程语言中，用栈存储变量和方法调用。

3.1 十进制转二进制

十进制转二进制可以用“除2取余”法，将余数逆序拼接就是二进制结果，其中可以用栈保存余数：

function decimalToBinary(decNumber) {
  const remStack = new Stack;
  let number = decNumber;
  let rem;
  let res = '';

  while(number) {
    rem = number % 2;
    remStack.push(rem);
    number = Math.floor(number / 2);
  }

  while(!remStack.isEmpty()) {
    res += remStack.pop().toString();
  }

  return res;
}

3.2 十进制转为 2-36 任意进制

function decimalToBinary(decNumber, base) {
  const remStack = new Stack;
  const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
  let number = decNumber;
  let rem;
  let res = '';

  if(!(base >= 2 && base <= 36)) {
    return '';
  }

  while(number) {
    rem = number % base;
    remStack.push(rem);
    number = Math.floor(number / base);
  }

  while(!remStack.isEmpty()) {
    res += digits[remStack.pop()];
  }

  return res;
}