Deques: entendendo e implementando essa estrutura de dados

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.