Forem: Bruno Pinho

Deques: entendendo e implementando essa estrutura de dados

Bruno Pinho — Mon, 16 Oct 2023 23:12:07 +0000

Os deques são uma das estrutura de dados mais interessantes que estudei até aqui. Eles são uma variação das filas que, como veremos, pode ser muito útil em diferentes tipos de implementações.

Este texto foi feito com base nas notas que fiz lendo o ótimo livro Estrutura de Dados e Algoritmos com JavaScript, da Loiane Groner. Se você quer aprender deques de forma mais profunda e também conhecer diversas outras estruturas, recomendo bastante a leitura.

Deques: as filas de duas pontas

De maneira sucinta, os deques são filas de duas pontas. Mas para ficar claro o que isso significa, é preciso rever de forma rápida o que são as filas, que também já escrevi sobre.

As filas são uma estrutura que permitem adicionar elementos e manipulá-los através do conceito de FIFO - um acrônimo em inglês para First In, First Out, ou primeiro que entra, primero que sai.

Isso significa que, usando os métodos enqueue e dequeue para fazer essa adição e remoção dos items, os mais recentes vão para o final da fila, enquanto aqueles que estão na fila há mais tempo serão retirados antes.

A premissa das filas é como uma fila na vida real: aqueles que chegaram primeiro estão na frente e, portanto, saem primeiro.

O que diferencia os deques das filas é que eles subvertem essa lógica e permitem que itens sejam adicionados ou removidos da frente ou do final da fila, o que nos dá muito mais flexibilidade na manipulação de itens quando usamos essa estrutura.

Os deques, assim, se aproximam muito mais de como diferentes filas funcionam no mundo real. Nas palavras da Loiane:

Um exemplo de um deque na vida real é a fila típica em cinemas, lanchonetes e assim por diante. Por exemplo, uma pessoa que acabou de comprar um ingresso poderia retornar para a frente da fila somente para pedir uma informação rápida. Se a pessoa que estiver no final da fila estiver com pressa, ela poderia também sair da fila.

Isso nos abre um novo leque ao usarmos deques em nossas aplicações, como veremos mais a frente. Mas antes, vamos ver como implementar o deque e quais são seus métodos.

Deque: métodos a serem implementados

O deque é uma fila especial que acaba por parecer a junção das estruturas de fila e pilha, por isso os métodos dessas estruturas tem uma lógica semelhante.

Assim, ele tem métodos que nos permitem adicionar elementos nas duas pontas da fila, como o addFront, que adiciona um item na frente, e o addBack que adiciona na cauda, como é feito na fila. O mesmo funciona para a remoção, com os métodos removeFront e removeBack.

A olhadinha que podemos dar utilizando o método peek precisa funcionar para as duas pontas, então também criamos os métodos peekFront e peekBack. Além disso, também implementaremos os métodos que estão sendo comuns a todas as estruturas que tenho escrito, como o size, clear, isEmpty e toString.

Criando uma classe de deque

Este é um exemplo didático que a Loiane constrói no livro e trago aqui, para entendermos como uma estrutura deque funciona por baixo dos panos.

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

    addFront(item) {
        if (this.isEmpty()) {
            this.addBack(item);
        } else if (this.lowestCount > 0) {
            this.lowestCount--;
            this.items[this.lowestCount] = item;
        } else {
            for (let i = this.count; i > 0; i -= 1) {
                this.items[i] = this.items[i - 1];
            }
            this.count += 1;
            this.items[0] = item;
        }
    }

    addBack(item) {
        this.items[this.count] = item;
        this.count += 1;
    }

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

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

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

        this.count -= 1;
        const result = this.items[this.count];
        delete this.items[this.count];
        return result;
    }   

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

        return this.items[this.lowestCount];
    }

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

        return this.items[this.count - 1];
    }

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

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

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

    toString() {
        if (this.isEmpty()) {
            return '';
        }

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

        return objString;
    }
}

Exemplos de usos dos deques

Um exemplo de uso dessa estrutura de dados que vemos no nosso dia-a-dia é no histórico e gerenciamento de nossas ações dentro de algum aplicativo, como o VS Code, nos permitindo desfazer ou refazer alguma ação.

