Estruturas de Dados com JS

Definição

Estruturas de dados são modos de armazenar e organizar dados na memória de um computador para que possam ser usados com mais eficiência. Podem ser usados em vários tipos de aplicativos. Em alguns casos, são bem especializados e orientados a tarefas específicas. As estruturas de dados clássicas são:

Vetores e matrizes (Arrays)
Pilha
Fila
Lista
Árvore

Vetores (Arrays)

É uma estrutura homogênea que mantém uma série de elementos de dados do mesmo tipo. Além de possuírem tamanho fixo, podem ter uma dimensão (vetores) ou mais de uma (matriz).

Alguns exemplos de vetor unidimensional

const num = [1, 2, 3, 4, 5];

const blackPink = ["Jisoo", "Lisa", "Jennie", "Rosé"];

Um exemplo de vetor bidimensional

const moreNumbers = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
];

Nessas anotações aqui você pode entender melhor como funcionam os vetores unidimensionais e multidimensionais.

Pilha

A pilha (stack) é uma estrutura de dados usada para colecionar elementos e permitir o acesso somente a um item da coleção armazenado - o último item que foi incluído na estrutura (item do topo). A pilha funciona com o método LIFO (Left In, First Out). O último item é o primeiro a sair da pilha.

class Stack {
  constructor(maxSize) {
    // definir o número máximo de elementos da pilha caso não seja fornecido
    if (isNaN(maxSize)) return maxSize = 10;
    this.maxSize = maxSize; // iniciar um array que conterá os valores da pilha
    this.container = []; // vetor que terá os elementos da pilha
  }
}

Vamos ver os operadores da pilha:

`isEmpty`

Operação que verifica se uma pilha está vazia

// verifica se a pilha está vazia
  isEmpty() {
    return this.container.length === 0;
}

`isFull`

Operação que verifica se uma pilha está cheia

// verifica se a pilha está cheia
  isFull() {
    return this.container.length >= this.maxSize;
}

`Push`

Operação que inclui elementos na pilha

push(element) {
    // Verifica se a pilha está cheia
    if (this.isFull()) {
      console.log("Stack Overflow!");
      return;
    }
    this.container.push(element);
  }

`Pop`

Operação que exclui elementos da pilha

pop() {
    // Verifica se a pilha está vazia
    if (this.isEmpty()) {
      console.log("Stack Underflow!");
      return;
    }
    this.container.pop();
  }

`Peek`

Operação que lê o valor armazenado no topo da pilha

peek() {
    if (this.isEmpty()) {
      console.log("Stack Underflow!");
      return;
    }
    return this.container[this.container.length - 1];
  }

Eis o código completo:

class Stack {
  constructor(maxSize) {
    // definir o número máximo de elementos da pilha caso não seja fornecido
    if (isNaN(maxSize)) return maxSize = 10;
    this.maxSize = maxSize; // iniciar um array que conterá os valores da pilha
    this.container = []; // vetor que terá os elementos da pilha
  }

  // método para ver os itens
  display() {
    console.log(this.container);
  }

  // verifica se a pilha está vazia
  isEmpty() {
    return this.container.length === 0;
  }

  // verifica se a pilha está cheia
  isFull() {
    return this.container.length >= this.maxSize;
  }

  push(element) {
    // Verifica se a pilha está cheia
    if (this.isFull()) {
      console.log("Stack Overflow!");
      return;
    }
    this.container.push(element);
  }

  pop() {
    // Verifica se a pilha está vazia
    if (this.isEmpty()) {
      console.log("Stack Underflow!");
      return;
    }
    this.container.pop();
  }

  peek() {
    if (this.isEmpty()) {
      console.log("Stack Underflow!");
      return;
    }
    return this.container[this.container.length - 1];
  }

  // método para limpar o array
  clear() {
    this.container = [];
  }
}

let pilha = new Stack(3);
pilha.push(1);
pilha.push(2);
pilha.push(3);
pilha.display();
pilha.pop();
pilha.clear();
pilha.display();
console.log(pilha);

Fila

Estrutura de dados que usa o método FIFO (First In, First Out). O primeiro item é o primeiro a sair da fila.

class Queue {
  constructor(value) {
    this._size = 0;

    if (value === undefined) return this._first = null, this._last = null;
    else this.enqueue(value);
  }

  // retornar tamanho da fila
  get size() {
    return this._size;
  }

  // verificar se a fila está vazia
  get empty() {
    return this.size === 0;
  }
}

Vamos ver os operadores da fila:

`Enqueue`

Operador para incluir elementos na fila

// colocar elementos na fila
  enqueue(value) {
    let newNode = new QueueNode(value);
    this.empty ? this._first = newNode : this._last.next = newNode;
    this._last = newNode;
    this._size++;
  }

`Dequeue`

Operador para excluir elementos da fila

// excluir elementos da fila
  dequeue() {
    let itemToRemove = this._first;
    this._first = itemToRemove.next;
    this._size--;
    return itemToRemove.value;
  }

