hanyeah

队列经常用，先进先出。一头进，另一头出。

双向队列，就是一头进，另一头出；另一头进，一头出。

这里要介绍的是连续双向队列。

最初是为了解决流体（液体或气体）在导管中流动的问题。

导管中的流体可以正着流，也可以反向流，所以就需要双向队列，一段流体的长度是连续的，不确定的，所以需要连续双向队列。但是管子的总长度是固定的。

代码如下（typescript）：

class Cdeque<T> {
    private item0: CdequeItem<T>; // 队首元素
    private item1: CdequeItem<T>; // 队尾元素
    private length: number; // 队列长度
    private lastRemoveArr: CdequeItem<T>[] = [];
    private lastAddedArr: CdequeItem<T>[] = [];
    constructor(length: number, data: T) {
      this.length = length;
      this.item0 = new CdequeItem(this.length, data);
      this.item1 = this.item0;
    }

    public getLength(): number {
      return this.length;
    }

    public destroy(): void {
      this.forEach((item: CdequeItem<T>) => {
        item.destroy();
      });
      this.item0 = null;
      this.item1 = null;
      this.lastRemoveArr = null;
    }

    public resize(length: number, data: T): void {
      if (length > this.length) {
        const d: number = length - this.length;
        this.length = length;
        this.unshift(d, data);
      } else if (length < this.length) {
        this.length = length;
        this.tryRemoveFromFront();
      }
    }

    /**
     * 获取最近一次移除的。
     */
    public getLastRemoveArr(): CdequeItem<T>[] {
      return this.lastRemoveArr;
    }

    /**
     * 获取最后一次添加的
     */
    public getLastAddedArr(): CdequeItem<T>[] {
      return this.lastAddedArr;
    }

    /**
     * 是否能合并。
     * @param data0
     * @param data1
     * @return boolean
     */
    public canMerge(data0: T, data1: T): boolean {
      return data0 === data1;
    }

    /**
     * 正向遍历
     * @param callBack
     */
    public forEach(callBack: (item: CdequeItem<T>) => void): void {
      let item: CdequeItem<T> = this.item0;
      let next: CdequeItem<T>;
      while (item !== this.item1) {
        next = item.next;
        callBack(item);
        item = next;
      }
      callBack(this.item1);
    }

    /**
     * 反向遍历
     * @param callBack
     */
    public reverseForEach(callBack: (item: CdequeItem<T>) => void): void {
      let item: CdequeItem<T> = this.item1;
      let prev: CdequeItem<T>;
      while (item !== this.item0) {
        prev = item.prev;
        callBack(item);
        item = prev;
      }
      callBack(this.item0);
    }

    /**
     * 在队列头部添加
     * @param length
     * @param data
     */
    public unshift(length: number, data: T): CdequeItem<T>[] {
      this.lastAddedArr = [];
      this.lastAddedArr.push(new CdequeItem(length, data));
      if (this.canMerge(data, this.item0.data)) {
        this.item0.length += length;
      } else {
        const item: CdequeItem<T> = new CdequeItem(length, data);
        item.next = this.item0;
        this.item0.prev = item;
        this.item0 = item;
      }
      this.tryRemoveFromEnd();
      return this.lastRemoveArr;
    }

    /**
     * 在队列尾部添加
     * @param length
     * @param data
     */
    public push(length: number, data: T): CdequeItem<T>[] {
      this.lastAddedArr = [];
      this.lastAddedArr.push(new CdequeItem(length, data));
      if (this.canMerge(data, this.item1.data)) {
        this.item1.length += length;
      } else {
        const item: CdequeItem<T> = new CdequeItem(length, data);
        item.prev = this.item1;
        this.item1.next = item;
        this.item1 = item;
      }
      this.tryRemoveFromFront();
      return this.lastRemoveArr;
    }

    private tryRemoveFromEnd(): void {
      this.lastRemoveArr = [];
      this.updatePrevLength();
      this.cutOff();
    }

    private updatePrevLength(): void {
      let item: CdequeItem<T> = this.item0;
      item.prevLength = 0;
      while (item !== this.item1) {
        item.next.prevLength = item.prevLength + item.length;
        item = item.next;
      }
    }

    private cutOff(): void {
      while (this.item1.prevLength >= this.length) {
        this.remove();
      }
      if (this.item1.length + this.item1.prevLength > this.length) {
        this.lastRemoveArr.push(new CdequeItem<T>(this.item1.length + this.item1.prevLength - this.length, this.item1.data));
        this.item1.length = this.length - this.item1.prevLength;
      }
    }

    private remove(): void {
      this.lastRemoveArr.push(new CdequeItem<T>(this.item1.length, this.item1.data));
      this.item1 = this.item1.prev;
      this.item1.next.destroy();
      this.item1.next = this.item1;
    }

    private tryRemoveFromFront(): void {
      this.lastRemoveArr = [];
      this.updateNextLength();
      this.reverseCutOff();
    }

    private updateNextLength(): void {
      let item: CdequeItem<T> = this.item1;
      item.nextLength = 0;
      while (item !== this.item0) {
        item.prev.nextLength = item.nextLength + item.length;
        item = item.prev;
      }
    }

    private reverseCutOff(): void {
      while (this.item0.nextLength >= this.length) {
        this.reverseRemove();
      }
      if (this.item0.length + this.item0.nextLength > this.length) {
        this.lastRemoveArr.push(new CdequeItem<T>(this.item0.length + this.item0.nextLength - this.length, this.item0.data));
        this.item0.length = this.length - this.item0.nextLength;
      }
    }

    private reverseRemove(): void {
      this.lastRemoveArr.push(new CdequeItem<T>(this.item0.length, this.item0.data));
      this.item0 = this.item0.next;
      this.item0.prev.destroy();
      this.item0.prev = this.item0;
    }

  }

一段流体柱的定义，如下：

class CdequeItem<T> {
    public length: number;
    public data: T;
    public next: CdequeItem<T>;
    public prev: CdequeItem<T>;
    public prevLength: number;
    public nextLength: number;
    constructor(length: number, data: T) {
      this.length = length;
      this.data = data;
      this.next = this;
      this.prev = this;
      this.prevLength = 0;
      this.nextLength = 0;
    }

    public destroy(): void {
      this.next = null;
      this.prev = null;
      this.data = null;
    }

    public clone(): CdequeItem<T> {
      return new CdequeItem<T>(this.length, this.data);
    }
  }