A mesma lógica é aplicada costuma ser aplicada no histórico do navegador, sendo usada o deque para gerenciar a adição e remoção das páginas visitadas, além de ir tirando registros mais antigos depois de algum tempo.

Além disso, ele é uma estrutura usada como pano de fundos de funções importantes de nossos sistemas operacionais, como o agendamento de tarefas.

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.

Filas: entendendo e implementando essa estrutura de dados

Bruno Pinho — Tue, 08 Aug 2023 12:05:12 +0000

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.

Pilhas: entendendo como essa estrutura de dados funciona

Bruno Pinho — Tue, 25 Jul 2023 00:14:40 +0000

As pilhas (ou stacks, para usar seu nome em inglês) são uma das estruturas de dados mais presentes em diferentes linguagens de programação. Elas permitem um controle maior na adição e remoção de itens à estrutura, o que as tornam uma opção muito interessante para algumas aplicações.

Explicarei neste texto um pouco dos conceitos por trás das pilhas, alguns casos em que elas são usadas e uma simulação de criação da estrutura utilizando JavaScript.

Este texto é um compilado das notas que eu fiz lendo o excelente Estruturas de dados e algoritmos com JavaScript, da Loiane Groner. Se quiser entender pilhas de uma forma mais aprofundada, assim como conhecer outras estruturas, recomendo bastante a leitura.

Spoiler: não são dessas pilhas que estamos falando!

Pilhas: como são e funcionam esta estrutura de dados

A ideia da estrutura das pilhas é simples e replica como funciona uma pilha de objetos no mundo real (como por exemplo, de livros): o último item colocado é o primeiro a sair.

As stacks funcionam como uma pilha de livros: um empilhado em cima do outro, da base ao topo.

No mundo da ciência da computação, este princípio tem até nome, sendo chamado de LIFO, ou Last In, First Out - o que traduzindo seria algo como último a entrar, primeiro a sair.

Assim, a ideia principal da pilha é ser uma estrutura onde a entrada e a saída de dados acontece de uma forma clara e definida. E ainda que, em nosso código, tentar pegar o item do meio de uma pilha não provoque tanto estrago quanto puxar um prato que está no meio de uma pilha de louças, esta é uma operação que você não vai conseguir fazer, já que só podemos acessar o item que está no topo.

Justamente porque a ideia desta estrutura é nos dar esse fluxo de trabalho por padrão, onde interagimos apenas com o topo da nossa pilha.

Métodos comuns em pilhas, como push e pop (que falaremos mais abaixo), sempre trabalham com os itens do topo. A proposta da stack não é que acessemos itens de outras posições.

Os vários casos de uso das pilhas

A estrutura de pilha é usada como um dos principais elementos para o controle de chamadas de funções nas mais diferentes linguagens. Em JavaScript, por exemplo, a Call Stack que controla o fluxo das chamadas de nosso código do momento em que ele inicia até seu retorno é, como o próprio nome diz, uma pilha.

Aliás, se você ainda não viu a explicação do Philip Roberts sobre o Event Loop do JavaScript e como ele trabalha junto com a Call Stack, olha, eu recomendo muito:

Aplicações como os navegadores se utilizam de pilhas para gerenciar elementos como o histórico de navegação, o que nos permite clicar no botão de voltar para a última página, por exemplo. O mesmo vale para as ações de voltar e avançar de um editor de texto.

Enfim, as stacks podem ser usadas em diferentes situações e são uma estrutura de dados extremamente importante. Mesmo que no dia-a-dia do desenvolvimento de nossas aplicações possamos não fazer tanto uso dela, por baixo dos panos da linguagem ou da ferramenta que estamos usando existe alguma implementação de pilha.

Criando uma pilha em JavaScript: um exemplo didático

Já que implementar e usar uma estrutura de dados é a melhor forma de decorar como ela funciona, vou trazer um dos exemplos que a Loiane constrói de stack em seu livro.

A ideia, mais do que ter uma classe para ser usada em ambiente de produção, é entender didaticamente como funcionam métodos chaves das pilhas, como o push, que serve para inserir um novo item na estrutura, e o pop, que remove o último item.

