队列和双端队列

队列是遵循先进先出FIFO原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。

队列的一些方法

• enqueue(element[s])：向队列尾部添加一个（或多个）新的项。
• dequeue()：移除队列的第一项并返回被移除的元素
• peek()/front()：返回队列中第一个元素——最先被添加，也将是最先被移出的元素。队列不做任何变动。
• isEmpty()：返回队列是否为空
• size()：返回队列中元素的个数

创建队列

/**
 * 队列
 */
export default class Queue<T> {
  private items: object
  private count: number
  private header: number
  constructor() {
    this.items = {}
    this.count = this.header = 0
  }

  /**
   * 入队列
   * @param element
   * @returns 当前队列的数量
   */
  enqueue(element: T): number {
    this.items[this.count++] = element
    return this.size()
  }

  /**
   * 出队列
   * @returns 出队列的元素
   */
  dequeue(): T {
    if (this.isEmpty()) return undefined
    const res = this.items[this.header]
    delete this.items[this.header]
    this.header++
    return res
  }

  /**
   * 查看队首的元素
   * @return 队首位的元素
   */
  peek(): T {
    if (this.isEmpty()) return undefined
    return this.items[this.header]
  }

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

  /**
   * 返回队列是否为空
   * @returns boolean
   */
  isEmpty(): boolean {
    return this.size() === 0
  }

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

  /**
   * 返回队列元素组成的字符串
   * @returns string
   */
  toString(): string {
    if (this.isEmpty()) return 'queue is empty!'
    let res = this.items[this.header].toString()
    for (let i = this.header + 1; i < this.count; i++) {
      res = `${res}, ${this.items[i].toString()}`
    }
    return res
  }
}

双端队列

双端队列(deque)是一种允许我们同时从前端和后端添加和删除元素的特殊队列。
在计算机中，双端队列的一个常见应用场景就是存储一系列可撤销的操作。每当用户在软件中进行了一个操作，该操作就会被存在一个双端队列中。每当用户点击撤销按钮时，该操作就会从双端队列中弹出，表示他从后面被移除了。在进行了预先定义的一定数量的操作后，最先进行的操作会被从双端队列的前端移除。
由于双端队列同时遵守了先进先出和后进先出的原则，所以可以说他是队列和栈组合的一种数据结构

创建双端队列Deque

/**
 * 双端队列
 */
export default 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
  }
}

队列和双端队列实践

循环队列——击鼓传花游戏

export const hotPotato = (
  elementList: [],
  num: number
): { eliminated: Array<any>; winner: any } => {
  // 创建一个队列
  const queue = new Queue()
  const eliminated = []
  // 将elementList按顺序放进队列中
  for (let element in elementList) {
    queue.enqueue(element)
  }
  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue())
    }
		// 将淘汰的人放入eliminated中
    eliminated.push(queue.dequeue())
  }
  return {
    eliminated,
    winner: queue.dequeue(),
  }
}

回文检查器**

import Deque from '../../ds/deque'
export const palindromeChecker = (str: string): boolean => {
  if (!str) return false
  let head: string, tail: string
  let flag = true
  const deque = new Deque<string>()

  // 去除空格、转换成小写
  str = str.toLowerCase().trim().split(' ').join('')
  for (let char of str) {
    deque.addTail(char)
  }
  while (deque.size() > 1) {
    head = deque.getHead()
    tail = deque.getTail()
    if (head !== tail) {
      flag = false
      break
    }
  }
  return flag
}