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()}`);
