[数据结构与算法]JavaScript(ES6)数据结构与算法——栈

实现栈结构有两种比较常见的方法

• 基于数组实现
• 基于链表实现

这里演示的是基于数组实现的方式

在实现栈结构之前，我们需要知道栈都有哪些功能

• 添加一个新元素到栈顶位置。push(element)
• 移除栈顶元素，同时返回被移除的元素。pop()
• 返回栈顶的元素，不对栈做任何操作。peek()
• 如果栈中没有任何就返回true，否则就返回false。isEmpty()
• 返回栈中的元素个数，这个方法和数组的length属性类似。size()

栈结构的封装

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

  //   - 添加一个新元素到栈顶位置。push(element)
  push(element) {
    this.items.push(element);
  }
  // - 移除栈顶元素，同时返回被移除的元素。pop()
  pop() {
    return this.items.pop();
  }
  // - 返回栈顶的元素，不对栈做任何操作。peek()
  peek() {
    return this.items[this.items.length - 1];
  }
  // - 如果栈中没有任何就返回true，否则就返回false。isEmpty()
  isEmpty() {
    return this.items.length === 0;
  }
  // - 返回栈中的元素个数，这个方法和数组的length属性类似。size()
  size() {
    return this.items.length;
  }
}

module.exports = new Stack();

测试

const stack = require("./stack");

stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);

console.log(stack.items);
console.log(stack.pop());
console.log(stack.items);
console.log(stack.isEmpty());
console.log(stack.size());

栈结构的应用

栈结构最典型的一个应用问题就是进制转换（十进制==>二进制）

为什么需要十进制转换为二进制

• 现实生活中，我们主要使用的是十进制，但在计算机科学中，二进制非常重要，因为计算机底层的所有内容都是用二进制数字表示的（0，1），没有十进制和二进制的相互转化的能力，与计算机交流很困难

下面代码通过栈将十进制转为二进制

const stack = require("../stack");

function decToBin(num) {
  while (num > 0) {
    let remainder = num % 2;
    num = Math.floor(num / 2);
    stack.push(remainder);
  }

  let binStr = "";

  while (!stack.isEmpty()) {
    binStr += stack.pop();
  }

  return binStr;
}
module.exports = decToBin;

测试

const dectoobin = require("./decToBin");

console.log(dectoobin(100));

此案例利用栈先进后出的特性，将十进制数取余的结果依次压入栈内，因为压入栈中的序列是倒叙，所以通过出栈的方式依次将出栈的数字保存在一个变量中，最后返回这个变量就是最后转换完成的二进制。