Skip to content

双端队列

· 4 min

双端队列，英语为 double-ended queue，简称 deque。这是一种允许在两端（队列的前端和队列的后端）进行插入和删除操作的数据结构。它既能满足队列的先进先出（FIFO）原则，也能实现栈的后进先出（LIFO）操作，因此在实际应用中非常灵活。

现实生活中的例子

想象一个排队购票的场景——通常我们从队尾进入队伍，但在某些情况下，例如一个刚买票的人需要补充一些信息，可以回到队伍前面；又如队伍末尾的人如果赶时间，可以直接离开队伍。类似地，火车的两端都有车门，可以让乘客从任一侧上下车。

双端队列常见方法

  1. addFront(element)：该方法在双端队列的前端添加新的元素。
  2. addBack(element)该方法在双端队列后端添加新的元素。
  3. removeFront()：该方法会从双端队列前端移除第一个元素。
  4. removeBack()：该方法会从双端队列后端移除第一个元素。
  5. peekFront()：该方法会返回双端队列前端的第一个元素。
  6. peekBack()：该方法会返回双端队列后端的第一个元素。

代码实现

class Deque {
  constructor() {
    this.frontIndex = 0 // 指向队首元素的索引
    this.backIndex = 0 // 指向队尾元素的下一个可插入的位置
    this.items = {} // 存储双端队列里面的所有元素
  }


  // 先实现一些辅助方法：size、isEmpty、clear
  size() {
    return this.backIndex - this.frontIndex
  }
  isEmpty() {
    return this.size() === 0
  }
  clear() {
    this.items = {}
    this.frontIndex = 0
    this.backIndex = 0
  }
  // 添加到前面
  addFront(item) {
    // 1. 如果队列为空，那么添加到前端和后端的效果是一样的
    if (this.isEmpty()) {
      this.addBack(item)
      return
    }


    // 2. 如果队列非空，并且 frontIndex > 0
    // 我们可以在 frontIndex - 1 位置添加新的元素
    if (this.frontIndex > 0) {
      this.frontIndex--
      this.items[this.frontIndex] = item
      return
    }


    // 3. 如果 frontIndex === 0
    // 我们需要将所有的元素向后面移动，为索引为 0 的位置腾出空间
    for (let i = this.backIndex; i > 0; i--) {
      this.items[i] = this.items[i - 1]
    }
    // 更新队尾的索引，因为所有元素都向后移动了
    // 所以 backIndex 需要更新
    this.backIndex++
    this.frontIndex = 0
    this.items[this.frontIndex] = item
  }
  // 添加到后面
  addBack(item) {
    this.items[this.backIndex] = item
    this.backIndex++
  }
  removeFront() {
    if (this.isEmpty()) {
      return undefined
    }
    // 取出队首的元素
    const result = this.items[this.frontIndex]
    // 需要删除这个元素
    delete this.items[this.frontIndex]
    this.frontIndex++
    return result
  }
  removeBack() {
    if (this.isEmpty()) {
      return undefined
    }
    this.backIndex-- // 现在指向队尾元素
    // 取出队尾
    const result = this.items[this.backIndex]
    delete this.items[this.backIndex]
    return result
  }
  peekFront() {
    if (this.isEmpty()) {
      return undefined
    }
    return this.items[this.frontIndex]
  }
  peekBack() {
    if (this.isEmpty()) {
      return undefined
    }
    return this.items[this.backIndex - 1]
  }
  // 返回队列的字符串表示
  toString() {
    if (this.isEmpty()) {
      return ''
    }
    // 先把队首元素作为字符串的起始
    let objString = `${this.items[this.frontIndex]}`
    // 从队首下一位遍历到队尾
    for (let i = this.frontIndex + 1; i < this.backIndex; i++) {
      objString = `${objString},${this.items[i]}`
    }
    return objString
  }
}