Estrutura de Dados com JavaScript: Pilha

Uma pilha é um tipo particular de dado em que as principais operações são a adição de um item (método push()) e remoção (método pop()). A pilha implementa um algoritmo LIFO (Last In First Out), que é uma estrutura onde o último elemento adicionado deve ser o primeiro a ser removido. Inicialmente, ela terá o seguinte código:

 

function pilha(){
    //cria uma variável que servirá 
     //para criação da pilha
    let topo = null; 
    let contador = 0;

    //Retorna o número de itens da fila
    this.GetContador = function(){
        return contador;
    }

    /* Métodos */
}

A nossa pilha terá quatro métodos adicionais: push(), pop(), peek() e displayAll(). Eles serão definidos dentro da função pilha() abaixo de this.GetContador. Vamos começar:

Push():

Descrição:

O método push() adiciona os dados especificados na pilha e o torna o nó do topo. Ele também aumenta a contagem de pilhas em 1.

this.Push = function (dado) {
    // Cria um nó que contém o dado e a referência para o próximo item
    let node = {
        dado: dado, 
        proximo: null
    };

    // Linka o nó atual para o topo da pilha
    // O próximo nó receberá o valor null como referência.
    node.proximo = topo;
        
    // Faz o nó atual ser o topo da pilha
    topo = node;

    // Incrementa o contador
    contador++;
}

Peek()

Descrição:

Exibe o item do topo da pilha. Retorna null se a pilha estiver vazia.

this.Peek = function(){
    // Se a lista estiver vazia, retornará null
    // senão, retornará o dado que estiver no nó topo.
    if (topo === null){
        return null;
    }else{
        return topo.dado;
    }
}

Pop()

Descrição:

Parece muito com o método peek(), com a diferença que o pop() remove o item que está no topo da pilha e diminui o contador em 1.

this.Pop = function(){
    // Se a lista estiver vazia, retornará null
    if(topo === null){
        return null;
    }else{
        // Atribui o topo a uma variável temporária
        let out = topo;

        // Atribui o topo para o próximo elemento da pilha
        topo = topo.proximo;

        // Se existir itens na pilha, decrementa o contador
        if (contador > 0){
            contador--;
        }

        // Retorna o valor que foi removido da pilha
        return out.dado;
    }
}

displayAll()

Descrição:

Exibe todos os dados da pilha como um vetor. Exibi-lo como um vetor foi minha escolha, pois não tinha certeza sobre como iria exibi-lo (por exemplo: console.log; document.write etc.).

this.DisplayAll = function(){
    // Se a lista estiver vazia, retornará null
    if (topo === null){
        return null;
    }else{
        // Instancia um vetor
        let arr = new Array();
        // Cria um nó que irá percorrer a pilha
        let noAtual = topo;

        // Percorre a pilha até alcançar o item mais abaixo
        for (let i = 0; i < contador; i++){
            // Atribui os dados ao vetor
            arr[i] = noAtual.dado;
            // Avança para a próxima posição da pilha
            noAtual = noAtual.proximo;
        }

        // Retorna o vetor
        return arr;
    }
}

Métodos utilizados na estrutura do tipo PILHA:

  • push(dado)
  • peek()
  • pop()
  • displayAll()

Gostou deste artigo? Comente abaixo!

Deixe um comentário