# 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

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

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

Um exemplo de vetor bidimensional

```javascript
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.

* [Vetores ou Arrays Dimensionais - Parte 1](https://ananopaisdojavascript.hashnode.dev/vetores-ou-arrays-dimensionais-parte-1)
* [Vetores ou Arrays Dimensionais: Exemplos - Parte 2](https://ananopaisdojavascript.hashnode.dev/vetores-ou-arrays-dimensionais-exemplos-parte-2)
* [Matrizes ou Arrays Multidimensionais](https://ananopaisdojavascript.hashnode.dev/matrizes-ou-arrays-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.

```javascript
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

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

## `isFull`

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

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

## `Push`

Operação que inclui elementos na pilha

```javascript
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

```javascript
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

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

Eis o código completo:

```javascript
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.

```javascript
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

```javascript
// 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

```javascript
// 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

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

Eis o código completo:

```javascript
// 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.

```javascript
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

```javascript
// 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

```javascript
// 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.

```javascript
// 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:

```javascript
// 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.

```javascript
// 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.

```javascript
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.

```javascript
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

```javascript
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

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

## `EncontrarNoRaiz()`

Encontra o nó raiz da árvore

```javascript
EncontrarNoRaiz(){
    return this.root;
 }
```

## `EmOrdem(no)`

Percorre a árvore a partir de um nó.

```javascript
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.

```javascript
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.

```javascript
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.

```javascript
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

```javascript
// 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! 😊