Tag: Algoritmos

Publicado em

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!

Publicado em

Estrutura de Dados com JavaScript: Lista Encadeada

Listas encadeadas são estruturas de dados feitas de grupos de nós que juntos representam uma sequência. Você notará que a Fila e a Pilha foram criadas usando a ideia básica de uma lista encadeada. No entanto, eles têm regras especiais que os tornam diferentes em funcionalidade.

function ListaEncadeada() {
    let contador = 0;
    let head = null;

    this.GetCount = function(){
        return countador;
    }

}

Nossa lista encadeada terá 6 métodos adicionais: DisplayAll (), DisplayAt (índice), AddFirst (dados), Add (dados, índice), RemoveFirst (), RemoveAt() .

DisplayAll():

Descrição:

O nome já diz tudo. Retorna um array com os dados ou, se vazio, retorna nulo.

this.DisplayAll = function() {
    // se está vazio
    if (head === null) {
        return null;
    } else {
        //senão, percorre a lista e a coloca em um array.
        let arr = new Array();
        let atual = head;

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

DisplayAt():

Descrição:

Como o método PeekAt (indice) anterior da Fila, é exibido em um índice específico ou, fora dos limites, ele retorna null.

this.DisplayAt = function(indice) {
    // verifique se há valores fora dos limites
    if (indice > -1 && indice < contador) {
        let atual = head;
        let i = 0;

        // não fui eu, é da nczonline (veja fonte).
        // É uma maneira diferente de implementar o FOR que estamos usando
        // e eu queria que todos tivessem a chance de conhecê-lo.
        while (i++ < indice) {
            atual = atual.proximo;
        }

        return atual.dado;
    } else {
        return null;
    }
}

AddFirst():

Descrição:

Adiciona à frente da lista. Se você está se perguntando, frente é onde o índice é 0 e referenciado pelo cabeçalho.

this.AddFirst = function(dado) {
    // Cria um novo nó
    let node = {
        dado: dado,
        proximo: head
    };

    head = node;
    contador++;
}

Add()

Descrição:

Adiciona um item à lista na posição especificada.

this.Add = function(dado, indice) {
    // se o índice escolhido for 0, faça o método AddFirst (dado).
    if (indice === 0) {
        this.AddFirst(dado);
    }
    // verifique se há valores fora dos limites
    else if (indice > -1 && indice < contador) {
        let node = {
            dado: dado,
            proximo: null
        };

        let anterior;
        let atual = head;
        let i = 0;

        // encontre o local certo
        while (i++ < indice) {
            anterior = atual;
            atual = atual.proximo;
        }

        anterior.proximo = node;
        node.proximo = atual;

        contador++;
    } else {
        alert("fora de alcance");
    }
}

RemoveFirst()

Descrição:

Remove o primeiro item.

this.RemoveFirst = function() {
    // se não há itens na lista, retorna nulo
    if (head === null) {
        return null;
    } else {
        let out = head;
        head = head.proximo;

        if (contador > 0) {
            contador--;
        }

        return out.dado;
    }
}

RemoveAt()

Descrição:

Remove um item de um índice específico.

this.RemoveAt = function(indice) {
    if (indice === 0) {
        return this.RemoveFirst(indice);
    }
    // verifique se há valores fora dos limites
    else if (indice > -1 && indice < contador) {

        let atual = head;
        let anterior;
        let i = 0;

        // encontre a localização correta
        while (i++ < indice) {
            anterior = atual;
            atual = atual.proximo;
        }

        // pule o item para remover
        anterior.proximo = atual.proximo;

        // diminuir o comprimento
        contador--;
    } else {
        return null;
    }

    // retorna o valor
    return atual.dado;
}
  • DISPLAYALL():
  • DISPLAYAT(INDICE):
  • ADDFIRST(DADO):
  • ADD(DADO,INDICE):
  • REMOVEFIRST():
  • REMOVEAT(INDICE):

Gostou deste artigo? Comente abaixo!

Publicado em

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!

Publicado em

Estrutura de Dados com JavaScript: Pilha

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!