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.
- Vetores ou Arrays Dimensionais - Parte 1
- Vetores ou Arrays Dimensionais: Exemplos - Parte 2
- 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.
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! 😊
Top comments (1)
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
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!!