Exibir código-fonte para Estrutura de Dados

ESTRUTURA DE DADOS 

Dados, existente em vários tipos, são blocos básicos da programação. Eles representam alguma unidade de informação que pode ser acessado através de um identificador – comumente, uma variável.[1] 

A maioria das linguagens de programação trabalha com as variações baseadas nos quatro tipos primitivos de dados, sendo elas: 

INT: valores numéricos inteiros (positivos e negativos); 

FLOAT: valores numéricos decimais/com números após a vírgula (positivos e negativos); 

BOOLEAN ou booleanos: representado apenas por dois valores, “verdadeiro” e “falso”. Também chamados de operadores lógicos; 

TEXT: sequências ou cadeias de caracteres, utilizados para manipular textos e/ou outros tipos de dados não numéricos ou booleanos, como hashes de criptografia. 

E para a organização do armazenamento e manipulação desses dados, utilizamos a estruturas de dados. 

ESTRUTURA DE DADOS, O QUE SÃO? 

Estrutura de dados, conceito da ciência da computação, essencial para profissionais que atuam com dados como desenvolvedores de software, cientistas de dados, dentre outros profissionais. Representa o modo otimizado, mais organizado e eficaz de armazenar e manipular dados, auxiliando no processamento de dados, permitindo a operação de algoritmos sobre eles de forma adequada e eficiente. A estrutura de dados tem várias vertentes para que essa manipulação de dados ocorra de forma eficiente.

[[arquivo:estruturasdedados.png|400px]] 

Cada estrutura de dados tem um conjunto de métodos próprios para realizar operações como: 

Inserir ou excluir elementos; 

Buscar e localizar elementos; 

Ordenar (classificar) elementos de acordo com alguma ordem especificada.

As estruturas de dados mais simples são as variáveis. Cada variável armazena um único dado, referente a qualquer coisas do tipo de dado determinado. Mas e se precisarmos armazenar conjuntos de dados do mesmo tipo em uma única variável ?[2]

Array, podendo também ser chamado de outros nomes, como: arranjo e mais especificamente, vetor (estruturas unidimensionais)  e matriz (estruturas multidimensionais), nada mais é que um "espaço" divido em um determinado tamanho e possível de armazenar informações de um mesmo tipo (algumas poucas linguagens permitem armazenamento de dados de tipos diferentes no mesmo, sendo assim minoria de toda forma). 

EXEMPLO PRÁTICO
Armazenar os valores dos salários de funcionários de uma empresa. Então criaríamos um array, tendo seu tipo como float, já que poderíamos ter valores decimais representando determinados valores de salário, criaríamos também, uma variável do tipo inteiro para ser o "índice do vetor" (variável que usaríamos para percorrer o vetor para ler, guardar informações e realizar qualquer tipo de manipulação nele). 

[[arquivo:codigoarray.png|400px]] 


Lista

As listas armazenam os elementos de forma sequencial, diferente de como ocorre nos arrays, as suas informações podem estar em qualquer lugar da memória , já que os seus endereços estão interligados. As listas usam ponteiros para interligar os elementos mostrando o próximo endereço, sem que seja necessário que eles estejam no próximo bloco de memória. [2]

[[Arquivo:Endereços_de_memória_ligados.png]]

Usando as listas não é necessário deslocar os elementos sempre que incluir ou excluir algo, como seria no array, basta mudar o endereço, visto que cada nó da lista direciona para o ponteiro da memória onde está o próximo elemento.

[[Arquivo:Exemplo1livro.png]]
[[Arquivo:Exemplo2livro.png]]

Tipos de Listas 

Lista encadeada simples: É uma lista que contém somente um endereço por nó apontando para o próximo da lista.

[[Arquivo:Lista_encadeada_simples.png|600px]]

Lista duplamente encadeada: São listas que cada nó possui dois ponteiros, em que um aponta para o próximo nó e o outro para o anterior.

[[Arquivo:Lista_dupla.png|600px]]


