Estrutura de Dados - Fila

30 de agosto, 2022 - 3 mins

Descrição

Uma fila é uma coleção ordenada de itens baseada em FIFO (First In First Out), também conhecido como first-come first-served. Novos elementos são adicionados na cauda e a remoção na frente. O elemento mais recente na fila deve esperar no final dela.

Um Exemplo de fila na vida real é a típica fila que se forma ocasionalmente nos bancos.

Repositório com os Exemplos.

Exemplos

Fila

class Queue {
  public items: { [key: number]: number | string };
  private count: number;
  private lowestCount: number;

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

  enqueue(element: number | string) {
    this.items[this.count] = element;
    this.count++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }

    const value = this.items[this.lowestCount];
    delete this.items[this.lowestCount];

    this.lowestCount++;

    return value;
  }

  peek() {
    if (this.isEmpty()) {
      return undefined;
    }

    return this.items[this.lowestCount];
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    return this.count - this.lowestCount;
  }

  clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }

  toString() {
    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;
  }
}

Exercícios

Batata Quente

function hotPotato(names: string[], times: number) {
  const eliminated = [];
  const queue = new Queue();

  names.forEach(name => queue.enqueue(name));

  while (queue.size() > 1) {
    for (let i = 1; i <= times; i++) {
      queue.enqueue(queue.dequeue());
    }
    eliminated.push(queue.dequeue());
  }

  return {
    eliminated,
    winner: queue.toString(),
  };
}