Filas: entendendo e implementando essa estrutura de dados
Tags: braziliandevs, javascript, datastructures
Published: 2023-08-08 12:05:12

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](https://novatec.com.br/livros/estruturas-de-dados-algoritmos-em-javascript-2ed/), 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 **F**irst **I**n, **F**irst **O**ut).


![Exemplo de fila, com carros um na frente do outro, e do lado direito a indicação do método dequeue, que remove o carro que está na frente da fila, e do lado direito uma explicação do método enqueue, que adiciona um carro ao final da fila](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nqzt80e3kqk981sufivy.png)

É uma lógica inversa das [pilhas](https://dev.to/brunopinho/pilhas-entendendo-como-essa-estrutura-de-dados-funciona-3al5), 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.

```javascript
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, mostrando como a callback queue é uma fila que envia de volta a call stack as callbacks de nosso código.](https://res.cloudinary.com/practicaldev/image/fetch/s--OIG-_8dF--/c_limit,f_auto,fl_progressive,q_66,w_800/https://devtolydiahallie.s3-us-west-1.amazonaws.com/gif4.gif)

Exemplo ilustrado feito pela [Lydia Hallie](https://www.lydiahallie.io/) em seu texto explicando [o que é o event loop](https://dev.to/lydiahallie/javascript-visualized-event-loop-3dif).

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](https://dev.to/brunopinho/pilhas-entendendo-como-essa-estrutura-de-dados-funciona-3al5):

{% embed https://www.youtube.com/watch?v=8aGhZQkoFbQ %} 

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**](https://novatec.com.br/livros/estruturas-de-dados-algoritmos-em-javascript-2ed/). Este artigo foi inspirado nas notas que fiz enquanto o lia.