介绍

双端队列（deque，全名 double-ended queue）是一种具有队列和栈性质的抽象数据类型。双端队列中的元素可以从两端弹出，插入和删除操作限定在队列的两边进行。

操作

双端队列可以在队列任意一端入队和出队。此外，经常还会有一个查看（Peek）操作，返回该端的数据而不将其出队。

操作的名称依语言的不同而不同；主流实现包括：

注意：JavaScript 的数组就是一个双端队列。

实现

JavaScript

class Deque {
  /**
   * Creates a deque
   * @param {array} [elements]
   */
  constructor(elements) {
    this._backElements = Array.isArray(elements) ? elements : [];
    this._frontElements = [];
    this._backOffset = 0;
    this._frontOffset = 0;
  }

  /**
   * Adds an element at the front of the queue
   * @public
   * @param {any} element
   */
  pushFront(element) {
    this._frontElements.push(element);
    return this;
  }

  /**
   * Adds an element at the back of the queue
   * @public
   * @param {any} element
   */
  pushBack(element) {
    this._backElements.push(element);
    return this;
  }

  /**
   * Dequeues the front element in the queue
   * @public
   * @returns {any}
   */
  popFront() {
    if (this.size() === 0) {
      return null;
    }

    if (this._frontElements.length > 0) {
      const front = this._frontElements.pop();
      if (this._frontOffset >= this._frontElements.length) {
        this._frontElements = this._frontElements.slice(this._frontOffset);
        this._frontOffset = 0;
      }
      return front;
    }

    const front = this.front();
    this._backOffset += 1;

    if (this._backOffset * 2 < this._backElements.length) {
      return front;
    }

    this._backElements = this._backElements.slice(this._backOffset);
    this._backOffset = 0;
    return front;
  }

  /**
   * Dequeues the back element of the queue
   * @public
   * @returns {any}
   */
  popBack() {
    if (this.size() === 0) {
      return null;
    }

    if (this._backElements.length > 0) {
      const back = this._backElements.pop();
      if (this._backOffset >= this._backElements.length) {
        this._backElements = this._backElements.slice(this._backOffset);
        this._backOffset = 0;
      }
      return back;
    }

    const back = this.back();
    this._frontOffset += 1;
    if (this._frontOffset * 2 < this._frontElements.length) {
      return back;
    }

    this._frontElements = this._frontElements.slice(this._frontOffset);
    this._frontOffset = 0;
    return back;
  }

  /**
   * Returns the front element of the queue
   * @public
   * @returns {any}
   */
  front() {
    if (this.size() === 0) {
      return null;
    }

    if (this._frontElements.length > 0) {
      return this._frontElements[this._frontElements.length - 1];
    }

    return this._backElements[this._backOffset];
  }

  /**
   * Returns the back element of the queue
   * @public
   * @returns {any}
   */
  back() {
    if (this.size() === 0) {
      return null;
    }

    if (this._backElements.length > 0) {
      return this._backElements[this._backElements.length - 1];
    }

    return this._frontElements[this._frontOffset];
  }

  /**
   * Returns the number of elements in the deque
   * @public
   * @returns {number}
   */
  size() {
    const frontSize = this._frontElements.length - this._frontOffset;
    const backSize = this._backElements.length - this._backOffset;
    return frontSize + backSize;
  }

  /**
   * Checks if the queue is empty
   * @public
   * @returns {boolean}
   */
  isEmpty() {
    return this.size() === 0;
  }

  /**
   * Returns the remaining elements in the queue as an array
   * @public
   * @returns {array}
   */
  toArray() {
    const backElements = this._backElements.slice(this._backOffset);
    const frontElements = this._frontElements.slice(this._frontElements);
    return frontElements.reverse().concat(backElements);
  }

  /**
   * Clears the queue
   * @public
   */
  clear() {
    this._backElements = [];
    this._frontElements = [];
    this._backOffset = 0;
    this._frontOffset = 0;
  }

  /**
   * Creates a shallow copy of the queue
   * @public
   * @return {Deque}
   */
  clone() {
    return new Deque(this.toArray());
  }

  /**
   * Creates a deque from an existing array
   * @public
   * @static
   * @param {array} elements
   * @return {Deque}
   */
  static fromArray(elements) {
    return new Deque(elements);
  }
}

参考

• Double-ended queue - Wikipedia (opens new window)
• 双端队列 - 维基百科，自由的百科全书 (opens new window)