Estrutura de Dados

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.

[IMAGEM]

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.

[IMAGEM]

Tipos de Listas

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

[IMAGEM]

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.

[IMAGEM]

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

[IMAGEM]

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

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.

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).

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.

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.

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.

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.

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.

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?

Referências:

BEZERRA, Cícero Aparecido. Introdução às estruturas de dados. Curitiba: UFPR, 2018. Disponível em: https://acervodigital.ufpr.br/xmlui/bitstream/handle/1884/55879/introducaoEstruturaDados.pdf?sequence=1&isAllowed=y. Acesso em: 07 dez. 2025.

BALIEIRO, Ricardo. Estrutura de dados. 1. ed. Rio de Janeiro: SESES, 2015. 176 p. Disponível em: https://hood.com.br/new/filegator/repository/Estrutura%20de%20Dados/10%20Livro%20Estrutura%20de%20Dados.pdf. Acesso em: 07 dez. 2025

CORTÉS, Mariela Inés. Estrutura de Dados. 3. ed. Fortaleza, CE: EdUECE, 2015. Disponível em: https://www.uece.br/cct/wp-content/uploads/sites/28/2021/07/Estrutura-de-Dados-2014.pdf. Acesso em: 07 dez. 2025.

UNIOESTE. Aulas Estruturas de Dados. Cascavel: Universidade Estadual do Oeste do Paraná, 2019. Disponível em: https://www.inf.unioeste.br/~adair/ED/Notas%20de%20Aula/Aulas%20Estruturas%20de%20Dados.pdf. Acesso em: 07 dez. 2025.

LUCCHESI, Cláudio L.; KOWALTOWSKI, Tomasz. Estruturas de Dados e Técnicas de Programação. Versão 1.12. Campinas: Instituto de Computação – UNICAMP, 2004. Disponível em: https://www.ic.unicamp.br/~mc202abcd/ln_tkcll.pdf. Acesso em: 07 dez. 2025.

BHARGAVA, A. Y. Entendendo Algoritmos: um guia ilustrado para programadores e outros curiosos. Novatec, 2017.

‌CORMEN, Thomas H. et al. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: GENLTC, 2012.

SIQUEIRA, Fernando De. 14-Listas. ALGORITMOS E ESTRUTURAS DE DADOS AVANÇADOS. Disponível em:https://sites.google.com/site/proffdesiqqueiraalgeedavanc/aulas/14-listas

SONG, Siang Wun. Listas Lineares. São Paulo: IME/USP, 2008. Disponível em: https://www.ime.usp.br/~song/mac5710/slides/02linear.pdf