Lista encadeadas circulares: Nessa lista o último nó aponta para o primeiro, esse tipo de lista pode ser simples ou dupla.

[[Arquivo:Listacircular.png]]

[[Arquivo:Listacircular2.png|600px]]

Se uma lista é ordenada, a ordem linear da lista corresponde à organização linear dos elementos da lista, podendo ser crescente ou decrescente. Se a lista não for ordenada, os elementos podem aparecer em qualquer ordem. 

Vantagens:

• Facilidade em inserir ou retirar algo no meio da lista

• Flexibilidade em criar listas de tamanhos indefinidos

Desvantagens:

• Dificuldade em acessar os últimos itens, porque só conseguimos saber o endereço do elemento seguinte

• Muitas linguagens não possuem listas prontas, o programador precisa criá-las manualmente.



- Estrutura de Dados - Fila

[4]
	A fila  é um  tipo especial de lista, onde os elementos são inseridos em uma extremidade, chamada início da fila, e retirados na extremidade oposta, chamada final da fila (figura 1). Esta característica é conhecida como FIFO (First In, First Out - Primeiro a Entrar, Primeiro a Sair). Desta forma, o primeiro elemento que foi inserido na fila será o primeiro elemento a ser removido. A estrutura fila pode ser comparada a uma fila de banco. O primeiro cliente que chegou, será o primeiro a ser atendido. Também a fila pode ser implementadas de forma estática, é uma estrutura de dados implementada sobre um vetor de tamanho fixo, definido previamente pelo programador, ou dinâmica, é construída sobre uma lista encadeada, o que significa que sua capacidade pode crescer de acordo com a necessidade do programa, restringida apenas pela memória disponível. 

[[Arquivo:img1-fila.png]]


Figura 1 – Fila


A estrutura de dados fila, como seu próprio nome já sugere, é semelhante ao funcionamento de uma fila de banco. Onde: 1) Se não há ninguém na fila e chega uma pessoa, está será o inicio e o fim da fila; 2) A partir de então, qualquer pessoa que chegar irá para o final da fila (após a pessoa que está no fim); 3) Cada elemento a ser removido será do inicio da fila (O primeiro que chega na fila é o primeiro que sai).

[[Arquivo:img2-fila.png]]

Figura 2 - Fila

[5]

As operações mais comuns efetuadas com filas são:
 
•  Criar: cria uma fila vazia. 

•  Enfileirar: insere um elemento no fim da fila. 

•  Desenfileirar: remover um elemento no início da fila. 

•  Exibir início: exibe o elemento do início da fila. 

•  Exibir a quantidade: retorna a quantidade de elementos da fila. 

•  Esvaziar: esvazia a fila. 

As filas são úteis em diversas aplicações, como por exemplo, os sistemas operacionais, que utilizam filas para gerenciar o escalonamento dos processos que serão executados pelo processador e a alocação de recursos. 
[6]
Uma fila possui elementos característicos, sem os quais torna-se impossível sua manipulação:

- Frente: é a posição que indica o próximo elemento a ser acessado.
 
- Fim: é a posição que indica o próximo elemento a ser inserido.

- Tamanho: é o número máximo de posições permitidas na fila. 

[[Arquivo:img3-fila.png]]


Figura 3 – Elementos Característicos da Fila


Tamanho = 7 Frente = 1 Fim = 4 

Operações:

Temos as operações de inicialização de uma fila, inserção de um elemento e retirada de um elemento.

- Inicialização: dizemos que uma fila F está vazia, quando sua frente e seu fim for igual a zero, ou seja, não existe nenhuma posição da estrutura ocupada por algum elemento. 

- Inserção: podemos inserir elementos até que o fim seja igual ao tamanho. Inserção de elementos além do tamanho da fila, configura-se um caso de overflow,ocorre quando uma operação excede a capacidade de armazenamento de um tipo de dado, resultando em erros inesperados. 

-Remoção: podemos retirar elementos da fila, até que frente seja igual ao fim. Retirada de elementos além desta situação, configura-se um caso de undeflow, se refere a uma condição em que um valor é reduzido abaixo do limite mínimo que pode ser representado por um tipo de dado,levando a comportamentos inesperados no programa. 

