Node.js: dominando filas, pilhas e estruturas de dados

Implementando filas com classes e entendo FIFO - Introdução

Apresentando o curso de algoritmos

Boas-vindas a este curso de algoritmos.

Meu nome é Eric.

Audiodescrição: Eric é um homem branco, careca, que usa óculos. Ele veste uma camiseta preta e está em um estúdio amplo.

Convidando para explorar algoritmos

Estamos aqui para convidá-los a participar deste curso de algoritmos, que é extremamente interessante quando pensamos em algoritmos de forma mais aplicada.

Nós já utilizamos algoritmos extensivamente em nosso código, mas, por vezes, não paramos para refletir sobre eles, não conhecemos internamente as decisões de design de algoritmos que foram tomadas para cada uma das estruturas que usamos. Estruturas como fila, pilha, lista ligada, conjuntos, mapas e aquele dicionário que normalmente utilizamos na linguagem. Como essas estruturas são implementadas? Como as pessoas desenvolveram essas ideias?

A proposta deste vídeo, desta série de vídeos, deste conteúdo tão interessante, é que possamos, juntos, explorar esse caminho. Esperamos que apreciem e contamos com a presença de todos para iniciarmos essa jornada, que acreditamos será fantástica.

Implementando filas com classes e entendo FIFO - O que são filas?

Introduzindo o conceito de fila

Olá, pessoal. Vamos começar discutindo a primeira estrutura de dados: a fila. Entre as estruturas de dados, a fila é geralmente a primeira que aprendemos, pois é baseada em um conceito simples e presente no nosso dia a dia.

Imaginemos uma manhã típica em que estamos chegando ao trabalho. Antes de chegar, passamos na padaria para pegar um café ou algo para comer. No entanto, há uma quantidade de pessoas à nossa frente, que serão atendidas antes de nós, pois chegaram primeiro. A ideia é que, pelo fato de essas pessoas terem chegado antes, elas têm prioridade no atendimento. Esse é o conceito de fila, que é comum em diversas situações do nosso cotidiano.

Exemplificando o uso de filas no cotidiano

Por exemplo, ao comprar ingressos online para grandes festivais, há uma alta demanda, e os pedidos são atendidos em ordem de chegada. Existe a fila virtual, onde as pessoas que conseguem entrar antes têm acesso aos ingressos primeiro. Esse conceito também se aplica ao atendimento de requisições em software. À medida que as requisições chegam, elas são atendidas conforme a disponibilidade de recursos computacionais. Se houver mais requisições do que recursos, elas entram em uma fila, seguindo o padrão de que quem chega primeiro é atendido primeiro.

Discutindo a importância das filas em algoritmos

Por que precisamos pensar em filas ao desenvolver algoritmos? O primeiro desafio é garantir um atendimento organizado. A ideia de um atendimento organizado é crucial, pois, sem ele, não conseguimos assegurar uma regra de atendimento por ordem de chegada. Por exemplo, ao registrar transações bancárias, é necessário que elas sejam processadas na ordem correta. Se fizermos uma transferência antes de um depósito, sem o valor disponível na conta, a transferência não será possível. No entanto, se processarmos o depósito primeiro e depois a transferência, garantimos que o processamento ocorra conforme esperado.

Além disso, enfrentamos a questão do sobrecarregamento. Se há poucos recursos e muitas pessoas para atender, é essencial ter uma estrutura de fila para organizar o atendimento de forma eficiente.

Relacionando filas a restrições de recursos

Imagine que vamos entrar em um prédio onde ocorrerá um evento. Nesse prédio, há 30 pessoas para chegar e apenas 3 pessoas para atender. Temos uma restrição de recursos para processamento, com uma quantidade maior de chamadas, e essas chamadas precisam ser atendidas na ordem em que chegam. Isso é importante para que não haja uma estrutura que permita que quem chegou antes receba um atendimento diferente ou que alguém no meio da fila seja escolhido para ser atendido fora de ordem.

Explorando a previsibilidade e o conceito FIFO

Quando pensamos em algoritmos, é fundamental lembrar que eles são processos. O ponto interessante ao considerar uma fila é justamente essa ideia de processo. Ao criar ou entender um algoritmo, devemos sempre pensar no processo subjacente e no problema que ele resolve. Aqui, estamos usando um exemplo cotidiano para tratar de algo técnico. A ideia da fila é essa: tiramos a ideia da fila do mundo real e a aplicamos para entender tecnicamente como resolver um problema.