`Peek`

Operação que lê o valor armazenado no topo da fila

// ler o primeiro elemento da fila
  peek() {
    return this._first.value;
  }

Eis o código completo:

// classe que define a estrutura de dados
class QueueNode {
  constructor(value) {
    this._value = value;
    this._next = null;
  }

  set next(value) {
    this._next = value;
  }

  get next() {
    return this._next;
  }

  get value() {
    return this._value;
  }
}


class Queue {
  constructor(value) {
    this._size = 0;

    if (value === undefined) return this._first = null, this._last = null;
    else this.enqueue(value);
  }

  // retornar tamanho da fila
  get size() {
    return this._size;
  }

  // verificar se a fila está vazia
  get empty() {
    return this.size === 0;
  }

  // colocar elementos na fila
  enqueue(value) {
    let newNode = new QueueNode(value);
    this.empty ? this._first = newNode : this._last.next = newNode;
    this._last = newNode;
    this._size++;
  }

  // excluir elementos da fila
  dequeue() {
    let itemToRemove = this._first;
    this._first = itemToRemove.next;
    this._size--;
    return itemToRemove.value;
  }

  // ler o primeiro elemento da fila
  peek() {
    return this._first.value;
  }
}

let fila = new Queue(10);
fila.enqueue(20);
fila.enqueue(30);
console.log(fila);

Lista Encadeada

Listas encadeadas são estruturas de dados feitas de grupos de nós que juntos representam uma sequência.

class LinkedList {
  constructor(value) {
    this._head = null;
    this._size = 0;

    if (value !== undefined) {
      this.append(value);
    }
  }
}

Vamos ver os operadores da lista encadeada:

`Get`

Operador que retorna os nós da lista encadeada

// obter os nós da lista
  getPrevNextNodes(index) {
    let count = 0;
    let prevNode = this.head;
    let nextNode = prevNode.next;

    while (count < index - 1) {
      prevNode = prevNode.next;
      nextNode = prevNode.next;
      count++;
    }

    return {
      prevNode,
      nextNode
    }
  }

`Insert`

Operador que insere (duh!) elementos na lista

// inserir elementos na lista
  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  // inserir valores no começo da lista
  prepend(value) {
    const node = new Node(value);

    node.next = this.head;
    this.head = node;
    this.length++;
  }

  insert(value, index) {
    if (index >= this.length) {
      this.append(value);
    }

    const node = new Node(value);

    const {
      prevNode,
      nextNode
    } = this.getPrevNextNodes(index);
    prevNode.next = node;
    node.next = nextNode;

    this.length++;
  }

`Remove`

Operador que remove (duh de novo!) elementos da lista com base no índice.

// remover os nós da lista
  remove(index) {
    let {
      previousNode,
      currentNode
    } = this.getNodes(index);
    previousNode.next = currentNode.next;
    this.length--;
  }

Eis o código completo:

// classe para criar os nós da lista
class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = this.head;
    this.length = 0;
  }

  // inserir elementos na lista
  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.length++;
  }

  // inserir valores no começo da lista
  prepend(value) {
    const node = new Node(value);

    node.next = this.head;
    this.head = node;
    this.length++;
  }

  insert(value, index) {
    if (index >= this.length) {
      this.append(value);
    }

    const node = new Node(value);

    const {
      prevNode,
      nextNode
    } = this.getPrevNextNodes(index);
    prevNode.next = node;
    node.next = nextNode;

    this.length++;
  }

  // obter os nós da lista
  getPrevNextNodes(index) {
    let count = 0;
    let prevNode = this.head;
    let nextNode = prevNode.next;

    while (count < index - 1) {
      prevNode = prevNode.next;
      nextNode = prevNode.next;
      count++;
    }

    return {
      prevNode,
      nextNode
    }
  }

  // remover os nós da lista
  remove(index) {
    let {
      previousNode,
      currentNode
    } = this.getNodes(index);
    previousNode.next = currentNode.next;
    this.length--;
  }

  // inverter a lista
  remove(index) {
    let {
      previousNode,
      currentNode
    } = this.getNodes(index);
    previousNode.next = currentNode.next;
    this.length--;
  }
}

const linkedList1 = new LinkedList();
linkedList1.append(2);
linkedList1.append(3);
linkedList1.append(4);
console.log(linkedList1);

let linkedList2 = new LinkedList();
linkedList2.append(23);
linkedList2.append(89);
linkedList2.append(12);
linkedList2.append(3);
console.log(linkedList2);

Árvore

A árvore é uma estrutura não linear, ou seja, é uma coleção de nós conectados por arestas. Os nós de menor valor ficam do lado esquerdo e os de maior valor ficam no lado direito.

// criar a árvore
class ArvoreBuscaBinaria {
  constructor(root = null) {
    this.root = null;
  }
}

Vamos ver os métodos da árvore:

