Estrutura de Dados com Classes JavaScript

FILA:

Image for post

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

Enqueue:

Enqueue(data){
    let no = {
        data: data,
        next: this.head
    };
    if (this.head === null){
        this.tail = no;
    }
    this.head = no;
    this.count++;
}

Dequeue:

Dequeue(){
    if (this.count === 0){
        return;
    } else {
        let current = this.head;
        let previous = null;
        while (current.next){
            previous = current;
            current = current.next;
        }
        if (this.count > 1){
            previous.next = null;
            this.tail = previous;
        } else {
            this.head = null;
            this.tail = null;
        }
        this.count--;
    }
}

MostrarTudo:

MostrarTudo(){
    if (this.head === null){
        return null;
    } else {
        let arr = [];
        let current = this.head;
        for (let i = 0; i < this.count; i++) {
            arr[i] = current.data;
            current = current.next;
        }
        return arr;
    }
}

VisualizarEm:

VisualizarEm(index){
    if (index > -1 && index < this.count){
        let current = this.head;
        for (let i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    } else {
        return null;
    }
}

Agora, vamos testar:

let fila = new Fila();
fila.Enqueue(1);
fila.Enqueue(2);
fila.Enqueue(3);
fila.Enqueue(4);
fila.Enqueue(5);
fila.Enqueue(6);
fila.Dequeue();
fila.Dequeue();
console.log(fila.VisualizarEm(1));
console.log(fila.MostrarTudo());
console.log(fila);
Image for post

PILHA:

Image for post

Então, para começarmos a implementar a pilha, precisamos construir a nossa classe Pilha e seu construtor. Vamos implementar também um contador, que será útil para nos mostrar a quantidade de itens na pilha. No nosso construtor, precisamos setar nossos valores do contador e do topo da pilha. Como ainda não há nada na pilha, o topo é null e o contador é 0:

class Pilha {
    constructor(top = null, count = 0){
        this.top = top;
        this.count = count;
    }
    GetContador(){
        return this.count;
    }
}

Push:

Push(data){
    let no = {
       data: data,
       next: null
    };
    no.next = this.top;
    this.top = no;
    this.count++;
}

Visualizar:

Visualizar(){
    if (this.top === null){
        return null;
    } else {
        return this.top.data;
    }
}

Remover:

Remover(){
    if (this.top === null){
        return null;
    } else {
        let remover = this.top;
        this.top = this.top.next;
        if (this.count > 0){
            this.count--;
        }
        return remover.data;
    }
}

MostrarTodos:

MostrarTodos(){
    if (this.top === null){
        return null;
    } else {
        let arr = [];
        let current = this.top;
        for (let i = 0; i < this.count; i++){
            arr[i] = current.data;
            current = current.next;
        }
        return arr;
    }
}

E podemos testar a nossa estrutura de dados, instanciando uma nova pilha:

let pilha = new Pilha();
pilha.Push(1);
pilha.Push(2);
pilha.Push(3);
pilha.Push(4);
pilha.Push(5);
pilha.Push(6);
pilha.Push(7);
pilha.Remover();
console.log(pilha.Visualizar());
console.log(pilha.MostrarTodos());
console.log(pilha);

E a saída será:

Image for post

LISTA ENCADEADA:

Image for post
class ListaEncadeada{
    constructor(head = null, count = 0){
        this.head = head;
        this.count = count;
    }
    GetContador(){
        return this.count;
    }
}

Vamos lá!

MostrarTudo():

MostrarTudo(){
    if (this.head === null){
        return null;
    } else {
        let arr = [];
        let current = this.head;
        for (let i = 0; i < this.count; i++) {
            arr[i] = current.data;
            current = current.next;
        }
        return arr;
    }
}

MostrarEm(index):

MostrarEm(index){
    if (index > -1 && index < this.count){
        let current = this.head;
        let i = 0;
        while (i++ < index){
                current = current.next;
        }
        return current.data;
    } else {
        return null;
    }
}

AdicionarInicio(data):

AdicionarInicio(data){
    let no = {
        data: data,
        next: this.head
    };
    this.head = no;
    this.count++;
}

AdicionarNaPosicao(data, index):

AdicionarNaPosicao(data, index){
    if (index === 0) {
        this.AdicionarInicio(data);
    } else if (index > -1 && index < this.count){
        let no = {
            data: data,
            next: null
        };
        let previous;
        let current = this.head;
        let i = 0;
        while (i++ < index){
            previous = current;
            current = current.next;
        }
        previous.next = no;
        no.next = current;
        this.count++;
    } else {
        console.log("Não existe esta posição na lista.")
    }
}

RemoverInicio():

RemoverInicio(){
    if (this.head === null){
        return null;
    } else {
        let out = this.head;
        this.head = this.head.next;
        if (this.count > 0){
            this.count--;
        }
        return out.data;
    }
}

RemoverNaPosicao(index):

RemoverNaPosicao(index){
    if (index === 0) {
        return this.RemoverInicio(this);
    } 
        
    else if ( index > -1 && index < this.count){
            
        let current = this.head;
        let previous;
        let i = 0;
        while (i++ < index){
            previous = current;
            current = current.next;
        }
        previous.next = current.next;
        this.count--;
        return current.data;
    } else {
        return null;
    }    
}

DEQUE (Fila Duplamente Encadeada):

Image for post

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;
}
class Node{
    constructor(data, next = null){
        this.data = data;
        this.next = next;
    }
}

