动态数组

在其他语言中(例如Java)，数组在声明的时候就需要指定长度，是一种固定长度的类型。而JavaScript的数组本身就是动态的，但是作为练习，可以先尝试实现一个动态数组：

  1. class CustomArray {
  2.   constructor (capacity = 10) {
  3.     this.data = new Array(capacity)
  4.     this.size = 0
  5.   }
  7.   getSize () {
  8.     return this.size
  9.   }
  11.   getCapacity () {
  12.     return this.data.length
  13.   }
  15.   get (index) {
  16.     if (index < 0 || index >= this.size) throw new RangeError('Get failed. Required index > 0 and index < size')
  17.     return this.data[index]
  18.   }
  20.   getLast () {
  21.     return this.get(this.size - 1)
  22.   }
  24.   set (index, el) {
  25.     if (index < 0 || index >= this.size) throw new RangeError('Get failed. Required index > 0 and index < size')
  26.     this.data[index] = el
  27.   }
  29.   isEmpty () {
  30.     return this.size === 0
  31.   }
  33.   contains (el) {
  34.     for (let i = 0; i < this.size; i ++) {
  35.       if (el.equals(this.data[i])) return true
  36.     }
  37.     return false
  38.   }
  40.   findIndex (el) {
  41.     for (let i = 0; i < this.size; i ++) {
  42.       if (el.equals(this.data[i])) return i
  43.     }
  44.     return -1
  45.   }
  47.   toString () {
  48.     let str = `Array: size = ${ this.size }, capacity = ${ this.data.length }`
  49.     if (this.size) {
  50.       let i
  51.       for (i = 0; i < this.size; i ++) str += ('\n' + this.data[i].toString())
  52.     }
  53.     return str
  54.   }
  56.   add (index, el) {
  57.     if (index < 0 || index > this.size) throw new RangeError('Add failed. Required index > 0 and index < size')
  59.     if (this.size === this.data.length) this.resize(this.size * 2)
  60.     let size = this.size
  61.     while (size > index) {
  62.       this.data[size] = this.data[size - 1]
  63.       size --
  64.     }
  65.     this.data[index] = el
  66.     this.size ++
  67.     return this.size
  68.   }
  70.   addFirst (el) {
  71.     return this.add(0, el)
  72.   }
  74.   addLast (el) {
  75.     return this.add(this.size, el)
  76.   }
  78.   remove (index) {
  79.     if (index < 0 || index >= this.size) throw new RangeError('Delete failed. Required index > 0 and index < size')
  80.     const delEl = this.data[index]
  81.     for (let i = index; i < this.size - 1; i ++) this.data[i] = this.data[i + 1]
  82.     this.size --
  83.     this.data[this.size] = null
  84.     if (this.size === Math.floor(this.data.length / 2)) this.resize(this.size)
  85.     return delEl
  86.   }
  88.   removeFirst () {
  89.     return this.remove(0)
  90.   }
  92.   removeLast () {
  93.     return this.remove(this.size - 1)
  94.   }
  96.   removeElement (el) {
  97.     const index = this.findIndex(el)
  98.     if (index !== -1) this.remove(index)
  99.   }
  101.   resize (len) {
  102.     const newData = new Array(len)
  103.     for (let i = 0; i < this.size; i ++) newData[i] = this.data[i]
  104.     this.data = newData
  105.   }
  106. }
  108. module.exports = CustomArray

栈

栈是一种后进先出的数据结构。例如撤销操作就利用了栈这种数据结构。栈通常会有push、pop、peek等操作。
这里利用动态数组实现栈:

  1. const CustomArray = require('./CustomArray')
  3. class Stack extends CustomArray {
  4.   constructor (capacity) {
  5.     if (typeof capacity === 'number') super(capacity)
  6.     else super(0)
  7.   }
  9.   push (el) {
  10.     return this.addLast(el)
  11.   }
  13.   pop () {
  14.     return this.removeLast()
  15.   }
  17.   peek () {
  18.     return this.getLast()
  19.   }
  21.   toString () {
  22.     let ret = '[Stack]: [\n\t'
  23.     for (let i = 0; i < this.size - 1; i ++) {
  24.       ret += this.data[i].toString() + '\n\t'
  25.     }
  26.     ret += `${this.data[this.size - 1]}\n]`
  27.     return ret
  28.   }
  29. }
  31. module.exports = Stack

