Tag: Pilha

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