MostrarInicioFim():

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():

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

AdicionarInicio(data):

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):

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

RemoverInicio():

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

RemoverFim():

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--;
    }
}

LISTA DUPLAMENTE ENCADEADA:

Image for post

Para criar nossa Lista, precisaremos de uma classe principal chamada ListaDuplamenteEncadeada e um classe que nos servirá de apoio, evitando reescrever código, chamada Node. A nossa lista terá um contador, que começará em 0 e, também, uma cabeça (head) e uma cauda (tail), que inicialmente terão o valor null:

class ListaDuplamenteEncadeada {
    constructor(head = null, tail = null, count = 0){
        this.head = head;
        this.tail = tail;
        this.count = count;
    }
}
class Node{
    constructor(data, next = null, previous = null){
        this.data = data;
        this.next = next;
        this.previous = previous;
    }
}

Precisamos também implementar 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;
}

Vamos lá!

MostrarTudo():

MostrarTudo(){
    if (this.head){
        let arr = [];
        let current = this.head;
        for (let i = 0; i < this.count; i++){
            arr[i] = current.data;
            current = current.next;
        }
        return arr;
    } else {
        return null;
    }
}

MostrarFimInicio():

MostrarFimInicio(){
    if (this.head){
        let arr = [];
        let current = this.tail;
        for (let i = 0; i < this.count; i++){
            arr[i] = current.data;
            current = current.previous;
        }
        return arr;
    } else {
        return null;
    }
}

VisualizarEm(index):

VisualizarEm(index){
    if (index > -1 && index < this.count){
        let current = this.head;
        let i = 0;
        while (i++ < index){
            current = current.next;
        }
        return current.data;
    } else {
        return null;
    }
}

AdicionarInicio(data):

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

AdicionarFinal(data):

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

AdicionarEm(data, index):

AdicionarEm(data, index){
    if (index > 0 && index < this.count){
        let no = new Node(data);
        let current = this.head;
        let i = 0;
        while(i++ < index){
            current = current.next;
        }
        current.previous.next = no;
        no.next = current;
        no.previous = current.previous;
        current.previous = no;
            
        this.count++;
    } else if (index < 1){
        this.AdicionarInicio(data);
    } else {
        this.AdicionarFinal(data);
    }
}

RemoverInicio():

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

RemoverFinal():

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

RemoverEm(index):

RemoverEm(index){
    if (index > 0 && index < this.count-1){
        let current = this.head;
        let i = 0;
        while( i++ < index){
            current = current.next;
        }
        current.previous.next = current.next;
        current.next.previous = current.previous;
        this.count--;
    } else if (index < 1){
        this.RemoverInicio();
    } else {
        this.RemoverFinal();
    }
}

Teste no seu navegador:

let lista = new ListaDuplamenteEncadeada();
lista.AdicionarInicio(1);
lista.AdicionarInicio(4);
lista.AdicionarInicio(5);
lista.AdicionarInicio(6);
lista.AdicionarFinal(2);
lista.AdicionarEm(3, 1);
console.log(lista.VisualizarEm(1));
console.log(lista.MostrarFimInicio());
lista.RemoverEm(2);
lista.RemoverInicio();
lista.RemoverFinal();
console.log(lista.MostrarTudo());

E a saída será:

Image for post

BINARY SEARCH TREE (Árvore de Busca Binária):

