JavaScript 数据结构与算法 之 栈

栈

栈结构

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

1. 创建基于数组的栈

class Stack {
  constructor() {
    this.items = [];
  }
  // 元素进栈
  push(item) {
    this.items.push(item);
  }
  // 元素出栈
  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.size()); // 输出 3
console.log(stack.isEmpty()); // 输出 false
stack.push(15);
stack.pop();
stack.pop();
console.log(stack.size()); // 输出 2

JS对象实现Stack类

class Stack {
  constructor() {
    this.count = 0;
    this.items = {};
  }
  push(item) {
    this.items[this.count] = item;
    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];
  }
  clear() {
    this.items = {};
    this.count = 0;
  }
  size() {
    return this.count;
  }
  isEmpty() {
    return this.count === 0;
  }
  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;
  }
}

保护数据结构内部元素

• 使用下划线命名约定

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

• 使用限定作用域Symbol实现类

Object.getOwnPropertySymbols 方法能够取到类里面声明的所有 Symbols 属性，这种方法还是不安全

const _items = Symbol('stackItems');
class Stack {
  constructor() {
    this[_items] = {};
  }
}

• WeakMap实现

const _items = new WeakMap();
class Stack {
  constructor() {
    items.set(this, []);
  }
  push(item) {
    const s = items.get(this);
    s.push(item);
  }
  pop() {
    const s = items.get(this);
    const r = s.pop();
    return r;
  }
  // ...
}

栈应用

• 进制转换

  • 十进制转二进制

  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;
  }

  • 任意进制转换(2~36)

  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;
  }