[7]
Outras variações de fila:

Fila Circular:
Uma variação da fila simples, mas que reaproveita o espaço do array quando o fim é alcançado, “voltando” para o início. Isso evita o problema de “fila cheia falsa” e permite melhor utilização da memória. É muito usada em sistemas embarcados, buffers de comunicação e estruturas que precisam de alto desempenho contínuo.

[[Arquivo:img4-fila.png]]

Figura 4 – Fila Circular

[8]
Fila Dupla (Deque – Double Ended Queue):
É uma fila onde tanto o início quanto o fim podem receber inserções e remoções. Isso permite funções de fila e de pilha ao mesmo tempo. Usada em algoritmos de busca, navegadores (voltar/avançar), buffers deslizantes e estruturas mais flexíveis de dados.

[[Arquivo:img5- fila.png|500px]]

Figura 5 – Fila Dupla


Pilha (Stack)

A Pilha(Stack) é uma estrutura de dados do tipo LIFO (Last in, First out), ou seja, o último elemento a entrar é o primeiro a sair. Podemos pensar em uma pilha de pratos, o último a ser colocado no topo da pilha é o primeiro a ser pego, é isso que acontece com os elementos da pilha. 

Há duas maneiras de implementar a pilha:

•Locação estatística: as informações são colocadas em um vetor (array) de tamanho fixo e limitado. Esse tipo de locação é rápido e fácil de implementar.

•Locação dinâmica: é feito com uma lista encadeada, enquanto houver memória disponível na máquina, os elementos continuarão sendo empilhados. Esse tipo de locação é um pouco mais complexo.

As principais operações da Pilha são:

•Push: empilhar um elemento 

•Pop: desempilha e retorna o elemento para o usuário 

•Top (peek): informa o elemento que está no topo mas sem desempilhar
 
•Is Empty: informa se a pilha está vazia ou não retornando um booleano

•Is Full: informa se a pilha está cheia, também retorna um booleano
 
•Size: retorna quantos elementos foram armazenados

Em que caso a pilha é usada?

•Navegadores Web - Histórico de páginas (o último app acessado é o primeiro para o qual você vai voltar) 

•A opção de desfazer e refazer (em editores de texto, Photoshop, etc)

•Recursão (o computador cria uma pilha de chamada para as funções)
 
Vantagens:

•Fácil de usar e simples de implementar 

•Perfeito para quando a ordem dos elementos importa
 
•Bom para memória automática 

Desvantagens:

•Normalmente são estruturas pequenas, usadas para armazenar poucos dados.

•Só é possível mexer no topo da pilha, as informações que estão no meio ou no fundo não podem ser acessadas. 

•Se for implementada com vetor pode ocorrer um Overflow.

•Se for implementada com Lista, por causa do uso dos ponteiros, é propenso a dar erros.



Estrutura de dados: árvore

Derivada das árvores genealógicas, essa estrutura abstrata usa hierarquia para organizar dados na computação. Elas possibilitam a implementação de algoritmos de forma não linear e natural. Suas aplicações são variadas, tais quais [1]:
    • Sistemas de arquivos (grande ênfase para distribuições Linux);
    • Bancos de dados

Definição formal [1]:
Formalmente, define-se uma árvore T como um conjunto de nodos que armazenam elementos em relacionamento pai-filho com as seguintes propriedades:
    • Se T não é vazia, ela tem um nodo especial chamado raiz de T, que não tem pai.
    • Cada v de T diferente da raiz tem um único pai, w: todo nodo com pai w é filho de w.

Conceitos e relacionamento entre os elementos [1]:
    • Cada elemento é chamado de nodo;
    • Nodos do mesmo pai são chamado de irmãos;
    • Um nodo é chamado de interno se ele possui filho, mas de externo - ou folha - se não possui filhos;
    • A partir de um nodo u em uma árvore T, podemos ter uma subárvore de T enraizada em u.