Para começar, criaremos uma classe chamada nó, que servirá de apoio para a criação da nossa Árvore Binária:

class No{
    constructor(data, esquerda = null, direita = null){
        this.data = data;
        this.esquerda = esquerda;
        this.direita = null;
    }
}

Agora, vamos criar a nossa Árvore:

class ArvoreBuscaBinaria{
    constructor(root = null){
        this.root = null;
    }
}

Também teremos os métodos principais da nossa árvore binária, que são:

E os métodos auxiliares, que são:

Insercao(data) e InserirNo(no, novoNo):

Insercao(data){
    let novoNo = new No(data);
    
    if (this.root === null){
        this.root = novoNo;
    } else {
        this.InserirNo(this.root, novoNo);
    }
}

O método InserirNo(no, novoNo) verifica em qual parte da árvore o nó deve ser inserido e coloca-o no lugar correto. Se o dado a ser inserido for menor que o nó raiz, o novo dado deve ir para a esquerda. Senão, o novo dado deve ir para a direita. O mesmo vale para os outros nós que já estão posicionados, ou seja, acontece uma comparação dos dados fornecidos com os dados do nó atual, movendo-se para a esquerda ou para a direita e recorrendo até encontrar um nó correto para qual o novo nó possa ser adicionado.

InserirNo(no, novoNo){
    if (novoNo.data < no.data){
        if (no.esquerda === null){
            no.esquerda = novoNo;
        } else {
            this.InserirNo(no.esquerda, novoNo);
        }
    } else {
        if (no.direita === null){
            no.direita = novoNo;
        } else {
            this.InserirNo(no.direita, novoNo);
        }
    }
}

Remover(data) e RemoverNo(no, key):

Remover(data){
    this.root = this.RemoverNo(this.root, data);
}
RemoverNo(no, key){
    if (no === null){
        return null;
    } else if (key > no.data){
        no.direita = this.RemoverNo(no.direita, key);
        return no;
    } else {
        if (no.esquerda === null && no.direita === null){
            no = null;
            return no;
        } 
        if(no.esquerda === null){
            no = no.direita;
            return no;
        } else if (no.direita === null){
            no = no.esquerda;
            return no;
        }
        let aux = this.EncontrarMenorNo(no.direita);
        no.data = aux.data;
        no.direita = this.RemoverNo(no.direita, aux.data);
        return no;
    }
}

EmOrdem(no):

EmOrdem(no){
    if (no !== null){
        this.EmOrdem(no.esquerda);
        console.log(no.data);
        this.EmOrdem(no.direita);
    }
}

PreOrdem(no):

PreOrdem(no){
    if (no !== null){
        console.log(no.data);
        this.PreOrdem(no.esquerda);
        this.PreOrdem(no.direita);
    }
}

PosOrdem(no):

PosOrdem(no){
    if (no !== null){
        this.PosOrdem(no.esquerda);
        this.PosOrdem(no.direita);
        console.log(no.data);
    }
}

Agora, precisamos declarar métodos auxiliares.

EncontrarMenorNo(no):

EncontrarMenorNo(no){
    if (no.esquerda===null){
        return no;
    } else {
        return this.EncontrarMenorNo(no.esquerda);
    }
}

EncontrarNoRaiz():

EncontrarNoRaiz(){
    return this.root;
}

Pesquisar(no, data):

Pesquisar(no, data){
    if (no === null){
        return null;
    }
    else if (data < no.data){
        return this.Pesquisar(no.esquerda, data);
    } else if (data > no.data){
        return this.Pesquisar(no.direita, data);
    } else {
        return no;
    }
}

Agora, precisamos criar uma nova árvore e implementar seus métodos:

let arvoreBinaria = new ArvoreBuscaBinaria();
arvoreBinaria.Insercao(20);
arvoreBinaria.Insercao(25);
arvoreBinaria.Insercao(15);
arvoreBinaria.Insercao(10);
arvoreBinaria.Insercao(28);
arvoreBinaria.Insercao(27);
arvoreBinaria.Insercao(9);
arvoreBinaria.Insercao(7);
arvoreBinaria.Insercao(2);
arvoreBinaria.Insercao(28);
let raiz = arvoreBinaria.EncontrarNoRaiz();
arvoreBinaria.EmOrdem(raiz);
arvoreBinaria.Remover(2);
arvoreBinaria.PosOrdem(raiz);
arvoreBinaria.PreOrdem(raiz);

E nossa saída será:

Image for post