DEV Community

Cover image for Estruturas de Dados com JS
ananopaisdojavascript
ananopaisdojavascript

Posted on

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é"];
Enter fullscreen mode Exit fullscreen mode

Um exemplo de vetor bidimensional

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

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
  }
}
Enter fullscreen mode Exit fullscreen mode

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;
}
Enter fullscreen mode Exit fullscreen mode

isFull

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

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

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);
  }
Enter fullscreen mode Exit fullscreen mode

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();
  }
Enter fullscreen mode Exit fullscreen mode

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];
  }
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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++;
  }
Enter fullscreen mode Exit fullscreen mode

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;
  }
Enter fullscreen mode Exit fullscreen mode

Peek

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

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

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);
Enter fullscreen mode Exit fullscreen mode

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);
    }
  }
}
Enter fullscreen mode Exit fullscreen mode

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
    }
  }
Enter fullscreen mode Exit fullscreen mode

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++;
  }
Enter fullscreen mode Exit fullscreen mode

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--;
  }
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

Á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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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);
    }
  }
Enter fullscreen mode Exit fullscreen mode

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);
      }
    }
  }
Enter fullscreen mode Exit fullscreen mode

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;
    }
  }
Enter fullscreen mode Exit fullscreen mode

EncontrarMenorNo()

Encontra o nó com o menor valor na árvore

EncontrarMenorNo(no) {
    if (no.esquerda === null) {
      return no;
    } else {
      return this.EncontrarMenorNo(no.esquerda);
    }
  }
Enter fullscreen mode Exit fullscreen mode

EncontrarNoRaiz()

Encontra o nó raiz da árvore

EncontrarNoRaiz(){
    return this.root;
 }
Enter fullscreen mode Exit fullscreen mode

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

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);
    }
  }
Enter fullscreen mode Exit fullscreen mode

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;
    }
  }
Enter fullscreen mode Exit fullscreen mode

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);
Enter fullscreen mode Exit fullscreen mode

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

Top comments (1)

Collapse
 
josuefs profile image
Josué F.

Olá Ana!
Queria sugerir uma alteração se considerar pertinente.

A última estrutura de dados está com um nome mais genérico, mas a descrição condiz com uma estrutura de dados mais específica, veja abaixo:

Árvore

"... Os nós de menor valor ficam do lado esquerdo e os de maior valor ficam no lado direito."

Essa descrição acredito que se encaixe melhor à Árvore Ordenada, que tem a premissa que considera o valor maior e menor conectados à ela, mas a Árvore em um sentido genérico não necessariamente.

Gostei muito do conteúdo, esclareceu muita coisa pra mim, mas fiquei com essa dúvida da árvore e acabei encontrando essa informação. Obrigado!!