Estrutura de Dados e Classes JavaScript: Deque

O Deque (Fila duplamente Encadeada) funciona basicamente com uma fila, com a diferença de que você pode adicionar e remover dados de qualquer extremidade da fila. Isso torna o nosso código um pouco mais difícil, mas chegaremos lá. Continuaremos usando class para realizar nossa estrutura de dados. Precisamos, inicialmente, criar a nossa classe Deque. Ela precisará de um início (head), um final (tail) e um contador:

class Deque {
    constructor(head = null, tail = null, count = 0){
        this.head = head;
        this.tail = tail;
        this.count = count;
    }
}

Também precisaremos criar os métodos GetHead, GetTail e GetCount:

GetHead(){
    if (this.head){
        return this.head.data;
    }
    return null;
}

GetTail(){
    if (this.tail){
        return this.tail.data;
    }
    return null;
}

GetCount(){
    return this.count;
}

A nossa fila duplamente encadeada terá os seguintes métodos:

• MostrarInicioFim();
• MostrarFimInicio();
• AdicionarInicio(data);
• AdicionarFim(data);
• RemoverInicio();
• RemoverFim().

Para criarmos nossos métodos, criaremos nosso código de forma diferente aos anteriores. Utilizaremos uma Classe de auxílio, para evitar reescrever código:

class Node{
    constructor(data, next = null){
        this.data = data;
        this.next = next;
    }
}

MostrarInicioFim():

Esse método retorna um array com os dados, percorrendo do início ao fim:

MostrarInicioFim(){
    if (this.head != null){
        let arr = [];
        let current = this.head;
        
        while (current){
            arr.push(current.data);
            current = current.next;
        }
        return arr;
    } else {
        return null;
    }
}

MostrarFimInicio():

Semelhante ao nosso método anterior, ele retorna um array com os dados da fila, porém, percorrendo do fim ao início. Para isso, utilizaremos o reverse():

MostrarFimInicio(){
    if (this.head != null){
        let arr = this.MostrarInicioFim();
        return arr.reverse();
    } else {
        return null;
    }
}

AdicionarInicio(data):

Adiciona o dado no início de nossa fila e, para isso, usaremos nossa classe Node criada anteriormente para auxílio. Precisamos também incrementar o nosso contador:

AdicionarInicio(data){
    let no = new Node(data);
    no.next = this.head;
    this.head = no;

    if (!this.tail) {
        this.tail = this.head;
    }
    this.count++;
}

AdicionarFim(data):

Esse método adicionar o dado no fim da fila. Semelhante ao nosso método anterior, usaremos a nossa classe Node de apoio. Precisamos também, nesse método, incrementar nosso contador.

AdicionarFim(data){
    let no = new Node(data);
    if (!this.head){
        this.head = no;
    } else {
        this.tail.next = no;
    }
    this.tail = no;
    this.count++;
}

RemoverInicio():

Remove o dado que está no início (head) de nossa fila duplamente encadeada.

RemoverInicio(){
    if (this.head){
        if (this.count === 1){
            this.head = null;
            this.tail = null;
        } else {
            this.head = this.head.next;
        }
        this.count--;
    }
}

RemoverFim():

Remove o dado que está na posição final da nossa fila:

RemoverFim(){
    if (this.head){
        if (this.count === 1){
            this.head = null;
            this.tail === null;
        } else {
            let current = this.head;

            while(current.next.next){
                current = current.next;
            }

            this.tail = current;
            this.tail.next = null;
        }
        this.count--;
    }
}

Gostou deste artigo? Comente abaixo!