Fila (queue): o que é, como funciona e exemplos práticos

Texto de: Marlliton Souza

Filas, assim como as pilhas, nos permitem inserir e remover elementos, mas seguindo o princípio FIFO (First In, Frist Out), ao invés do princípio LIFO (Last In, First Out). Isso quer dizer que o primeiro elemento a entrar na fila, será o primeiro a ser removido também.

Se pensarmos um pouco, lidamos com filas no nosso cotidiano com muita frequência. Um exemplo comum é a fila do caixa de supermercado. Quando você chega ao fim da fila, tem que esperar todos os que estão a sua frente serem atendidos, para só então, você fazer o pagamento e sair da fila.

Trazendo isso para o lado dos computadores, o princípio é o mesmo, e o último elemento a ser adicionado na fila, será o último a ser removido. A figura acima ilustra o processo de enfileirar (enqueue) onde um elemento é adicionado ao fim da fila, e o processo de desenfileirar (dequeue), que por sua vez remove sempre o primeiro elemento da fila.

Criando a classe Queue (Fila)

Agora que já entendemos um pouco da teoria por trás das filas, vamos implementar uma fila usando a linguagem JavaScript. Para isso, primeiro precisamos criar uma estrutura de dados primitiva para armazenar os elementos da fila, como fizemos no exemplo de pilhas (stacks).

Diferentemente do que foi feito no artigo sobre pilhas, aqui usaremos um objeto como estrutura de dados primitiva para armazenar os elementos da fila. Caso você tenha interesse, o código fonte desse artigo pode ser acessado clicando aqui!

Os métodos que a classe Queue deverá conter são:

• enqueue: adiciona um elemento ao final da fila;
• dequeue: remove o elemento que estiver no início da fila e devolverá o mesmo;
• peek: retorna o primeiro elemento da fila, em outras palavras, o elemento presente na primeira posição;
• isEmpty: verifica se a fila está vazia.
• size: devolve o tamanho da fila.

Queue

export class Queue {
    readonly _items: object
    private _count: number
    private _firstElement: number
    constructor(items: object = {}) {
      this._items = items
      this._count = 0
      this._firstElement = 0
    }
  
    enqueue(item: any) {
      this._items[this._count] = item
      this._count++
    }
  
    dequeue() {
      if(this.isEmpty()) return
  
      const element = this._items[this._firstElement]
      delete this._items[this._firstElement]
      this._firstElement++
      return element
    }
  
    peek() {
      if(this.isEmpty()) return
      return this._items[this._firstElement]
    }
  
    isEmpty() {
      return this._count - this._firstElement === 0
    }
  
    size() {
      return this._count - this._firstElement
    }
  } 

Podemos perceber que implementar uma fila não é tão difícil, na verdade, é bem simples depois que você entende o conceito básico do funcionamento de uma fila.

Usando a classe Queue (Fila)

Primeiramente, precisamos instanciar a classe Queue, e logo em seguida, podemos começar a chamar os métodos que definimos anteriormente.

Verificando se a fila está vazia:

Vamos adicionando 4 elementos a fila e visualizá-los:

Como pode ser visto, os itens foram adicionados na ordem correta (sempre ao final da fila). Agora verificaremos se o método dequeue está funcionando corretamente.

Removendo itens da fila:

Como esperado, os dois primeiros elementos da fila foram removidos, restando apenas os dois últimos.

Espiando o início da fila e verificando o tamanho da fila:

Temos o e-mail bia@zmail.com como sendo o primeiro elemento da fila, já que iniciamos com 4 elementos e removemos dois durante nossos testes.

Para facilitar ainda mais o entendimento, o diagrama a seguir representa as operações de enfileiramento e desenfileiramento feitas na fila:

Conclusão

Neste artigo, entendemos em detalhes como a estrutura de dados fila (queue) funciona, e se você chegou até aqui, tenho certeza que será capaz de implementar sua versão. Bons estudos! 👾

Saiba mais

FIFO - wikipedia