学习JavaScript数据结构与算法第五章

三槐 / 2023-05-08 / 原文

五，队列和双端队列

我们已经学习了栈。队列和栈非常类似，但是使用了与后进先出不同的原则。

双端队列是一种将栈的原则和队列的原则混合在一起的数据结构。

5.1 队列数据结构

队列是遵循先进先出（FIFO，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

在计算机科学中，一个常见的例子就是打印队列。比如说我们需要打印五份文档。我们会打开每个文档，然后点击打印按钮。每个文档都会被发送至打印队列。第一个发送到打印队列的文档会首先被打印，以此类推，直到打印完所有文档

// @ts-check

class Queue {
  #count = 0
  #lowestCount = 0
  #items = {}
  // 向队列添加元素

  enqueue(element) {
    this.#items[this.#count] = element
    this.#count++
  }

  // 从队列移除元素
  dequeue() {
    if (this.isEmpty()) return undefined

    const result = this.#items[this.#lowestCount]
    delete this.#items[this.#lowestCount]
    this.#lowestCount++
    return result
  }

  // 查看队列头元素
  peek() {
    if (this.isEmpty()) return undefined

    return this.#items[this.#lowestCount]
  }

  // 检查队列是否为空
  isEmpty() {
    return this.size() === 0
  }

  // 获取它的长度
  size() {
    return this.#count - this.#lowestCount
  }

  // 清空队列
  clear() {
    this.#items = {}
    this.#count = 0
    this.#lowestCount = 0
  }

  // toString方法
  toString() {
    if (this.isEmpty()) return ''

    let objString = `${this.#items[this.#lowestCount]}`

    for (let i = this.#lowestCount + 1; i < this.#count; i++) {
      objString = `${objString},${this.#items[i]}`
    }
    return objString
  }
}


const queue = new Queue()
console.log(queue.isEmpty())

queue.enqueue('John')
queue.enqueue('Jack')
console.log(queue)
console.log(queue.toString())


queue.enqueue('Camila')
console.log(queue.toString())
console.log(queue.size())
console.log(queue.isEmpty())

queue.dequeue()
queue.dequeue()
console.log(queue.toString())

5.2 双端队列数据结构

双端队列（deque，或称 double-ended queue）是一种允许我们同时从前端和后端添加和移除元素的特殊队列。

在计算机科学中，双端队列的一个常见应用是存储一系列的撤销操作。每当用户在软件中进行了一个操作，该操作会被存在一个双端队列中（就像在一个栈里）。当用户点击撤销按钮时，该操作会被从双端队列中弹出，表示它被从后面移除了。在进行了预先定义的一定数量的操作后，最先进行的操作会被从双端队列的前端移除。由于双端队列同时遵守了先进先出和后进先出原则，可以说它是把队列和栈相结合的一种数据结构。

class Deque {
  #count = 0
  #lowestCount = 0
  #items = {}
  // 向双端队列的前端添加元素
  addFront(element) {
    if (this.isEmpty()) {
      this.addBack(element)
    } else if (this.#lowestCount > 0) {
      this.#lowestCount--
      this.#items[this.#lowestCount] = element
    } else {
      for (let i = this.#count; i > 0; i--) {
        this.#items[i] = this.#items[i - 1]
      }
      this.#count++
      this.#lowestCount = 0
      this.#items[0] = element
    }
  }

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

  isEmpty() {
    return this.#count - this.#lowestCount === 0
  }

  toString() {
    if (this.isEmpty()) return ''

    let objString = `${this.#items[this.#lowestCount]}`
    for (let i = this.#lowestCount + 1; i < this.#count; i++) {
      objString = `${objString},${this.#items[i]}`
    }
    return objString
  }

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

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

    const result = this.#items[this.#lowestCount]
    delete this.#items[this.#lowestCount]
    this.#lowestCount++
    return result

  }
  removeBack() {
    if (this.isEmpty()) return undefined
    const result = this.#items[this.#count]
    delete this.#items[this.#count]
    this.#count--
    return result
  }

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

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

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

}

const deque = new Deque()
console.log(deque.isEmpty())

deque.addBack('John')
deque.addBack('Jack')
console.log(deque.toString())


deque.addBack('Camila')
console.log(deque.toString())
console.log(deque.size())

console.log(deque.isEmpty())

deque.removeFront()
console.log(deque.toString())

deque.removeBack()
console.log(deque.toString())

deque.addFront('John')
console.log(deque.toString())