Pilhas: entendendo como essa estrutura de dados funciona

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.