JavaScript数据结构与算法

数组结构

参考：https://aboss.top/post/173/

栈结构

栈(stack)又名堆栈，是一种运算受限的线性表，限定仅在表尾进行插入和删除操作。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素称作进栈，从一个栈删除元素称作出栈。

特点：后进先出，即 Last in First out (LIFO)。

class Stack {
  #items = [] //# 符号声明私有属性，ES13 新特性

  pop() {
    return this.#items.pop() //出栈
  }

  push(data) {
    return this.#items.push(data) //进栈
  }

  peek() {
    return this.#items.at(-1) //栈顶
  }

  isEmpty() {
    return this.#items.length === 0
  }

  size() {
    return this.#items.length
  }

  clear() {
    this.#items = []
  }

  toString() {
    return this.#items.join(" ")
  }
}

// 十进制转 2 8 16 进制
function convert(decNumber, base) {
  let remStack = new Stack()
  let number = decNumber
  let string = ""
  let baseString = "0123456789ABCDEF"

  while (number > 0) {
    remStack.push(number % base)
    number = Math.floor(number / base)
  }

  while (!remStack.isEmpty()) {
    string += baseString[remStack.pop()]
  }

  return string
}

convert(500, 16)

队列结构

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端进行删除操作，而在表的后端进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾（入队），进行删除操作的端称为队头（出队）。队列中没有元素时，称为空队列。

特点：先进先出，即 First in First out(FIFO)。

封装与应用

class Queue {
  #items = {}
  #lowCount = 0
  #count = 0

  dequeue() {
    if (this.isEmpty()) {
      return undefined
    }

    let res = this.#items[this.#lowCount]
    delete this.#items[this.#lowCount]
    this.#lowCount++
    return res //出队
  }

  enqueue(data) {
    this.#items[this.#count] = data //入队
    this.#count++
  }

  front() {
    return this.#items[this.#lowCount] //队头
  }

  isEmpty() {
    return this.size() === 0
  }

  size() {
    return this.#count - this.#lowCount
  }

  clear() {
    this.#items = {}
    this.#count = 0
    this.#lowCount = 0
  }

  toString() {
    let str = ""
    for (let i = this.#lowCount; i < this.#count; i++) {
      str += `${this.#items[i]} `
    }

    return str
  }
}

// 击鼓传花游戏
function game(list, num) {
  let queue = new Queue()
  for (let i = 0; i < list.length; i++) {
    queue.enqueue(list[i])
  }

  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue())
    }

    console.log(queue.dequeue(), "淘汰了")
  }

  return queue.dequeue() + " 获胜"
}

game(["张三", "李四", "王五", "赵六", "孙七"], 7)

双端队列

class DeQueue {
  #items = {}
  #lowCount = 0 //队头索引
  #count = 0

  removeFront() {
    if (this.isEmpty()) {
      return undefined
    }

    let res = this.#items[this.#lowCount]
    delete this.#items[this.#lowCount]
    this.#lowCount++

    return res
  }

  removeBack() {
    if (this.isEmpty()) {
      return
    }

    this.#count--
    const res = this.#items[this.#count]
    delete this.#items[this.#count]

    return res
  }

  addFront(data) {
    if (this.isEmpty()) {
      this.addBack(data)
    } else {
      if (this.#lowCount > 0) {
        this.#lowCount--
        this.#items[this.#lowCount] = data
      } else {
        // #lowCount=0
        for (let i = this.#count; i > 0; i--) {
          this.#items[i] = this.#items[i - 1]
        }
      }
    }
  }

  addBack(data) {
    this.#items[this.#count] = data
    this.#count++
  }

  peekFront() {
    return this.#items[this.#lowCount]
  }

  peekBack() {
    return this.#items[this.#count - 1]
  }

  isEmpty() {
    return this.size() === 0
  }

  size() {
    return this.#count - this.#lowCount
  }

  clear() {
    this.#items = {}
    this.#count = 0
    this.#lowCount = 0
  }

  toString() {
    let str = ""
    for (let i = this.#lowCount; i < this.#count; i++) {
      str += `${this.#items[i]} `
    }

    return str
  }
}

// 回文字符串检查
function test(str) {
  const lowstr = str.toLocaleLowerCase().split(" ").join("")
  let dequeue = new DeQueue()

  for (let i = 0; i < lowstr.length; i++) {
    dequeue.addBack(lowstr[i])
  }

  let isEqual = true
  while (dequeue.size() > 1) {
    if (dequeue.removeFront() != dequeue.removeBack()) {
      isEqual = false
      break
    }
  }

  return isEqual
}

test("上海自来水来自海上")

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

链表的特点

1. 插入、删除数据效率高O(1)级别(只需更改指针指向即可)，随机访问效率低O(n)级别(需要从链头至链尾进行遍历)
2. 和数组相比，内存空间消耗更大，因为每个存储数据的节点都需要额外的空间存储后继指针。

单链表

每个节点只包含一个指针，即后继指针。

class Node {
  constructor(element) {
    this.element = element
    this.next = null
  }
}

class LinkedList {
  constructor() {
    this.count = 0
    this.head = null
  }

  push(element) {
    const node = new Node(element)

    if (this.head === null) {
      this.head = node
    } else {
      let current = this.head

      while (current.next !== null) {
        current = current.next
      }

      current.next = node
    }

    this.count++
  }

  getNodeAt(index) {
    if (index >= 0 && index < this.count) {
      let node = this.head
      for (let i = 0; i < index; i++) {
        node = node.next
      }

      return node
    }

    return
  }

