Estrutura de Dados - Implementando uma Pilha

Continuando a série de artigos sobre estruturas de dados, hoje irei descrever como funciona a pilha e também detalhar uma forma de implementá-la utilizando JavaScript através do Node.js.

PILHA

É uma estrutura de dados onde o último elemento que entrou deve ser o primeiro elemento a sair, isso é Last In, First Out ou simplesmente LIFO.

Abaixo, podemos verificar uma ilustração que exemplifica o funcionamento de uma pilha:

Pilha - Empilhamento

Pilha - Desempilhamento

Como pode ser visto, a cada inclusão de um livro na pilha, ele se torna o topo e a cada retirada de livro, sendo sempre o último elemento da pilha, o anterior a ele se torna o topo da estrutura até que a pilha fique vazia. Nesse caso, pegamos uma pilha que estava vazia e empilhamos todos os elementos. Logo em seguida, desempilhamos todos os elementos até que a pilha ficasse novamente vazia.

Agora que o conceito está definido, irei partir para implementação da pilha utilizando JavaSript. O código a seguir será uma pilha de livros, contudo, esse pode ser adaptado para outro tipo de modelo, pois a lógica será a mesma.

IMPLEMENTAÇÃO

Primeiramente irei implementar a classe Livro, que irá ser a representação lógica de cada livro que será colocado na pilha. Segue código fonte da classe:

class Livro {
    constructor(nome, autor, paginas) {
        this.nome = nome;
        this.autor = autor;
        this.paginas = paginas;
    }

    imprimir() {
        console.log(this);
    }

}

module.exports = Livro;

O próximo passo será a implementação do nó, que irá representar cada item da pilha. O nó irá conter a referência de um livro e também a referência para o próximo elemento da pilha.

Segue a implementação:

class No {
    constructor(livro, no = null) {
        this.livro = livro;
        this.no = no;
    }
}

module.exports = No;

Em seguida irei implementar a classe que irá representar a estrutura de dados pilha e suas operações, sendo elas: empilhar (push), desempilhar (pop), tamanho da pilha e imprimir elementos da pilha.

Abaixo, o código fonte base da pilha, cada operação será implementada nos próximos tópicos do artigo:

const No = require("./No");

class Pilha {
    constructor() {
        this.topo = null;
        this.quantidadeNos = 0;
    }

    /**
     * Empilha um livro na pilha
     */
    push(livro) {}

    /**
     * Desempilha um livro na pilha
     */
    pop() {}

    /**
     * Retorna a quantidade de livros na pilha
     */
    tamanhoDaPilha() {}

    /**
     * Imprime os livros na pilha
     */
    imprimirPilha() {}

}

module.exports = Pilha;

EMPILHAR (PUSH)

Para realizar o empilhamento, irei fazer com que o novo nó do livro que está sendo incluído aponte para o nó que é o atual topo da pilha e em seguida, esse novo nó irá se tornar o topo da pilha. Um pouco confuso, não é! Mas com o código fonte ficará mais simples de entender:

    /**
     * Empilha um livro na pilha
     */
    push(livro) {
        const novoNo = new No(livro, this.topo);
        this.topo = novoNo;
        this.quantidadeNos++;
    }

DESEMPILHAR (POP)

A lógica por trás do desempilhar é pegar o nó que é o topo da pilha e fazer com que o nó que ele aponta se torne o novo topo e em seguida o método implementado retorne o livro do antigo topo. Essa operação faz com que o topo alterne entre o atual para o próximo nó da pilha. Segue código da implementação:

    /**
     * Desempilha um livro na pilha
     */
    pop() {
        const topo = this.topo;
        if (topo != null) {
            this.topo = topo.no;
            this.quantidadeNos--;
            return topo.livro;
        }
        return null;
    }

TAMANHO DA PILHA

Para saber o tamanho da pilha, o método abaixo irá retornar o atributo quantidadeNos que foi incrementado cada vez em que houve um empilhamento e decrementado cada vez em que houve um desempilhamento. Veja a implementação abaixo:

    /**
     * Retorna a quantidade de livros na pilha
     */
    tamanhoDaPilha() {
        return this.quantidadeNos;
    }

IMPRIMIR ELEMENTOS DA PILHA

O método imprimir basicamente irá realizar a iteração do nó do topo da lista até o nó que aponte para nulo (null).

Segue exemplo da implementação do método:

    /**
     * Imprime os livros na pilha
     */
    imprimirPilha() {
        let atual = this.topo;
        while (atual != null) {
            atual.livro.imprimir();
            atual = atual.no;
        }
    }

CONCLUSÃO

A estrutura de dados pilha é utilizada sempre que necessitamos do empilhamento e desempilhamento de elementos. Atualmente, as linguagens de programação já implementam essa estrutura de dados nativamente, não sendo necessária a implementação manualmente como foi feito, contudo é importante saber o conceito por traz da implementação para que a utilizemos de forma correta e assertiva para solucionarmos problemas nos algoritmos que estamos desenvolvendo.

Você pode baixar os fontes dessa implementação através do link abaixo:

/nandobhx/node-pilha

Espero que esse artigo tenha agregado conhecimentos para você e caso queira deixar uma sugestão ou comentário envie uma mensagem no menu "Contato" desse blog ou através do LinkedIn.

Grande abraço!!!