Filas: entendendo e implementando essa estrutura de dados

Este texto vai falar uma estrutura de dados clássica: a fila. Ela é simples de entender e é extremamente útil no campo da computação.

Eu compilei as notas que fiz lendo o ótimo livro Estrutura de Dados e Algoritmos com JavaScript, da Loiane Groner, para escrever este artigo. Se você quer saber mais sobre essa e outras estruturas, recomendo demais a leitura.

Filas e o conceito do primeiro que entra, primeiro que sai

O principal objetivo da estrutura de fila é replicar o comportamento de uma fila do mundo real, onde a primeira pessoa a chegar à fila é a primeira que será chamada. Este conceito é chamado de FIFO (o acrônimo em inglês para First In, First Out).

É uma lógica inversa das pilhas, que é uma outra estrutura de dados que já escrevi sobre. Se nas pilhas o último item (o táxi, em nosso exemplo acima) é o primeiro que será removido, nas filas esse último item deverá esperar todos que estão antes dele ser retirados para chegar sua vez.

Métodos comuns de uma fila

Os métodos comuns de uma fila são o enqueue, que adiciona um item na última posição da fila, dequeue, que remove o primeiro item, e peek, que retorna o primeiro item de nossa fila sem removê-lo - aliás, como curiosidade e para ajudar a lembrar, já que o método faz jus ao nome, peek pode ser traduzido como olhadinha para português.

Criando uma classe de fila

Para fins didáticos, a Loaine cria uma classe de fila com os métodos que falei acima e alguns outros, como o isEmpty para checar se a fila está vazia, size para que seja retornado seu tamanho, clear para limpar a nossa estrutura e toString para retornar em string o conteúdo da fila. É este exemplo que vou replicar aqui.

export default class Queue {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }

  enqueue(element) {
    this.items[this.count] = element;
    this.count += 1;
  }

  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount += 1;
    return result;
  }

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

    return this.items[this.lowestCount];
  }

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

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

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

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    let stringQueue = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i += 1) {
      const currItem = this.items[i];

      stringQueue = `${stringQueue}, ${currItem}`;
    }
    return stringQueue;
  }
}

Exemplos de usos de filas

Filas são usadas em vários contextos e em diferentes aplicações.

A própria linguagem que ilustra o exemplo acima, o JavaScript, faz uso de uma fila para lidar com a lista de callbacks que precisam voltar a call stack durante o funcionamento do event loop.

Exemplo ilustrado feito pela Lydia Hallie em seu texto explicando o que é o event loop.

E se o que falei acima pareceu muito confuso para você, trarei de volta a palestra do Philip Roberts na JS Conf explicando o que diabos é o event loop, que já havia compartilhado no texto sobre pilhas:

Outro exemplo de fila é o controle dos arquivos que deverão ser impressos por uma impressora, que no geral são gerenciados por meio de uma fila, onde o arquivo que foi colocada primeiro será o primeiro a ser impresso.

---

Espero que este artigo tenha ajudado a entender melhor o que é a estrutura de filas e quais são suas vantagens.

Lembrando que se você quer se aprofundar mais nessa e em outras estrutura de dados, recomendo de novo o livro da Loiane, Estruturas de dados e algoritmos com JavaScript. Este artigo foi inspirado nas notas que fiz enquanto o lia.