第4章 栈.md

第4章 栈

概念

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

数组实现

class StackArray {
  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 = []
  }

  toArray() {
    return this.items
  }

  toString() {
    return this.items.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() {
    /* while (!this.isEmpty()) {
        this.pop();
      } */
    this.items = {}
    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
  }
}

保护数据结构内部元素

1. 下划线命名约定

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

2. Symbol 实现类 假的私有属性。

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

1. 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
  }
}

进制转换算法

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
}