JavaScript 数据结构与算法1(数组与栈) - 张宁187

index.js

// 创建类表示栈
class IndexStack {
  constructor() {
    // 我们需要一种数据结构来保存栈里的元素。可以选择数组来实现。
    this.item = [];
  }
}

 // 栈里面添加元素
  push(element) {
    this.item.push(element);
  }

  // 清空栈元素
  clear() {
    this.items = [];
  }

  push(element) {
    // 在 JavaScript 中对象是一系键值对的集合。
    // 要向栈中添加元素，使用 count 作为 items 对象的键名，插入的元素则是它的值。
    this.items[this.count] = element;
    this.count++;
  }
const stack = new Stack();
stack.push(111);
stack.push(222);
// items = {0: 111, 1: 222}; count = 2;

  size() {
    return this.count;
  }

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

  // 从栈中弹出元素
  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;
  }

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

以上除了 toString 方法，我们创建的其他方法的复杂度均为 O(1)，代表我们直接找到目标元素并对其进行操作（push、pop、peek）。

const stack = new Stack();
// getOwnPropertyNames 方法返回一个由指定对象的所有自身属性的属性名
// （包括不可枚举属性但不包括Symbol值作为名称的属性）组成的数组
console.log(Object.getOwnPropertyNames(stack));// 1
console.log(Object.keys(stack));// 2
console.log(stack.items);// 3

　　1 和 2 行输出结果为 ['count', 'items']。这表示 count 和 items 属性是公开的，我们可以像 3 行那样直接访问它们。根据这种行为，我们可以对这两个属性赋新的值。

这里使用 ES6 语法创建的 Stack 类。ES6 类是基于原型的，尽管基于原型的类能节省内存空间并在扩展方便优于基于函数的类，但这种方式不能声明私有属性（变量）或方法。这里我们希望 Stack 类的用户只能访问我们在类中暴露的方法。下面学习其他使用 JavaScript 来实现私有属性的方法。

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

const _items = Symbol('stackItems');

class Stack2 {
  constructor() {
    this.count = 0;
    this[_items] = [];
  }
  push(element) {
    this[_items][this.count] = element;
    this.count++;
  }
}
// 上面这种方法创建了一个假的私有属性，
// 因为 es6 新增的 Object.getOwnPropertySymbols 方法能够取到类里面声明的所有 Symbols 属性。
// 以下是 破坏 Stack2 类的示例

const stack2 = new Stack2();
stack2.push(1);
stack2.push(2);
let objectSymbols = Object.getOwnPropertySymbols(stack2);
console.log(objectSymbols.length);// 1
console.log(objectSymbols);// [Symbol(stackItems)]
console.log(objectSymbols[0]);// Symbol(stackItems)
stack2[objectSymbols[0]].push(1);
console.log(stack2);

　　上面代码说明 stack2[objectSymbols[0]] 是可以得到 _items 的。并且 _items 属性是一个数组，可以进行任意的数组操作，比如从中间删除或添加元素（使用对象进行存储也是一样的）。但是我们操作的是栈，不应该出现这种行为。所以这种方式也是不可取的。

// 声明 WeakMap 类型的变量 item3
const items3 = new WeakMap();

class Stack3 {
  constructor() {
    // 这里以 this 为键，把代表栈的数组存入 items
    items3.set(this, []);
  }

  push(element) {
    // 从 WeakMap 中取出值，以 this 为键从 items3 中取值。
    const s = items3.get(this);
    s.push(element);
  }

  pop() {
    const s = items3.get(this);
    const r = s.pop();
    return r;
  }
}

　　以上 items3 在 Stack3 类里是真正的私有属性。（利用 weakMap 来实现私有化）采用这种方法，代码的可读性不强，而且在扩展该类时无法继承私有属性。鱼和熊掌不可兼得。

class Stack {
  // 可以通过 # 作为前缀来声明私有属性，这种行为和 WeakMpa 中的私有属性很相似。应该在不久的将来就能实现
    #count = 0;
  #items = {};
}

// 十进制转二进制
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(10));

// 十进制转任意进制
function baseConverter(decNumber, base) {
  const remStack = new Stack();
  // 余数为 0-9 加上 A-Z ，A 对应 10 B 对应 11 ，往后依次累加
  const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ';
  let number = decNumber;
  // 余数
  let rem;
  let binaryString = '';

  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()) {
    binaryString += digits[remStack.pop()];
  }
  return binaryString;
}

console.log(baseConverter(12345, 2));
console.log(baseConverter(12345, 8));
console.log(baseConverter(12345, 16));