三、Typescript数据结构与算法-队列

北京

队列(Queue)，它是一种受限的线性表，先进先出(FIFO First In First Out)

受限之处在于它只允许在队列的前端（front）进行删除操作

而在队列的后端（rear）进行插入操作

实现

import IQueue from "./IQueue";
export class ArrayQueue<T> implements IQueue<T> {
  private data: T[] = [];
  // 入队
  enqueue(element: T): void {
    this.data.push(element);
  }
  // 出列
  dequeue(): T | undefined {
    return this.data.shift();
  }
  // 队首
  peek(): T | undefined {
    return this.data[0];
  }
  isEmpty(): boolean {
    return this.data.length === 0;
  }
  get size(): number {
    return this.data.length;
  }
  }

export default interface IQueue<T> {
  enqueue(element: T): void;
  dequeue(): T | undefined;
  peek(): T | undefined;
  isEmpty(): boolean;
  get size(): number;
}

ts 类 get

IQueue 和队列的 IStack 都存在相同的方法，可以写成一个通过继承来实现

export default interface IList<T> {
  peek(): T | undefined;
  isEmpty(): boolean;
  get size(): number;
}

import IList from "../types/ILIst";
export default interface IQueue<T> extends IList<T> {
  enqueue(element: T): void;
  dequeue(): T | undefined;
}

面试题 — 击鼓传花

简述：一堆人围成圈，数数，1、2、3 数到 3 的淘汰，重新数，直到只剩一个人

import ArrayQueue from "./queue";
/**
 *
 * @param names
 * @param num
 * @returns
 */
// function hotPotato<T extends string[], U>(names: T, num: U): number {

function hotPotato(names: string[], num: number) {
  const queue = new ArrayQueue<string>();
  // 依次入队
  for (const name of names) {
    queue.enqueue(name);
  }
  // 只剩一个人结束循环
  while (queue.size > 1) {
    for (let i = 1; i < num; i++) {
      queue.enqueue(queue.dequeue()!);
    }
    queue.dequeue();
  }
  return names.indexOf(queue.dequeue()!);
}