`Insercao(data)`

Cria um novo nó na árvore com o valor especificado.

Insercao(data) {
    let novoNo = new No(data);

    if (this.root === null) {
      this.root = novoNo;
    } else {
      this.InserirNo(this.root, novoNo);
    }
  }

`InserirNo(no, novoNo)`

Verifica em qual parte da árvore o nó deve ser inserido.

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)` / `RemoverNo(no, key)`

Remove nós da árvore

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

`EncontrarMenorNo()`

Encontra o nó com o menor valor na árvore

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

`EncontrarNoRaiz()`

Encontra o nó raiz da árvore

EncontrarNoRaiz(){
    return this.root;
 }

`EmOrdem(no)`

Percorre a árvore a partir de um nó.

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

`PreOrdem(no)`

Percorre primeiro o nó raiz e vai para o lado esquerdo e depois para o lado direito.

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

`PosOrdem(no)`

Percorre o lado esquerdo, depois vai para o lado direito e por último vai até o nó raiz.

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

`Pesquisar(no, data)`

Pesquisa o nó com dados que tenham valor em toda a árvore.

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

Eis o código completo

// criar os nós da árvore
class No {
  constructor(data, esquerda = null, direita = null) {
    this.data = data;
    this.esquerda = esquerda;
    this.direita = null;
  }
}

// criar a árvore
class ArvoreBuscaBinaria {
  constructor(root = null) {
    this.root = null;
  }

  // inserir novo nó com valor especificado
  Insercao(data) {
    let novoNo = new No(data);

    if (this.root === null) {
      this.root = novoNo;
    } else {
      this.InserirNo(this.root, novoNo);
    }
  }

  // verificar em qual parte da árvore o nó deve ser inserido
  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 nós da árvore
  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;
    }
  }

  // percorrer a árvore a partir de um nó
  EmOrdem(no) {
    if (no !== null) {
      this.EmOrdem(no.esquerda);
      console.log(no.data);
      this.EmOrdem(no.direita);
    }
  }

  // percorre primeiro o nó raiz e vai para o lado esquerdo e depois para o lado direito
  PreOrdem(no) {
    if (no !== null) {
      console.log(no.data);
      this.PreOrdem(no.esquerda);
      this.PreOrdem(no.direita);
    }
  }

  // percorre o lado esquerdo, depois vai para o lado direito e por último vai até o nó raiz
  PosOrdem(no) {
    if (no !== null) {
      this.PosOrdem(no.esquerda);
      this.PosOrdem(no.direita);
      console.log(no.data);
    }
  }

  // encontra o nó com menor valor na árvore
  EncontrarMenorNo(no) {
    if (no.esquerda === null) {
      return no;
    } else {
      return this.EncontrarMenorNo(no.esquerda);
    }
  }

  // encontra o nó raiz da árvore
  EncontrarNoRaiz(){
    return this.root;
  }

  // pesquisa o nó com dados que tenham valor em toda a árvore
  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;
    }
  }
}

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

console.log(arvoreBinaria);

E aí? Gostaram? Até a próxima anotação! 😊

Blog

Estruturas de Dados com JS

ananopaisdojavascript

Definição

Vetores (Arrays)

Pilha

`isEmpty`

`isFull`

`Push`

`Pop`

`Peek`

Fila

`Enqueue`

`Dequeue`

`Peek`

Lista Encadeada

`Get`

`Insert`

`Remove`

Árvore

`Insercao(data)`

`InserirNo(no, novoNo)`

`Remover(data)` / `RemoverNo(no, key)`

`EncontrarMenorNo()`

`EncontrarNoRaiz()`

`EmOrdem(no)`

`PreOrdem(no)`

`PosOrdem(no)`

`Pesquisar(no, data)`

Join Our Newsletter. No Spam, Only the good stuff.

Related

Estruturas de Dados com JS

ananopaisdojavascript

Definição

Vetores (Arrays)

Pilha

isEmpty

isFull

Push

Pop

Peek

Fila

Enqueue

Dequeue

Peek

Lista Encadeada

Get

Insert

Remove

Árvore

Insercao(data)

InserirNo(no, novoNo)

Remover(data) / RemoverNo(no, key)

EncontrarMenorNo()

EncontrarNoRaiz()

EmOrdem(no)

PreOrdem(no)

PosOrdem(no)

Pesquisar(no, data)

Join Our Newsletter. No Spam, Only the good stuff.

Related

`isEmpty`

`isFull`

`Push`

`Pop`

`Peek`

`Enqueue`

`Dequeue`

`Peek`

`Get`

`Insert`

`Remove`

`Insercao(data)`

`InserirNo(no, novoNo)`

`Remover(data)` / `RemoverNo(no, key)`

`EncontrarMenorNo()`

`EncontrarNoRaiz()`

`EmOrdem(no)`

`PreOrdem(no)`

`PosOrdem(no)`

`Pesquisar(no, data)`