Neste post estarei fazendo uma implementação simples da estrutura de dados conhecida como Pilha utilizando o JavaScript. Apesar da lista JavaScript ser totalmente capaz de simular a pilha, fila, lista, etc… a ideia é focar na teoria e criar do zero uma pilha de nós (nodes) como se a funcionalidade não estivesse disponível.
Como funciona a pilha?
A pilha é um tipo de estrutura de dados que funciona no formato que o último item que foi inserido será o primeiro a ser removido da estrutura (Lifo – Last in, First out). Então quando você adicionar 3 números e quiser remove-los, eles serão removidos na ordem inversa que foram adicionados (terceiro – segundo – primeiro).
Considerações
Algumas considerações na nossa implementação para que não ocorra confusão:
- A classe do JavaScript ainda não permite declarar propriedades como privadas, por isso usarei _ na frente do nome das propriedades ao qual NÂO deveríamos estar acessando externamente.
- Esta é uma implementação para uso acadêmico. Por favor utilize a lista do JavaScript para trabalhar com a pilha em produção (new Array ou []).
- Alguns trechos de código poderiam ser resumidos em uma única linha, mas foram mantidos quebrados para auxiliar aqueles que estão aprendendo.
Implementação:
Classe e Construtor
Beleza, então vamos começar. A primeira coisa que precisamos é criar a classe e o construtor dela conforme o código abaixo. Para o nome da classe usaremos o termo em português, mas para o resto iremos utilizar os termos em Inglês pois parece ser o padrão mais utilizado por livros e cursos.
class Pilha { constructor() { this._top = null; this._count = 0; } //Continuação do código
Como você pode ver, teremos apenas duas variáveis de controle, _top que fará referencia para o topo da pilha e _count que controlará quantos itens a pilha possuí.
GetCount()
O método GetCount é o mais simples de todos. Ele apenas irá retornar a quantidade de itens na pilha.
GetCount = function () { return this._count; };
Peek()
Exibe o item no topo da pilha ou null caso ela esteja vazia.
Peek = function () { if (this._top) { return this._top.data; } return null; };
Push(item)
O método Push (empurrar) é a forma como adicionaremos itens a pilha. Pelo fato de ser uma linguagem não tipada, poderemos adicionar qualquer valor a pilha que ela o aceitará.
Push = function (data) { let node = { data: data, next: null }; node.next = this._top; this._top = node; this._count++; };
Como você pode ver, o método cria um objeto chamado node (nó) que é um objeto JS e terá 2 propriedades, o data (dados em inglês) para o valor e next (próximo) para referência o item anterior. Após isso definimos este novo valor como sendo o do topo e referenciamos o antigo topo no next.
Isto é feito desta forma pois para a pilha, é importante termos um controle de quem está no topo. Os outros itens serão manipulados apenas quando chegar a vez deles.
Pop()
O Método Pop (tirar) funciona da forma oposta ao Push, ele remove o item que está no topo da fila.
Pop = function () { if (this._top) { let out = this._top; this._top = this._top.next; if (this._count > 0) { this._count--; } return out.data; } return null; };
Como você pode ver o código acima faz o seguinte: Confere se existe algum item no topo da fila para poder remove-lo, transforma o next em topo, reduz a contagem em 1 e retorna o item removido ou null caso esteja vazio.
DisplayAll()
Este método exibe todos os itens da pilha, do topo ao fundo, no formato de um vetor JavaScript. Caso a pilha esteja vazia, retorna null
DisplayAll = function () { if (this._top) { let arr = new Array(); let current = this._top; for (let i = 0; i < this._count; i++) { arr[i] = current.data; current = current.next; } return arr; } return null; };
Apesar deste código ter um pouco mais de lógica que os métodos anteriores, ele ainda é fácil de entender. Ele testa se o _top não está vazio e se verdadeiro, percorrerá a pilha copiando o valor armazenado dentro de cada nó para dentro do vetor.
Executando o código
Após criar a classe, um teste simples ajudará a verificar que todos os métodos estão fazendo o que deveriam
let pilha = new Pilha(); console.log(`Contagem: ${pilha.GetCount()}`); pilha.Push(4); console.log(`Peek: ${pilha.Peek()}`); console.log(`Contagem: ${pilha.GetCount()}`); pilha.Push(22); console.log(`Contagem: ${pilha.GetCount()}`); console.log(`Pop: ${pilha.Pop()}`); console.log(`Pop: ${pilha.Pop()}`); console.log(`Pop: ${pilha.Pop()}`); console.log(`Contagem: ${pilha.GetCount()}`); pilha.Push(1); pilha.Push(-2); pilha.Push(100); pilha.Push(350); console.log(`Todos: ${pilha.DisplayAll()}`);