Javascript数据结构之栈处理

栈数据结构

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

栈在编辑语言的编译器和内存中保存变量、方法调用等，也被用于浏览器历史记录

基于数组的栈

• push（element(s)）：插入一个（或几个）新元素到栈项
• pop()：移除栈顶的元素，同时返回被移除的元素
• peek()：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶元素，仅仅返回它）
• isEmpty()：如果栈里没有任何元素就返回 true，否则返回 false
• clear()：移除栈里所有元素
• size()：返回栈里的元素个数，该方法和数组的 length 属性很类似

class Stack {
  constructor() {
    this.items = [];
  }
  // 向栈插入元素
  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;
  }
  // 返回栈长度
  size() {
    return this.items.length;
  }
  // 清空栈元素
  clear() {
    this.items = [];
  }
}

const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5);
stack.push(8);
console.log(stack.peek()); // 8
stack.push(11);
console.log(stack.items); // [ 5, 8, 11 ]
console.log(stack.size()); // 3
stack.pop();
console.log(stack.items); // [ 5, 8 ]

基于对象的栈

• push（element(s)）：插入一个新元素到栈项
• pop()：移除栈顶的元素，同时返回被移除的元素
• peek()：返回栈顶的元素，不对栈做任何修改（该方法不会移除栈顶元素，仅仅返回它）
• isEmpty()：如果栈里没有任何元素就返回 true，否则返回 false
• clear()：移除栈里所有元素
• size()：返回栈里的元素个数，该方法和数组的 length 属性很类似
• toString()：返回栈里所有元素

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;
  }
  // 查看栈顶元素
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }
  // 检查栈是否为空
  isEmpty() {
    return this.count === 0;
  }
  // 返回栈长度
  size() {
    return this.count;
  }
  // 清空栈元素
  clear() {
    this.count = 0;
    this.items = {};
  }
  // toString
  toString() {
    if (this.isEmpty()) {
      return '';
    }
    let objString = `${this.items[0]}`;
    for (let i = 1; i < this.count; i++) {
      objString = `${objString},${this.items[i]}`;
    }
    return objString;
  }
}

const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5);
stack.push(8);
console.log(stack.peek()); // 8
stack.push(11);
console.log(stack.toString()); // 5,8,11
console.log(stack.size()); // 3
stack.pop();
console.log(stack.toString()); // 5,8

保护数据结构内部元素

上面基于数组或对象的栈，我们希望保护内部元素，只有我们暴露出的方法才能修改内部结构。对于 Stack 类来说，要确保元素只会被添加到栈顶，而不是栈底或其他任意位置。不幸的是，在 Stack 类中声明的 items 和 count 属性并没有得到保护。

console.log(Object.getOwnPropertyNames(stack)) // [ 'count', 'items' ]
console.log(Object.keys(stack)) // [ 'count', 'items' ]
console.log(stack.items) // { '0': 5, '1': 8 }

• 下划线命名约定

class Stack {
  constructor() {
    this._count = 0;
    this._items = {};
  }
}

下划线命名约定就是在属性名称之前加上一个下划线(_)。不过这种方式只是一种约定，并不能保护数据，而且只能依赖于使用我们代码的开发者具备的常识。

• 用 ES2015 的限定作用域 Symbol 实现类

ES2015新增了一种叫作 Symbol 的基本类型，它是不可变的，可以用作对象的属性。看看怎么用它在 Stack 类中的声明 items 属性

const _items = Symbol('stackItems');
class Stack {
  constructor() {
    this[_items] = [];
  }
  // 向栈插入元素
  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;
  }
  // 返回栈长度
  size() {
    return this[_items].length;
  }
  // 清空栈元素
  clear() {
    this[_items] = [];
  }
}

const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5);
stack.push(8);
let objectSymbols = Object.getOwnPropertySymbols(stack);
console.log(objectSymbols.length); // 1
console.log(objectSymbols); // [ Symbol(stackItems) ]
console.log(objectSymbols[0]); // Symbol(stackItems)
stack[objectSymbols[0]].push(1);
console.log(stack[objectSymbols[0]]); // [ 5, 8, 1 ]