队列

和栈不同，队列是先进先出的数据结构，这里同样使用动态数组来实现队列：

  1. const CustomArray = require("./CustomArray")
  3. class Queen extends CustomArray {
  4.   constructor (capacity = 0) {
  5.     super(capacity)
  6.   }
  8.   enqueue (value) {
  9.     return this.addLast(value)
  10.   }
  12.   dequeue () {
  13.     return this.removeFirst()
  14.   }
  16.   getFront () {
  17.     return this.get(0)
  18.   }
  20.   toString () {}
  21. }
  23. module.exports = Queen

上述队列的实现，出队的时间复杂度都是O(n)，我们可以使用循环队列的方式将时间复杂度降低为O(1)，使用两个指针即可：

  1. class LoopQueue {
  2.   constructor (capacity = 1) {
  3.     this.data = new Array(capacity + 1) // 额外使用一个空间来区分队列为空和队列满的情况
  4.     this.size = 0
  5.     this.front = 0
  6.     this.tail = 0
  7.   }
  9.   getCapacity () {
  10.     return this.data.length - 1
  11.   }
  13.   isEmpty () {
  14.     return this.front === this.tail
  15.   }
  17.   getFront () {
  18.     if (this.isEmpty()) throw new RangeError('cannot get front element of empty queue.')
  19.     return this.data[this.front % this.data.length]
  20.   }
  22.   enqueue (el) {
  23.     if (this.size > 0 && this.front === (this.tail + 1) % this.data.length)
  24.       this.resize(this.getCapacity() * 2)
  25.     this.data[this.tail] = el
  26.     this.tail = (this.tail + 1) % this.data.length
  27.     this.size ++
  28.   }
  30.   dequeue () {
  31.     if (this.isEmpty()) throw new RangeError('cannot dequeue element from an empty queue.')
  33.     if (this.size > 0 && this.size === Math.floor(this.getCapacity() / 4))
  34.       this.resize(Math.floor(this.getCapacity() / 2))
  35.     const ret = this.data[this.front]
  36.     this.front = (this.front + 1) % this.data.length
  37.     this.size --
  38.     return ret
  39.   }
  41.   resize (newCapacity) {
  42.     const newData = new Array(newCapacity + 1)
  43.     for (let i = 0; i < this.size; i ++) {
  44.       newData[i] = this.data[(this.front + i) % this.data.length]
  45.     }
  46.     this.data = newData
  47.     this.front = 0
  48.     this.tail = this.size
  49.   }
  51.   toString () {
  52.     let ret = '[Queue]: [front: '
  53.     for (let i = this.front; i != this.tail; i = (i + 1) % this.data.length) {
  54.       ret += this.data[i]
  55.       if ((i + 1) % this.data.length !== this.tail) ret += ', '
  56.     }
  57.     ret += ' tail]'
  58.     return ret
  59.   }
  60. }
  62. module.exports = LoopQueue

