Estrutura de Dados com JavaScript: Fila

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!

Deixe um comentário