O ponto central ao falarmos de fila é a previsibilidade. Sabemos que o que chegou primeiro será atendido primeiro. Essa é a regra da fila que conhecemos normalmente. Não estamos discutindo como furar a fila ou como estabelecer prioridades; estamos tratando de uma fila comum. Para entender bem o conceito, vamos implementar usando as ferramentas do Node.

Concluindo com a simplicidade das filas

Um conceito importante ao trabalhar com filas é o FIFO, que vem do inglês "First In First Out". Quando trabalhamos com filas, frequentemente ouvimos falar de filas FIFO ou LIFO. Quando falarmos sobre pilhas, abordaremos o que chamam de fila LIFO. Mas aqui estamos lidando com uma fila FIFO, ou seja, "Primeira Entrada, Primeira Saída". Em tecnologia, ouvimos muito sobre filas de primeira entrada e primeira saída, ou filas FIFO. Os conceitos são frequentemente os mesmos quando falamos de filas de atendimento.

É importante observar que a ideia da fila é uma regra de atendimento simples, não complexa. Portanto, a implementação também deve ser simples. Veremos que, à medida que os algoritmos são apresentados, eles são construídos com base na ideia de outros. Para avançarmos, pegaremos um conceito inicial, como o de fila, para fazer outras implementações. Assim, é crucial entender bem como a fila funciona, pois ela é a base. Vamos explorar como a fila funciona, ver suas implementações e sempre tentar relacionar isso à resolução de problemas.

Até a próxima!

Implementando filas com classes e entendo FIFO - Criando o objeto de fila

Iniciando a implementação da fila

Já discutimos um pouco sobre a teoria das filas, então agora vamos partir para a implementação. Vamos abrir o Visual Studio Code. Já criamos uma pasta dentro da nossa estrutura de projeto chamada "aula1" e, dentro dela, vamos criar um arquivo chamado fila.js, que será o arquivo em que trabalharemos agora.

Para todas as estruturas que vamos criar, utilizaremos classes. Isso facilita o encapsulamento de todas as ideias em uma única estrutura. Vamos começar criando uma classe chamada Fila.

class Fila {
}

Definindo o construtor e o método enfileirar

Inicialmente, vamos definir o constructor, que não receberá nenhum parâmetro. No constructor, definiremos uma variável de array, um campo de array. Utilizaremos o array do JavaScript como base para todas as estruturas que desenvolveremos, pois é uma estrutura básica que aprendemos logo no início e que nos ajudará a entender as técnicas.

class Fila {
    constructor(){
        this.elementos = [];
    }
}

Vamos começar criando essa estrutura com this.elementos = [], definindo assim uma lista vazia. Com isso, já temos o básico da fila, algo que consegue receber elementos. O primeiro método que implementaremos será para adicionar elementos à fila, sempre no final. Se adicionarmos três itens, o terceiro item sempre será o último. Essa será a ideia ao longo de toda a implementação da fila.

Vamos criar um método chamado enfileirar, que receberá um parâmetro elemento. A ideia é que o elemento seja adicionado na posição correspondente ao tamanho atual do array, já que o array começa a contar a partir de 0. Portanto, se o array tem dois itens, o novo elemento será colocado na posição 2.

enfileirar(elemento){
    this.elementos[this.elementos.length] = elemento;
}

Testando a fila e adicionando elementos

Agora, fora da classe, vamos realizar um teste para verificar como utilizar essa fila. Vamos criar uma constante minhaFila e instanciar a fila.

const minhaFila = new Fila();

Em seguida, utilizaremos minhaFila.enfileirar para adicionar um número.

minhaFila.enfileirar(1);

Para visualizar o array interno que estamos utilizando, faremos um console.log(minhaFila.elementos). Isso nos permitirá entender como a estrutura está sendo construída.

console.log(minhaFila.elementos);

Ao rodar o código, veremos que o array contém um único elemento, que é o número 1. Vamos tentar enfileirar mais elementos, como 2 e 3.

minhaFila.enfileirar(2);
minhaFila.enfileirar(3);

Quando olharmos o resultado, veremos os números 1, 2 e 3, indicando que a fila está funcionando corretamente.

Implementando o método retirar

Agora precisamos começar a consumir esses itens. Sempre consumiremos o primeiro item da fila. Para isso, criaremos um método retirar dentro da classe Fila.

retirar(){
    if (this.elementos.length == 0){
        return null;
    }
    const elementoARetornar = this.elementos[0];
    this.elementos = this.elementos.slice(1, this.elementos.length);
    return elementoARetornar;
}

O método retirar não precisará de parâmetros, pois apenas solicitará a remoção de um item. Se a fila estiver vazia, retornaremos null. Caso contrário, armazenaremos o primeiro elemento em uma constante elementoARetornar e utilizaremos o método slice para removê-lo do array.

