Tag: Estrutura de Dados

Filas são coletâneas de dados que mantém os objetos em uma ordem determinada ao aplicar o algoritmo FIFO (First In First Out), ou seja, o primeiro a entrar é o primeiro a sair.

function Fila(){
    let contador = 0;

    // Ambos início e final da fila estão nulos (não possuem nenhum dado)
    let inicio = null;
    let final = null;

    // Retorna a quantidade de itens na fila.
    this.GetContador = function(){
        return contador;
    }
}

A nossa fila terá quatro métodos adicionais: enqueue(dado), dequeue(), peekAt() e displayAll().

Enqueue():

Descrição:

Adiciona um item no início da fila. O processo é o mesmo do método push() utilizado na pilha, mas foi alterado por causa do exercício.

this.Enqueue = function (dado){
    // Cria um nó com o dado
    let node = {
        dado: dado,
        // Os próximos pontos serão para valorizar de maneira linear
        // Se o início está vazio (null), não será um problema
        proximo: inicio
    };

    // Se é o primeiro item a ser inserido na lista
    // o início será o final
    if (inicio === null){
        tail = node;
    }

    // define o nó como o novo início
    inicio = node;

    //incrementa o contador
    contador++;
}

Dequeue()

Descrição:

Remove e retorna o último item inserido e armazenado que seria aquele no lado oposto da fila.

this.Dequeue = function(){
    // Se a fila está vazia, retorna null
    if (contador === 0){
        return;
    }else{
        let atual = inicio;
        let anterior = null;
    }

    // Enquanto houver um próximo, ele avançará a fila
    // A ideia é ter um atual no final e um anterior
    while (atual.proximo){
        anterior = atual;
        atual = atual.proximo;
    }

    // se há mais que 1 item, 
    // remove o final e decrementa o contador em 1
    if (contador > 1){
        // remove a referência ao último nó.
        anterior.proximo = null;

        // torna o nó anterior como final da lista
        final = anterior;
    }

    // Reseta a fila
    else{
        inicio = null;
        final = null;
    }

}

DisplayAll()

Descrição:

O nome já diz tudo. Ele funciona da mesma maneira que o método da pilha().

this.DisplayAll =  function(){
    // Se não há nada no início, nada será retornado
    if (inicio === null){
        return null;
    }else{
        let arr = new Array();
        let atual = inicio;

        for ( let i = 0; i < contador; i++){
            arr[i] = atual.dado;
            atual = atual.proximo;
        }
        return arr;
    }
}

PeekAt()

Descrição:

Segue a mesma ideia do peek(), mas qualquer item da fila pode ser buscado e exibido.

this.PeekAt = function (index){
    // Qualquer coisa menor que 0 e igual ou maior que a contagem não está na fila
    if (index > -1 && index < contador){
        let atual = inicio;

        // Navega pela fila para achar o item
        for (let i = 0; i < index; i++){
            atual = atual.proximo;
        }
        return atual.dado;
    }
    // Um index fora dos limites da fila foi escolhido
    else{
        return null;
    }
}

• enqueue(dado)
• dequeue()
• displayAll()
• peekAt(index)

Gostou deste artigo? Comente abaixo!

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!