这种方法创建了一个假的私有属性，因为 ES2015 新增的 Object.getOwnPropertySymbols 方法能够取到类里声明的所有 Symbols 属性。上面的破坏 Stack 类的例子，可以看到访问 stack[objectSymbols[0]] 是可以得到 _items 的。_items 属性是一个数组，可以进行任意的数组操作。

• 用 ES2015 的 WeakMap 实现类

WeakMap 数据类型可以确保属性是私有的，这种数据结构，只需要知道 WeakMap 可以存储键值对，其中键是对象，值可以是任意数据类型。

const items = new WeakMap();

class Stack {
  constructor() {
    items.set(this, [])
  }
  // 向栈插入元素
  push(element) {
    const s = items.get(this);
    s.push(element);
  }
  // 从栈弹出元素
  pop() {
    const s = items.get(this);
    const r = s.pop();
    return r;
  }
  // 查看栈顶元素
  peek() {
    const s = items.get(this);
    return s[s.length - 1];
  }
  // 检查栈是否为空
  isEmpty() {
    const s = items.get(this);
    return s.length === 0;
  }
  // 返回栈长度
  size() {
    const s = items.get(this);
    return s.length;
  }
  // 清空栈元素
  clear() {
    items.set(this, [])
  }
  getItems() {
    const s = items.get(this);
    return s;
  }
}

const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5);
stack.push(8);
console.log(stack.peek()); // 8
stack.push(11);
console.log(stack.getItems()); // [ 5, 8, 11 ]
console.log(stack.size()); // 3
stack.pop();
console.log(stack.getItems()); // [ 5, 8 ]
stack.clear()
console.log(stack.size()); // 0

• ECMAScript 类属性提案

Typescript 提供了一个给类属性和方法使用的 private 修饰符。该修饰符只在编译时有用，在代码被编译完成后，属性同样是公开的

class Stack {
  #count = 0;
  #items = [];
}

栈的运用要

栈的实际运用非常广泛。在回溯问题中，它可以存储访问过的任务或路径、撤销的操作。也可以用它来解决一些计算机科学问题。任意进制转换的算法。判断回文数。

• 十进制转二进制

十进制转化成二进制，我们可以将十进制数除以2并对商取整直到结果是0为止。把十进制数取余的数存入栈中，利用栈中后进先出的原则，依次弹出余数，即为该下进制数的二进制表示。

function decimalToBinary(decNumber) {
  const remStack = new Stack();
  let number = decNumber;
  let rem;
  let binaryString = '';
  while(number > 0) {
    rem = Math.floor(number % 2);
    remStack.push(rem);
    number = Math.floor(number / 2);
  }
  while(!remStack.isEmpty()) {
    binaryString += remStack.pop().toString();
  }
  return binaryString;
}
console.log(decimalToBinary(42)) // 101010
console.log(decimalToBinary(10)) // 1010
console.log(decimalToBinary(1000)) // 1111101000

• 进制转换算法

在将十进制转成二进制时，余数是0或1；在将十进制转成8进制时，余数是0~7；将十进制转成16进制数据时，余数是1~9 、A 、B 、C 、D 、E ，从十一制开始，字母表中的每个字母将表示相应的基数。字母A代表基数11，B代表基数12。

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

console.log(baseConverter(100345, 2)) // 11000011111111001
console.log(baseConverter(100345, 8)) // 303771
console.log(baseConverter(100345, 16)) // 187F9
console.log(baseConverter(100345, 35)) // 2BW0

• 回文数

根据栈后进先出（LIFO）原则 ，该数据结构特点，组成字符器与原始值相等即为回文数。

function isPalindrome(value) {
  const stack2 = new Stack();
  for (let i = 0; i < value.length; i++) {
    stack2.push(value[i]);
  }
  let value2 = '';
  while(stack2.size() > 0) {
    value2 += stack2.pop();
  }
  if (value === value2) {
    return true;
  } else {
    return false;
  }
}
console.log(isPalindrome('10001')) // true
console.log(isPalindrome('level')) // true
console.log(isPalindrome('leveel')) // false