1. The stack

The characteristics of

Ordered collections that follow the last in, first out (LIFO) principle.

implementation

Array based implementation

class Stack {
  constructor() {
    this.items = []
  }
  // Add elements to the top of the stack
  push(element) {
    this.items.push(element)
  }
  // Remove the element from the top of the stack
  pop() {
    return this.items.pop()
  }
  // Look at the top of the stack
  peek() {
    return this.items[this.items.length - 1]}// Check whether the stack is empty
  isEmpty() {
    return this.items.length === 0
  }
  // Get the stack length
  size() {
    return this.items.length
  }
  // Clear the stack elements
  clear() {
    this.items = []
  }
}
Copy the code

Object-based implementation

Implementing a stack based on an array is the easiest way to do it, but to use it, we need to iterate through the array until we find the element we want, and it takes O(n) time; In addition, an array is an ordered collection of elements. To keep the elements in order, it takes up more memory space. So we can add a count attribute and use an object to implement the stack structure.

class Stack {
  constructor() {
    this.count = 0
    this.items = {}
  }
  push(element) {
    this.items[this.count++] = element
  }
  pop() {
    if (this.isEmpty()) {
      return undefined
    }
    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 = {}
  }
  // Customize the toString method
  toString() {
    if (this.isEmpty()) {
      return ' '
    }
    let result = ' '
    for (let i = 0; i < this.count; i++) {
      result += `The ${this.items[i]}${i === this.count - 1 ? ' ' : ', '}`
    }
    return result
  }
}

Copy the code

Protect the elements inside the data structure

For stack data structures, make sure that elements are added only to the top of the stack, not to the bottom of the stack or anywhere else. However, the items and count properties declared in the Stack class are not protected and can be modified at will.

const stack = new Stack()

Object.getOwnPropertyNames(stack) // [ 'count', 'items' ]
Object.keys(stack) // [ 'count', 'items' ]
console.log(stack.items, stack.count) / / {}, 0
Copy the code

We want users of the Stack class to have access only to the methods that we expose in the class

Implement the class using ES6’s scoped Symbol

ES6 adds the Symbol primitive data type, which represents a unique value that we use as a property of the object.

const _ items = Symbol('stackItem')

class Stack {
  constructor() {
    this.count = 0
    this[_items] = {}
  }
  // self-defining function
  // Add a print method
  print() {
    return this[_items]
  }
}
Copy the code

This way also can’t avoid attribute is accessed, while using the Symbol type to avoid being Object. The keys () and Object getOwnPropertyNames () method to access, But ES6 provides the same Object. GetOwnPropertySymbols () method to get all the Symbol attributes

const stack = new Stack()

Object.getOwnPropertyNames(stack) // [ 'count' ]
Object.getOwnPropertySymbols(stack) // [ Symbol(stackItem) ]

let objectSymbol = stack[Object.getOwnPropertySymbols(stack)[0]] // Get the _items object
objectSymbol[1] = 2
stack.print() // {'1': 2}
Copy the code

Use ES6 WeakMap implementation class

The idea is to save an array by WeakMap, and the next steps are to use the GET function to take out the array for operation; The disadvantages are that the code is not readable, and you cannot inherit private properties when you extend the class.

const items = new WeakMap(a)class Stack {
  constructor() {
    items.set(this[])},push(element) {
    const s = items.get(this)
    s.push(element)
  }
  pop() {
    const s = items.get(this)
    const result = s.pop()
    return result
  }
  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[])}},Copy the code

Actual Usage Scenario

Transformation into the system

function baseConverter(decNumber, base = 2) {
  const remStack = new Stack()
  const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  let number = decNumber
  let baseString = ' '
  / / 2-36 into the system
  if (base < 2 || base > 36) {
    return ' '
  }
  // Take the modulo of decNumber
  while (number > 0) {
    let rem = Math.floor(number % base)
    remStack.push(rem)
    number = Math.floor(number / base)
  }
  // Take the reverse operation
  while(! remStack.isEmpty()) { baseString += digits[remStack.pop()] }return baseString
}
Copy the code

---

2. Queue and dual-end queue