Além disso, também temos a implementação de outros métodos, como o size() para saber o tamanho da pilha, clear() para remover todos os itens, toString() para exibir a stack como uma grande string e peek() para dar uma espiadinha em qual é o item do topo.

class Stack {
    constructor() {
        this.items = {};
        this.count = 0;
    }

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

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

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

        const item = this.items[this.count - 1];
        delete this.items[this.count - 1];
        return item;
    }

    size() {
        return this.count;
    }

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

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

        return this.items[this.count - 1];
    }

    toString() {
        if (this.isEmpty) {
            return '';  
        }

        let stackString = `${this.items[0]}`;
        for (let i = 0; i < this.count; i += 1) {
            const currItem = this.items[this.count - 1];
            stackString = `${stackString}, ${currItem}`;
        }

        return stackString;
    }
}

const stack = new Stack();
console.log(stack.push(7));
console.log(stack.push(42));
console.log(stack.size()); // 2
console.log(stack.peek()); // 42
console.log(stack.pop()); // 42
console.log(stack.clear());

Lembrando que como em JavaScript não temos métodos privados, a ideia desse código não é ser uma implementação real de uma pilha, mas sim ilustrar como ela funciona por baixo dos panos.

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

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.

Dicas para deixar seu relatório de code coverage do Jest mais completo

Bruno Pinho — Thu, 02 Jun 2022 21:38:21 +0000

Fazendo o excelente curso de testes do Fabio Vedovelli, aprendi algumas dicas que achei muito úteis para deixar o relatório de code coverage do Jest mais completo. Compartilho aqui:

1. Mostrando diferentes arquivos do seu projeto no `code-coverage`

Por padrão, quando criamos um relatório de cobertura com o comando npm jest -- --coverage, apenas os arquivos que já testamos são analisados para gerar o resultado.

Porém, também é possível criar o relatório considerando pastas que ainda estão sem testes, o que pode ser útil para analisar quais linhas e arquivos precisam serem testadas.

Para fazer isso, é só ir ao seu arquivo jest.config.js e inserir a chave collectCoverageFrom com o valor sendo um array com os diretórios e arquivos que você quer que sejam analisados. Assim:

...
collectCoverageFrom: [
    '<rootDir>/components/**/*.js',
    '<rootDir>/pages/**/*.js',
    '<rootDir>/hooks/**/*.js',
    '<rootDir>/store/**/*.js',
  ],
...

Em uma tradução bem informal, é o mesmo de a gente dizer ao Jest "pega e faz o relatório a partir desses lugares aqui". O resultado é um coverage report com todos os arquivos .js das pastas components, pages, hooks e store.

2. Mostrando seu relatório no navegador

Outra dica legal que o Vedovelli compartilhou é sobre como exibir seu relatório de code coverage no navegador, deixando ele bem mais visual e informativo.

Como dá pra ver, ele mostra de forma mais intuitiva os arquivos analisados, o percentual deles que está coberto e quais linhas ainda faltam serem testadas. Dá até pra entrar no relatório de cada arquivo e ver em destaque quais são as partes do código que não estão cobertas.

Para exibir o report desta forma, basta abrir o arquivo index.html que foi criado pelo comandonpm -- --coverage e está dentro do diretório ./coverage/lcov-report/. Você pode fazer isto de duas formas:

Utilizando a extensão do VS Code `Live Server`

Um jeito rápido de visualizar o relatório é utilizando a extensão Live Server, que cria um server de desenvolvimento local e te permite abrir qualquer arquivo .html clicando no botão que a extensão adiciona ao VS Code.

Utilizando a dependência `http-server`

Caso não queira ou possa utilizar o Live Server, você pode instalar a dependência http-servere chegar ao mesmo resultado.

Para isso, instale o pacote globalmente:

npm install --global http-server

E execute o comando que inicia seu servidor passando o caminho para o diretório do arquivo index.html:

http-server ./coverage/lcov-report/

Concluindo

Essas são duas maneiras que aprendi de deixar nossos relatórios de code coveragemais completos que aprendi e gostaria de compartilhar aqui. Como já apontei, aprendi tudo no curso de testes em JavaScript do Fabio Vedovelli.

E você, tem outras dicas de como deixar esses relatórios melhores?