Olá pessoal! Neste artigo, demonstrarei as principais Estruturas de Dados utilizando JavaScript. Será uma postagem bem longa, por isso, prepare seu café e uma boa leitura!
FILA:
Filas são estruturas de dados onde o primeiro a entrar é o primeiro a sair. É chamado de FIFO (First In First Out). As operações em Fila são análogas ao que ocorre em filas reais, como a fila de um banco, por exemplo, com a exceção de que os elementos na fila não se movem, conforme o primeiro elemento é retirado. Na estrutura de dados Fila, o algoritmo indica quem está na primeira posição.
Utilizaremos as classes que foram implementadas no ECMAScript 2015 para criação de nossa fila. A nossa estrutura terá os seguintes métodos:
- Enqueue (inserção na fila);
- Dequeue (remoção da fila);
- MostrarTudo;
- VisualizarEm.
Para começar, precisamos criar uma classe chamada Fila, onde teremos o início da fila (head), fim da fila (tail) e um contador (count). Como a fila está vazia, o nosso head e nosso tail recebem o valor null, e nosso contador começa em 0. Precisamos também de um método Get para nosso contador:
class Fila {
constructor(head = null, tail = null, count = 0){
this.head = head;
this.tail = tail;
this.count = count;
}
GetContador(){
return this.count;
}
}
Enqueue:
Para adicionarmos um item no início da nossa fila, precisamos criar um nó, que conterá o dado e uma referência à próxima posição da fila, que deverá ser null. Quando inserirmos nosso primeiro elemento, o início e o final da fila serão o mesmo elemento, e precisaremos incrementar o contador:
Enqueue(data){
let no = {
data: data,
next: this.head
};
if (this.head === null){
this.tail = no;
}
this.head = no;
this.count++;
}
Dequeue:
Removeremos o primeiro elemento da fila e retornaremos o último item inserido e armazenado no final da fila. Fazendo isso, teremos que, enquanto houver um próximo elemento, avançaremos na fila. A ideia é ter um atual no final da fila e um anterior e, então, teremos que decrementar o contador:
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:
O próprio nome já diz: mostraremos todos os elementos da fila. Utilizaremos um vetor para isso e, com um laço de repetição, iremos inserir cada valor em sua respectiva posição neste vetor. Também precisamos verificar se há elementos na fila:
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:
No método VisualizarEm, iremos procurar o elemento na nossa fila, buscando-o e exibindo-o. Utilizaremos um laço de repetição para percorrer nossa fila e encontrar o elemento que buscamos:
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);
E a nossa saída será:
PILHA:
A pilha é uma estrutura de dados que implementa o conceito de último a entrar, primeiro a sair (LIFO (Last in First Out)), ou seja, o último elemento adicionado será o primeiro elemento a ser removido. Utilizaremos também, na nossa estrutura de dados, a palavra-chave class, que foi introduzida no ECMAScript 2015. Mas isso não significa que JavaScript é uma linguagem orientada e objetos. O JavaScript continua sendo orientado a protótipos, ou seja, o prototype continua agindo “por baixo dos panos”, e a palavra-chave class apenas “mascara” toda essa prototipagem, tornando o código mais simples de ser lido.
Abaixo temos uma imagem do funcionamento da pilha:
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;
}
}
Nossa pilha terá os seguintes métodos:
- Push;
- Visualizar;
- Remover;
- MostrarTodos.
Push:
Para criar nosso método push, precisamos criar um nó. Cada nó precisa ter o dado e a referência para o próximo nó, que precisa ser null, pois cada vez que inserirmos algo na pilha, esse elemento inserido deverá ser o primeiro a ser removido. Então, cada nó inserido deve virar o topo da pilha.
Push(data){
let no = {
data: data,
next: null
};
no.next = this.top;
this.top = no;
this.count++;
}
Visualizar:
Para visualizarmos o item que está no topo da pilha, precisamos nos certificar de que a pilha não está vazia. Caso a pilha não estiver vazia, retornaremos o dado que está no topo de nossa estrutura:
Visualizar(){
if (this.top === null){
return null;
} else {
return this.top.data;
}
}
Remover:
Para remover o elemento do topo da pilha, precisamos entender que a pilha não poderá estar vazia. Caso ela não esteja vazia, removeremos o elemento do topo e diminuiremos o nosso contador em 1.
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:
Iremos adicionar os dados em um vetor, para então exibi-los. Precisamos ter certeza que nossa pilha não está vazia e, então, criamos um vetor, Utilizaremos um laço de repetição que irá inserir cada elemento de nossa pilha em sua respectiva posição:
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á:
