Estrutura de dados com exemplos em javascript
Estrutura de dados é uma estrutura fundamental na construção de algoritmos e na linguagens de programação, pois são responsáveis de organizar e manipular os dados de maneira mais eficiente na memória do computador, o que pode ocasionar na otimização de processos e operações.
Tipos de estruturas de dados:
Os exemplos mais comuns são listas, pilhas, filas, árvores e grafos, nos exemplos vou usar arrays como base.
Listas
Uma lista é uma coleção de valores, organizados em uma sequência ordenada, no javascript uma lista é um Array, um array é uma estrutura de dados muito útil quando você precisa armazenar e gerenciar uma coleção de itens de forma ordenada. Ele oferece muitas operações úteis para manipular esses itens, como adicionar ou remover itens, pesquisar por um item específico, etc.
No geral, você deve utilizar um array quando precisar armazenar e gerenciar uma coleção de valores e quiser ter acesso rápido a esses valores através de índices numéricos.
Exemplo:
// Criar uma lista vazia
const list = [];
// Adicionar elementos à lista
list.push(1); // adiciona 1 ao final da lista
list.unshift(2); // adiciona 2 no início da lista
// Remover elementos da lista
list.pop(); // remove o último elemento da lista
list.shift(); // remove o primeiro elemento da lista
// Acessar elementos da lista
console.log(list[0]); // imprime o primeiro elemento da lista
// Procurar elementos na lista
console.log(list.indexOf(1)); // imprime o índice do elemento 1 na lista
// Ordenar elementos da lista
list.sort(); // ordena os elementos da lista em ordem crescente
Pilha
Uma pilha é uma estrutura que segue a regra "o último a entrar, é o primeiro a sair" (Last In, First Out, ou LIFO). ou resumindo o último item que for adicionado ao array, vai ser o primeiro a sair.
A pilha é muito comum em linguagens de programação e é amplamente usada em aplicações, como desfazer operações em editores de código, na navegação quando você quer voltar a página anterior dentre outros.
Logo abaixo está um exemplo de implementação da pilha em javascript:
class Stack {
constructor() {
this.items = [];
}
push(item) {
this.items.push(item);
}
pop() {
return this.items.pop();
}
peek() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
}
Fila
Uma fila é uma estrutura inversa a pilha pois ela segue a regra "primeiro a entrar, primeiro a sair" (First In, First Out, ou FIFO), ou resumindo o primeiro a entrar, é o primeiro a sair.
A fila é uma estrutura muito comum em sistemas de atendimento ao cliente, como bancos, postos de gasolina, fila do supermercado etc, e é amplamente usado em muitas aplicações, como gerenciamento de tarefas em segundo plano, e gerenciamento de eventos.
Exemplo de implementação da fila em javascript:
class Queue {
constructor() {
this.items = [];
}
enqueue(item) {
this.items.push(item);
}
dequeue() {
return this.items.shift();
}
peek() {
return this.items[0];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
}
Árvores
Uma árvore é um pouco mais complicada que as outras, ela é uma estrutura hierarquia de dados que consiste em nós e ramos, cada nó tem um ou mais filhos, mais só pode ter um pai, O primeiro no de todos da árvore, é chamado de raiz, e os nós sem filhos são chamados de folhas.
Essa estrutura é muito útil e usada em aplicações, como por exemplo para representar estrutura de dados em sistemas de arquivos, para implementar árvores de busca e para representar as relações de hierarquia em banco de dados.
Exemplo de implementação da Árvore em javascript:
class TreeNode {
constructor(value) {
this.value = value;
this.children = [];
}
}
class Tree {
constructor() {
this.root = null;
}
}
const tree = new Tree();
const root = new TreeNode(1);
const left = new TreeNode(2);
const right = new TreeNode(3);
root.children.push(left, right);
tree.root = root;
Grafos
Um grafo em estrutura de dados é uma estrutura de dados composta por vértices (também conhecidos como nós) e arestas. Cada vértice pode ter um conjunto de arestas que o ligam a outros vértices. As arestas podem ser orientadas (o que significa que elas têm uma direção) ou não orientadas (o que significa que não têm uma direção). Grafos são usados para representar relacionamentos entre elementos de um conjunto de dados e são úteis para resolver problemas de caminho mais curto, para representar redes e para modelar sistemas complexos. veja mais
Aqui está um exemplo de um grafo não orientado em JavaScript:
class Graph {
constructor() {
this.nodes = [];
this.edges = [];
}
addNode(node) {
this.nodes.push(node);
}
addEdge(node1, node2) {
this.edges.push([node1, node2]);
}
}
const graph = new Graph();
const node1 = 'A';
const node2 = 'B';
const node3 = 'C';
graph.addNode(node1);
graph.addNode(node2);
graph.addNode(node3);
graph.addEdge(node1, node2);
graph.addEdge(node2, node3);
Neste exemplo, temos uma classe Graph que representa o grafo inteiro. O grafo tem uma matriz de nós e uma matriz de arestas. Nós adicionamos três nós ao grafo e duas arestas que os ligam. Isso nos dá um grafo com a seguinte estrutura:
A -- B -- C
Aqui está um exemplo de um grafo orientado em JavaScript:
class DirectedGraph {
constructor() {
this.nodes = [];
this.edges = [];
}
addNode(node) {
this.nodes.push(node);
}
addEdge(node1, node2) {
this.edges.push([node1, node2]);
}
}
const graph = new DirectedGraph();
const node1 = 'A';
const node2 = 'B';
const node3 = 'C';
graph.addNode(node1);
graph.addNode(node2);
graph.addNode(node3);
graph.addEdge(node1, node2);
graph.addEdge(node2, node3);
Neste exemplo, temos uma classe DirectedGraph que representa um grafo orientado. É igual ao exemplo anterior, exceto que as arestas são orientadas, o que significa que têm uma direção. Isso nos dá um grafo com a seguinte estrutura:
A -> B -> C
Alguns outros exemplos de uso de grafos incluem:
- Representar uma rede de computadores e encontrar o caminho mais curto entre dois computadores.
- Representar uma rede de transporte e encontrar o caminho mais rápido entre dois locais.
- Representar uma rede de relacionamentos e encontrar o caminho mais curto entre duas pessoas.