  // 指定位置删除
  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head
      if (index === 0) {
        this.head = this.head.next
      } else {
        let previous = this.getNodeAt(index - 1)
        current = previous.next
        previous.next = current.next
      }

      this.count--
      return current.element
    }

    return
  }

  equalFn(a, b) {
    return JSON.stringify(a) === JSON.stringify(b)
  }

  indexOf(element) {
    let current = this.head
    for (let i = 0; i < index; i++) {
      if (this.equalFn(element, current.element)) {
        return i
      }
      current = current.next
    }

    return -1
  }

  // 指定元素删除
  remove(element) {
    const index = this.indexOf(element)
    return this.removeAt(index)
  }

  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element)
      if (index === 0) {
        const current = this.head
        node.next = current
        this.head = node
      } else {
        const previous = this.getNodeAt(index - 1)
        const current = previous.next

        node.next = current
        previous.next = node
      }

      this.count++
      return true
    }

    return false
  }

  isEmpty() {
    return this.size() === 0
  }

  size() {
    return this.count
  }

  getHead() {
    return this.head
  }
}

// 回文字符串检查
function test(str) {
  const lowstr = str.toLocaleLowerCase().split(" ").join("")
  let sll = new LinkedList()

  for (let i = 0; i < lowstr.length; i++) {
    sll.push(lowstr[i])
  }

  let isEqual = true
  while (sll.size() > 1) {
    if (sll.removeAt(0) !== sll.removeAt(sll.size() - 1)) {
      isEqual = false
      break
    }
  }

  return isEqual
}

test("上海自来水来自海上")

击鼓传花游戏使用单链表：

// 击鼓传花游戏
function game(list, num) {
  let queue = new LinkedList()
  for (let i = 0; i < list.length; i++) {
    queue.push(list[i])
  }

  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      queue.push(queue.removeAt(0))
    }

    console.log(queue.removeAt(0), "淘汰了")
  }

  return queue.removeAt(0) + " 获胜"
}

game(["张三", "李四", "王五", "赵六", "孙七"], 7)

十进制转 2 8 16 进制：

// 十进制转 2 8 16 进制
function convert(decNumber, base) {
  let remStack = new LinkedList()
  let number = decNumber
  let string = ""
  let baseString = "0123456789ABCDEF"

  while (number > 0) {
    remStack.push(number % base)
    number = Math.floor(number / base)
  }

  while (!remStack.isEmpty()) {
    string += baseString[remStack.removeAt(remStack.size() - 1)]
  }

  return string
}

convert(500, 16)

双链表

class DoublyNode extends Node {
  constructor(element) {
    super(element)
    this.prev = null
  }
}

class DoublyLinkedList extends LinkedList {
  constructor() {
    super()
    this.tail = null
  }

  push(element) {
    const node = new DoublyNode(element)
    if (this.head === null) {
      this.head = node
      this.tail = node
    } else {
      this.tail.next = node
      node.prev = this.tail
      this.tail = node
    }

    this.count++
  }

  remove(element) {
    const index = this.indexOf(element)
    return this.removeAt(index)
  }

  insert(element, index) {
    if (index >= 0 && index <= this.count) {
      const node = new DoublyNode(element)
      let current = this.head
      if (index === 0) {
        if (this.head === null) {
          this.head = node
          this.tail = node
        } else {
          node.next = this.head
          this.head.prev = node
          this.head = node
        }
      } else if (index === this.count) {
        current = this.tail
        current.next = node
        node.prev = current
        this.tail = node
      } else {
        const previous = this.getNodeAt(index - 1)
        current = previous.next

        node.next = current
        current.prev = node
        previous.next = node
        node.prev = previous
      }

      this.count++
      return true
    }

    return false
  }

  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head
      if (index === 0) {
        this.head = current.next
        if (this.count === 1) {
          this.tail = null
        } else {
          this.head.prev = null
        }
      } else if (index === this.count - 1) {
        current = this.tail
        this.tail = current.prev
        this.tail.next = null
      } else {
        let previous = this.getNodeAt(index - 1)
        current = previous.next
        previous.next = current.next
        current.next.prev = previous
      }

      this.count--
      return current.element
    }

    return
  }

  getHead() {
    return this.head
  }

  getTail() {
    return this.tail
  }
}

循环链表

循环链表和链表之间唯一的区别在于，最后一个元素指向下一个元素的指针(tail.next)不是undefined，而是指向第一个元素(head)。

class CircularLinkedList extends LinkedList {
  constructor() {
    super()
  }

  push(element) {
    const node = new Node(element)
    let current
    if (this.head === null) {
      this.head = node
    } else {
      current = this.getNodeAt(this.size() - 1)
      current.next = node
    }

    node.next = this.head
    this.count++
  }

  insert() {
    if (index >= 0 && index <= this.count) {
      const node = new Node(element)
      let current = this.head
      if (index === 0) {
        if (this.head === null) {
          this.head = node
          node.next = this.head
        } else {
          node.next = current
          this.head = node

          current = this.getNodeAt(this.size() - 1)
          current.next = this.head
        }
      } else {
        const previous = this.getNodeAt(index - 1)
        node.next = previous.next
        previous.next = node
      }

      this.count++
      return true
    }

    return false
  }

  removeAt(index) {
    if (index >= 0 && index < this.count) {
      let current = this.head
      if (index === 0) {
        if (this.size() === 1) {
          this.head = null
        } else {
          let last = this.getNodeAt(this.size() - 1)
          this.head = this.head.next
          last.next = this.head
        }
      } else {
        const previous = this.getNodeAt(index - 1)
        current = previous.next
        previous.next = current.next
      }

      this.count--
      return current.element
    }

    return
  }
}