Com isso, implementamos a funcionalidade básica de uma fila, permitindo adicionar e remover elementos conforme necessário.

Explicando o uso do método slice

O que o slice faz?

Precisamos passar o início e o final. O início será 1 e o final será o tamanho da nossa fila, this.elementos.length. O que fizemos aqui? Vamos dar uma olhada. No método retirar, na linha 10, estamos testando se o nosso array de elementos está vazio. Se estiver vazio, retornamos null. Caso contrário, pegamos um elemento para retornar. Na linha 14, definimos const elementoRetornar = this.elementos[0]. Na linha 15, ajustamos a nossa nova lista, removendo o primeiro item. No final, retornamos o elemento a ser retornado. Essa é a implementação do método retirar.

Vamos fazer algo interessante: retirar o primeiro item. Saímos da classe que estávamos desenvolvendo e, com as entradas feitas, na linha 24, criamos const itemRetirado = minhaFila.retirar(). O que vamos salvar aqui? Ao enfileirar três elementos, retiramos um.

const itemRetirado = minhaFila.retirar();
console.log("item retirado: ", itemRetirado);

No terminal, a saída da execução do script mostra a listagem 1, 2 e 3. Vamos verificar se o 1, que é o primeiro da lista, foi retirado. Usamos console.log(itemRetirado) para mostrar o item retirado na tela de saída.

Realizando testes adicionais

Ao clicar em "run code", verificamos que o item retirado foi 1, e os elementos restantes são 2 e 3. Na execução, enfileiramos três elementos nas linhas 22, 23 e 24, e na linha 25 retiramos o 1. O item retirado apareceu corretamente. Podemos fazer outro teste: enfileirar mais um número.

minhaFila.enfileirar(4);

Ao executar novamente, vemos que o 4 foi adicionado, resultando em um array com 2, 3 e 4.

Se fizermos novamente const itemRetiradoNovo = minhaFila.retirar(), imprimimos o item retirado novo com console.log("Item retirado novo:", itemRetiradoNovo), e em seguida imprimimos a lista final com console.log(minhaFila.elementos).

const itemRetiradoNovo = minhaFila.retirar();
console.log("item retirado novo: ", itemRetiradoNovo);
console.log(minhaFila.elementos);

Ao executar novamente, vemos que criamos 1, 2, 3, retiramos 1, enfileiramos 4, resultando em 2, 3, 4. Retiramos mais um, o 2, e no final ficaram 3 e 4. Observamos que os primeiros a entrar foram os primeiros a sair.

Implementando métodos auxiliares

Precisamos implementar dois últimos itens. Primeiro, verificar se a fila está vazia, o que é importante para decidir se continuamos a trabalhar com ela. Criamos a função estaVazia(), que retorna true se this.elementos.length for igual a zero, e false caso contrário. Retornamos esse valor.

estaVazia(){
    const vazia = this.elementos.length == 0;
    return vazia;
}

O último item é verificar o tamanho da fila. Criamos a função tamanho(), que retorna this.elementos.length.

tamanho(){
    return this.elementos.length;
}

Nos testes de codificação, na linha 40, usamos console.log("A fila está vazia:", minhaFila.estaVazia()) e console.log("Tamanho atual da fila:", minhaFila.tamanho()).

console.log("a fila está vazia?", minhaFila.estaVazia());
console.log("tamanho atual da fila:", minhaFila.tamanho());

Ao executar novamente, verificamos que a fila não está vazia e o tamanho atual é 2, conforme mostrado na saída.

Implementamos a fila de forma padrão, utilizando o que o JavaScript permite, que é o array, e implementando as ações. Quando usamos a fila, apesar de olharmos dentro dela, não utilizamos o elemento diretamente, apenas os métodos enfileirar e retirar. Até a próxima!

Sobre o curso Node.js: dominando filas, pilhas e estruturas de dados

O curso Node.js: dominando filas, pilhas e estruturas de dados possui 213 minutos de vídeos, em um total de 48 atividades. Gostou? Conheça nossos outros cursos de Node.JS em Programação, ou leia nossos artigos de Programação.

Matricule-se e comece a estudar com a gente hoje! Conheça outros tópicos abordados durante o curso:

• Implementando filas com classes e entendo FIFO
• Aplicando pilha para gerenciar listas
• Construindo listas ligadas com a estrutura de nodes
• Otimizando o acesso a dados com dicionários e o objeto Map
• Eliminando duplicidades com set e otimizando listas