export default class Queue<T> {
  private count: number;
  private lowestCount: number;
  private items: { [key: number]: T };
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }
  /**加入队列*/
  public enqueue(item: T): void {
    // 队列的末尾添加元素: 将队列的大小作为key
    this.items[this.count] = item;
    this.count++;
  }
  /**拿出队首*/
  public dequeue(): T {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    // 删除队首元素
    delete this.items[this.lowestCount];
    // 队首元素自增
    this.lowestCount++;
    return result;
  }
  /**是否为空队列*/
  public isEmpty(): boolean {
    return this.count - this.lowestCount === 0;
  }
  /**查看下一个出队元素 */
  public peek(): T {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }
  /**队列个数*/
  public size(): number {
    return this.count - this.lowestCount;
  }
  /**清空队列*/
  public clear(): void {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }
  public toString(): string {
    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;
  }
}

/**
 * 双端队列
 */
export class Deque<T> {
  private items: {}
  private lowestCount: number
  private count: number

  constructor() {
    this.items = {}
    this.lowestCount = 0
    this.count = 0
  }

  /**
   * 向队列的尾端添加元素
   * @param element
   * @returns size
   */
  addTail(element: T): number {
    this.items[this.count++] = element
    return this.size()
  }

  /**
   * 向队列头部添加元素
   * @param element
   * @returns size
   */
  addHead(element: T): number {
    if (this.count === 0) {
      this.addTail(element)
    } else if (this.lowestCount > 0) {
      this.items[--this.lowestCount] = element
    } else {
      for (let i = this.count; i > this.lowestCount; i--) {
        this.items[i] = this.items[i - 1]
      }
      this.count++
      this.items[0] = element
    }
    return this.size()
  }

  /**
   * 返回队列尾部的元素
   * @returns T
   */
  getTail(): T {
    if (this.isEmpty()) return undefined
    this.count--
    const res = this.items[this.count]
    delete this.items[this.count]
    return res
  }

  /**
   * 返回头部元素
   * @returns T
   */
  getHead(): T {
    if (this.isEmpty()) return undefined
    const res = this.items[this.lowestCount]
    delete this.items[this.lowestCount]
    this.lowestCount++
    return res
  }

  /**
   * 看一下队列首部的元素
   * @returns T
   */
  peekHead(): T {
    if (this.isEmpty()) return undefined
    return this.items[this.lowestCount]
  }

  /**
   * 看一下队列尾部的元素
   * @return T
   */
  peekTail(): T {
    if (this.isEmpty()) return undefined
    return this.items[this.count - 1]
  }

  /**
   * 返回元素的个数
   * @returns number
   */
  size(): number {
    return this.count - this.lowestCount
  }

  /**
   * 判断队列是否为空
   */
  isEmpty(): boolean {
    return this.size() === 0
  }

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

  toString(): string {
    if (this.isEmpty()) {
      return ''
    }
    let res = this.items[this.lowestCount].toString()
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      res = `${res}, ${this.items[i].toString()}`
    }
    return res
  }
}