Aresta e caminhos [1]: 
    • Uma aresta consiste em dois novos u,v, tais que um deles é pai e o outro filho;
    • Um caminho é uma sequência de nodos, tais que, dois a dois, formam arestas.

Ordenação [1]:
    • Uma árvore é tomada por ordenada se existe uma ordem linear identificável para os filhos de seus nodos.
[[arquivo:Arvore exemplo livro.png]]
Imagem retirada de: Estruturas de dados & algoritmos em Java, MT Goodrich, R Tamassia - 2013.


Estruturas de dados: Tabela hash

A tabela hash também chamada por tabela de (dispersão, indexação e espalhamento), é uma estrutura de dados capaz de armazenar e acessar informações de forma muito rápida. Sua eficiência facilita nas operações como buscar, inserir e retirar de maneira com maior praticidade.

Ela funciona a partir de chaves, que são transformadas em índices por meio de uma função hash. Esses índices apontam para posições de um array, onde os dados são armazenados. [1]

<div style="display:flex; gap:20px;">

[[Arquivo:tabela array.png|thumb|300px|<span style="font-size:20px;">Tabela Array</span>]]

[[Arquivo:tabela hash.png|thumb|600px|<span style="font-size:20px;">Tabela Hash</span>]]

</div>



Um exemplo é quando se tem muitos valores de preços de produtos e é preciso colocar tudo em uma lista, caso precisasse rever algum preço específico seria necessário percorrer vários elementos até encontrar um preço específico, mesmo que a lista estivesse ordenada.

[[Arquivo:lista-1.png|600px]]

Com a tabela hash, a chave é convertida diretamente em um índice, permitindo acessar o valor de forma direta, sem percorrer toda a estrutura. Isso torna a busca muito mais eficiente.

[[Arquivo:lista-2.png|600px]]

Colisões
 
Quando se trabalha com muitas chaves em uma tabela, e com poucas posições(array), as chaves tendem a se entrar em um lugar que se tem uma outra chave localizada. Existem varias maneiras de resolver colisões, más existem duas principais que são utilizadas. 

Encadeamento(Chaining): O array não armazena somente um valor, então podemos utiliza-lo para fazer uma lista e adicionar novos valores em uma única posição, de forma organizada. [2]

[[Arquivo:colisõe 1.png|500px]]

Endereçamento Aberto(Open addressing): Ocorre quando um índice já está ocupado e é preciso encontrar outro índice vazio, essa maneira utiliza varias forma como sondagem linear, quadrática, duplo hashing, etc. [2]

[[Arquivo:colisões 2.png|500px]]

Em condições ideais, as operações em uma tabela hash ocorrem em tempo constante (O(1)), o que é muito mais rápido do que uma busca linear (O(n)). Com a tabela hash a facilidade de localizar algo de forma prática, eficiente e com menos tempo, mesmo que em algum momento haja colisões, existem maneiras de resolver de modo mais simples. Com base nisto as tabelas hash são muito utilizadas, oferecem  mais rapidez e praticidade além de terem um ótimo desempenho.



Pergunta:

1- Qual é a regra básica de funcionamento de uma fila e como ela determina quem é atendido primeiro? 

2- Em um aplicativo para anotar os pedidos dos clientes em um restaurante, os garçons adicionam novos pedidos ao final da fila e os cozinheiros retiram os pedidos do início da fila. Nesse aplicativo é usado um array ou uma lista?

3- Em que caso a operação Is Full pode ser usada, quando a implantação é feita com vetores ou lista encadeada? 

4- Por que pilhas são usadas em chamadas recursivas? 

5- A estrutura de dados do tipo árvore deriva de onde? Qual sua principal característica?

6- Depois que a função de hash transforma a chave em um índice, onde é armazenado este valor?

7- Em uma lista, o que compõe cada nó da estrutura?


