Estrutura de Dados com JavaScript: Deque (Fila duplamente encadeada)

A fila duplamente encadeada é basicamente como uma fila, exceto que você pode adicionar ou remover de qualquer lado. Agora que você está um pouco mais acostumado a como isso funciona, eu gostaria de tornar as coisas um pouco mais difíceis.

function Deque() {
    let contador = 0;
    let head = null;
    let tail = null;

    // Permite visualizar o valor armazenado na cabeça
    this.getHead = function() {
        if (head) {
            return head.dado;
        }

        return null;
    }

    // Permite visualizar o valor armazenado no final
    this.getTaill = function() {
        if (tail) {
            return tail.dado;
        }
        return null;
    }

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

    // Permite definir a estrutura do nó fora de cada método.
    // Dessa forma, será necessário fazer apenas uma vez
    let Node = function(dado) {
        this.dado = dado;
        this.proximo = null;
    }

}

 

A fila duplamente encadeada terá muito mais métodos que o outro, com um total de 10, os que você já viu e:

DisplayHeadToTail(), DisplayTailToHead() AddHead(data), AddTail(data),RemoveHead() e RemoveTail().

DisplayHeadToTail():

Descrição:

Retorna um array com os dados ou, se vazio, retorna null.

this.DisplayHeadToTail = function() {
    if (head != null) {
        let arr = new Array();
        let atual = head;

        // enquanto houver um atual
        while (atual) {

            // ATENÇÃO: Para quem é novo no javascript, dê uma olhada. Você consegue adivinhar o que esse método faz?
            arr.push(atual.dado);
            atual = atual.proximo;
        }

        return arr;
    } else {
        return null;
    }
}

DisplayTailToHead():

Descrição:

Retorna os dados da fila duplamente encadeada do início ao fim (oposto ao anterior).

this.DisplayTailToHead = function() {
    if (head != null) {

        // Chama DisplayHeadToTail() e inverte ela.
        let arr = this.DisplayHeadToTail();

        // Este é um dos grandes métodos do JavaScript.
        return arr.reverse();
    } else {
        return null;
    }
}

AddHead():

Descrição:

Adiciona ao início (head) da fila duplamente encadeada.

this.AddHead = function(dado) {

    // Como você pode ver, agora nós precisamos declarar um novo nó
    let node = new Node(dado);

    node.proximo = head;
    head = node;

    // Se a lista está vazia:
    if (!tail) {
        tail = head;
    }

    contador++;
}

AddTail():

Descrição:

Adiciona ao final (tail) da fila duplamente encadeada.

this.AddTail = function(dado) {
    let node = new Node(dado);

    // Se a lista está vazia
    if (!head) {
        head = node;
    } else {
        tail.proximo = node;
    }

    tail = node;
    contador++;
}

RemoveHead():

Descrição:

Remove o início(head) da fila duplamente encadeada.

this.RemoveHead = function() {
    if (head) {
        // Se é o item final
        if (contador === 1) {
            head = null;
            tail = null;
        } else {
            head = head.proximo;
        }

        contador--;
    }
}

RemoveTail():

Descrição:

Remove o elemento final (tail) da fila duplamente encadeada:

this.RemoveTail = function() {
    if (head) {
        // Se não é o último item
        if (contador === 1) {
            head = null;
            tail = null;
        } else {
            let atual = head;

            // precisamos ir tão longe quanto os dois antes da última
            while (atual.proximo.proximo) {
                atual = atual.proximo;
            }

            tail = atual;
            tail.proximo = null;
        }

        contador--;
    }
}
  • DisplayHeadToTail():
  • DisplayTailToHead():
  • AddHead(dado):
  • AddTail(dado):
  • RemoveHead():
  • RemoveHead():

Gostou deste artigo? Comente abaixo!

Deixe um comentário