也可以不适用size记录队列长度：

  1. /**
  2.  * 版本2：不使用 size
  3.  */
  5. class LoopQueen {
  6.   constructor (capacity = 1) {
  7.     this.data = new Array(capacity + 1)
  8.     this.front = 0
  9.     this.tail = 0
  10.   }
  12.   getCapacity () {
  13.     return Math.max(this.data.length - 1, 0)
  14.   }
  16.   isEmpty () {
  17.     return this.front === this.tail
  18.   }
  20.   getFront () {
  21.     if (this.isEmpty()) throw new RangeError('cannot get the front element of empty queue.')
  22.     return this.data[this.front]
  23.   }
  25.   enqueue (el) {
  26.     if (
  27.       this.getCapacity() > 0 &&
  28.       (this.tail + 1) % this.data.length === this.front
  29.     ) {
  30.       this.resize(this.getCapacity() * 2)
  31.     }
  32.     this.data[this.tail] = el
  33.     this.tail = (this.tail + 1) % this.data.length
  34.   }
  36.   dequeue () {
  37.     if (this.isEmpty()) throw new RangeError('cannot dequeue element from an empty queue.')
  39.     const size = this.tail > this.front
  40.       ? this.tail - this.front
  41.       : this.tail + this.data.length - this.front
  42.     if (
  43.       this.getCapacity() > 0 &&
  44.       size <= Math.floor(this.getCapacity() / 4)
  45.     ) {
  46.       this.resize(Math.floor(this.getCapacity() / 2))
  47.     }
  48.     const ret = this.data[this.front]
  49.     this.front = (this.front + 1) % this.data.length
  50.     return ret
  51.   }
  53.   resize (newCapacity) {
  54.     const newData = new Array(newCapacity + 1)
  55.     const size = this.tail > this.front
  56.       ? this.tail - this.front
  57.       : this.tail + this.data.length - this.front
  58.     for (let i = 0; i < size; i ++) {
  59.       newData[i] = this.data[(this.front + i) % this.data.length]
  60.     }
  61.     this.data = newData
  62.     this.front = 0
  63.     this.tail = size
  64.   }
  66.   toString () {
  67.     let ret = '[Queue]: [front '
  68.     for (let i = this.front; i !== this.tail; i = (i + 1) % this.data.length) {
  69.       ret += this.data[i]
  70.       if ((i + 1) % this.data.length !== this.tail) ret += ', '
  71.     }
  72.     ret += ` tail] => [front: ${this.front}] => [tail: ${this.tail}] => [capacity: ${this.getCapacity()}]`
  73.     return ret
  74.   }
  75. }
  77. module.exports = LoopQueen

上述两种实现都会浪费一个空间，如果不想浪费一个空间可以这样实现：

  1. /**
  2.  * 版本3：不浪费一个空间，使用size来判断队列是否已满
  3.  */
  4. class LoopQueen {
  5.   constructor (capacity = 1) {
  6.     this.data = new Array(capacity)
  7.     this.size = 0
  8.     this.front = 0
  9.     this.tail = 0
  10.   }
  12.   isEmpty () {
  13.     return this.size === 0
  14.   }
  16.   getCapacity () {
  17.     return this.data.length
  18.   }
  20.   getFront () {
  21.     if (this.isEmpty()) throw new RangeError('cannot get the front element of empty queue.')
  22.     return this.data[this.front]
  23.   }
  25.   enqueue (el) {
  26.     if (this.getCapacity() > 0 && this.size === this.getCapacity()) this.resize(this.getCapacity() * 2)
  27.     this.data[this.tail] = el
  28.     this.tail = (this.tail + 1) % this.data.length
  29.     this.size ++
  30.   }
  32.   dequeue () {
  33.     if (this.isEmpty()) throw new RangeError('cannot dequeue element from an empty queue.')
  35.     if (this.getCapacity() > 0 && this.size <= Math.floor(this.getCapacity() / 4)) this.resize(Math.floor(this.getCapacity() / 2))
  36.     const ret = this.data[this.front]
  37.     this.front = (this.front + 1) % this.getCapacity()
  38.     this.size --
  39.     return ret
  40.   }
  42.   resize (newCapacity) {
  43.     const newData = new Array(newCapacity)
  44.     for (let i = 0; i < this.size; i ++) {
  45.       newData[i] = this.data[(this.front + i) % this.data.length]
  46.     }
  47.     this.data = newData
  48.     this.front = 0
  49.     this.tail = this.size
  50.   }
  52.   toString () {
  53.     let ret = '[Queue]: [front '
  54.     for (let i = 0; i < this.size; i ++) {
  55.       ret += this.data[(i + this.front) % this.data.length]
  56.       if (i + 1 !== this.size) ret += ', '
  57.     }
  58.     ret += ` tail] => [front: ${this.front}] => [tail: ${this.tail}] => [capacity: ${this.getCapacity()}]`
  59.     return ret
  60.   }
  61. }
  63. module.exports = LoopQueen