Referências:
[1]
@article{ramos2018estrutura,
  title={Estrutura de Dados},
  author={Ramos, Jos{\'e} Marcio Benite and Lacerda, Liluyoud Cury de and Duarte, Sara Luize Oliveira},
  year={2018}
}
[2]
@article{juniorestrutura,
  title={Estrutura de Dados},
  author={Junior, Vilson Heck}
}

[4]

@article{cortes2015estruturadedados,
  title={Estrutura de Dados},
  author={Cort{\'e}s, Mariela In{\'e}s}},
  journal={Editora da Universidade Estadual do Cear{\'a} (EdUECE)},
  year={2015}
}


[5]
@misc{balieiro2015estrutura,
  title={ESTRUTURA DE DADOS.”},
  author={BALIEIRO, RICARDO},
  year={2015},
  publisher={SESES}
}
[6]

@article{bezerra2018introducao,
  title={Introdu{\c{c}}{\~a}o {\`a}s Estruturas de Dados},
  author={Bezerra, C{\'\i}cero Aparecido},
  journal={Universidade Federal do Paran{\'a}},
  year={2018}
}


[7]

@article{lucchesi2004estruturas,
  title={Estruturas de Dados e Tecnicas de Programacao},
  author={Lucchesi, Claudio L and Kowaltowski, Tomasz},
  journal={Instituto de Computa{\c{c}}ao, UNICAMP},
  year={2004}
}


[8]

@article{daestruturas,
  title={Estruturas de Dados},
  author={da Computa{\c{c}}{\~a}o, Curso de Ci{\^e}ncia}
}


[2]
@book{bhargava2017entendendo,
title     = {Entendendo Algoritmos: um guia ilustrado para programadores e outros curiosos},
  author    = {Bhargava, Aditya Y.},
  year      = {2017},
  publisher = {Novatec},
}


@book{cormen2012algoritmos,
  title     = {Algoritmos: teoria e prática},
  author    = {Cormen, Thomas H.},
  year      = {2012}
  publisher = {GEN LTC},
}

@misc{song2008listas,
 title        = {Listas Lineares},
  author       = {Song, Siang Wun},
  year         = {2008},
  publisher    = {IME/USP},
}

Piech, Chris. Arrays. CS106A, Stanford University. Disponível em: 
chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://web.stanford.edu/class/archive/cs/cs106a/cs106a.1184/lectures/15-Arrays/15-Arrays.pdf

Lintzmayer, Carla Negri. Análise de Algoritmos e de Estruturas de Dados.

Bezerra, Cicero Aparecido. Introdução às estruturas de dados.

https://www.alura.com.br/artigos/estruturas-de-dados-introducao

chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://catalogcdns3.ulife.com.br/content-cli/CTI_ESTDAD_19/unidade_3/ebook/EstruturasDados.pdf

UNIVERSIDADE FEDERAL DO PARANÁ. Pilhas e Filas – CI1001. Disponível em: https://www.inf.ufpr.br/gregio/CI1001/PilhaFila.pdf. Acesso em: 10 dez. 2025.

UNIVERSIDADE FEDERAL DE MINAS GERAIS. Estruturas de Dados – Pilha. YouTube, 2020. Disponível em: https://youtu.be/2V91Re1czwA?si=lwVXakxxIXyAv2MT. Acesso em: 9 dez. 2025

PROF. GIORDANO CARMINATI. Pilhas e Filas – Estruturas de Dados. YouTube, 2021. Disponível em: https://youtu.be/tR_Fl4v7FM0?si=F0p9KQOr6xemuuse. Acesso em: 9 dez. 2025.


[1]
 
@book{goodrich2013estruturas,
  title={Estruturas de dados \& algoritmos em Java},
  author={Goodrich, Michael T and Tamassia, Roberto},
  year={2013},
  publisher={Bookman Editora}
}

[1]
@article{pimenteltabelas,
  title={Tabelas hash},
  author={Pimentel, Renato}
}

[2]
@article{barros2020acelerando,
  title={Acelerando a constru{\c{c}}{\~a}o de tabelas hash para dados textuais com aplica{\c{c}}{\~o}es},
  author={Barros, Chayner Cordeiro},
  year={2020}
}