JS实现栈数据结构

栈（stack）是一种常见的数据结构，它是遵循后进先出的有序集合，(LIFO)，生活中书桌上堆放的书本，餐桌上叠起来的盘子，都是典型的栈的形象。

使用JS来实现一个栈的数据结构，可以基于数组开始。

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

栈的方法有

• push(elements) 添加一个或者多个元素到栈顶
• pop() 移除栈顶的元素
• peek() 返回栈顶的元素，并对栈不做修改
• isEmpty() 栈为空返回true，否则返回false;
• clear() 清空栈
• size() 返回栈的元素个数

使用javascript的数组可以实现上述方法

push(element) {
  this.items.push(element)
}
pop() {
  return this.items.pop()
}
peek() {
  return this.items[this.items.length - 1];
}
isEmpty() {
  return this.items.length === 0;
}
clear() {
  this.items = [];
}
size() {
  return this.items.length
}

使用数组来创建栈十分方便，但是数组属于元素的有序集合，为了保证有序，占用的内存空间也更多。
我们可以使用对象来再次创建一个栈，实现上述的方法。

class Stack {
  constructor() {
    this.count = 0;
    this.items = {};
  }
  push(element) {
    this.items[this.count] = element;
    this.count++;
  }
  pop() {
    if(this.isEmpty()) {
      return undefined;
   } 
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }
  size() {
    return this.count;
  }
  isEmpty() {
    return this.count === 0;
  }
  peek() {
    if (this.isEmpty) {
      return undefined;
    }
    return this.items[this.count - 1];
  }
  clear() {
    this.count = 0;
    this.items = {};
  }
}

为了保护类内部的数据，可以设置下划线命名，this._items,this._count;
或者使用symbol，或者weakMap，感兴趣的友友们，可以参考学习javascript数据结构和算法，这些文章的编写也是对我平时阅读这本书的一些总结，个人练习输出，这本书是写的很不错的，解释的很简洁明确。

用栈解决问题的一个实例是，进制转换。
比如十进制转换二进制。

function decimalToBinary(decNumber) {
  const stack = new Stack();
  let number = decNumber;
  let rem; // 余数
  let binaryNumber = '';
  while(number > 0) {
    rem = Math.floor(number % 2);
    stack.push(rem);
    number= Math.floor(number / 2);
  }
  while(!stack.isEmpty()) {
    binaryNumber += stack.pop().toString();
  }
  return binaryNumber;
}

扩展到其他进制转换。

function baseConvert(decNumber, base) {
  const stack = new Stack();
  let number = decNumber;
  let rem;
  let baseString = '';
  const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
  if (!(base >= 2 && base <= 36)) {
    return '';
  }
  while(number > 0) {
    rem = Math.floor(number % base);
    stack.push(rem);
    number = Math.floor(number / base);
  }
  while(!stack.isEmpty()) {
    baseString += digits[stack.pop()];
  }
  return baseString;
}