Estrutura de Dados: Filas

Eae gente bonita, beleza?

Hoje volto a falar sobre um tema muito importante dentro da estrutura de dados, dessa vez abordando o tema Filas. É um tema muito importante e que está presente no dia a dia do desenvolvedor e muitas vezes nem percebemos.

O que é uma fila?

Uma fila é uma coleção de itens ordenada baseada no conceito de FIFO (First In First Out). Basicamente signfica que o primeiro a entrar na fila também é o primeiro a sair. Assim como acontece na fila do cinema, por exemplo. E os novos itens sempre são adicionados no final da fila.

Onde isso é aplicado?

A fila é uma estrutura de dados bem útil e usada de várias formas durante o desenvolvimento de software. Por exemplo:

• Fila de e-mails: é muito comum sua aplicação gerar e-mails para serem enviados usando uma cloud. Porém esses e-mails não são enviados diretamente. Eles entram em uma fila para serem processados e enviados ao seu destino.

• Processamento de pagamentos: Imagine se você compra algo na amazon e por algum motivo o seu pagamento não é processado? Para conseguir lidar com a quantidade de pagamentos e ter a certeza de que ele será processado é possível usar uma fila para controlar isso.

Na prática

Aqui vai um exemplo de implementação de uma fila e algumas formas de uso ⤵

class Queue {

    // Quantidade de items na fila.
    #count = 0;

    // Serve para controlar quando é o primeiro item da fila. Não necessáriamente pode ser 0.
    #lowestCount = 0;

    // Objeto com todos os items armazenados.
    #items = {};

    // Adiciona os items na fila.
    enqueue(element) {
        this.#items[this.#count] = element;
        this.#count++;
    }

    // Verifica se a fila está vazia.
    isEmpty() {
        return (this.#count - this.#lowestCount) === 0;
    }

    // Remove o primeiro item da fila.
    dequeue() {
        if (this.isEmpty()) {
            return undefined;
        }

        const result = this.#items[this.#lowestCount];
        delete this.#items[this.#lowestCount];
        this.#lowestCount++;
        return result;
    }

    // Retorna o primeiro item da fila.
    peek() {
        if(this.isEmpty()) {
            return ''
        }

        return this.#items[this.#lowestCount];
    }

    // Retorna o tamanho da fila.
    size() {
        return this.#count - this.#lowestCount;
    }

    // Limpa a fila.
    clear() {
        this.#items = {};
        this.#count = 0;
        this.#lowestCount = 0;
    }

    // Retorna todos os items da fila em uma string.
    toString() {
        if (this.isEmpty()) {
            return '';
        }

        let objString= `${this.#items[this.#lowestCount]}`;

        for (let index = this.#lowestCount + 1; index < this.#count; index++) {
            objString = `${objString}, ${this.#items[index]}`;
        }
        return objString;
    }

}

Aqui é um exemplo de uso bem simples da nossa fila. Primeiro nós estanciamos a classe e em seguida começar a adicionar itens e manipular a fila da forma que precisarmos.

const queue = new Queue();

queue.enqueue("Cristian"); // Cristian
queue.enqueue("Paulo"); // Cristian, Paulo
console.log(queue.size()) // 2
queue.enqueue("Mateus"); // Cristian, Paulo, Mateus
queue.dequeue();
console.log(queue.toString()) // Paulo, Mateus
console.log(queue.peek()); // Paulo
queue.clear();
console.log(queue.isEmpty()); // True

Serviços

Vimos que implementar e usar uma fila parece uma tarefa simples, porém usar uma fila em larga escala é uma tarefa bem complexa. Então é comum usar serviços para realizar essa tarefa, existem diversos serviços e formas de fazer como por exemplo o SQS da AWS.

Outros tipos de fila

Também existe um outro tipo de fila chamada de Deque ou fila de duas pontas. Ela permite que você faça operações de remoção e inserção nas duas pontas da fila.

Referências

Estruturas de Dados e Algoritmos com JavaScript by Loiane Groner

Se chegou até aqui, me segue la nas redes vizinhas.