Filas

Afluentes:

• Estrutura de Dados
• DAS5102 Fundamentos da Estrutura da Informação

Vídeoaulas

• Filas - Analisando Visualmente
• Filas - Implementando em Java

Introdução

A Fila é uma estrutura de dados que modela as filas que existem comumente nas mais diversas situações do mundo real. Essencialmente em uma fila o elementos são inseridos em série um atrás do outro. Um certo nó sempre é inserido atrás dos nós já existentes na fila, e quando a remoção de um nó da fila é requerida, o nó mais antigo inserido, ou seja, o primeiro elemento da fila é removido.

Operações básicas:

• criar uma fila vazia;
• inserir um novo elemento;
• retirar o nó da cabeça da fila;
• verificar qual é o nó na cabeça da fila;
• verificar se a fila está vazia;
• verificar o número de nós na fila.

Uma fila nada mais é do que uma lista encadeada (veremos depois) onde as regras de inserção e remoção são bem estipuladas. Nós são sempre inseridos no início da lista e removidos da cabeça da lista.

1public class No {
2	Object info;
3	No proximo;
4}

1public class Fila {
2    No inicio;
3    No cabeca;
4    int tamanho;
5}

É possível implementarmos uma fila usando listas encadeadas simples. Ao definir esta estrutura como base para a implementação de filas, a inserção de novos elementos é simples:

novo_no->prox = inicio; 
inicio = novo_no; 
tamanho++. 

A remoção de um no da fila é problemática. Devemos percorrer todos os nós da lista a partir de seu início até encontrarmos o nó que aponta para NULL, ou seja o nó a ser retirado. Ainda, devemos manter uma referência para o nó anterior durante a busca pelo último nó. Assim que o último nó é encontrado, devemos fazer com que cabeça aponte para o nó anterior, fazer com que o nó anterior aponte para NULL e retornar o nó previamente apontado por cabeça. Como podemos ver essa é uma implementação bem pouco eficaz. Imagine o caso em que existam centenas de milhares de elementos em uma lista!

Também é possível implementar filas usando listas duplamente encadeadas. Tente identificar a vantagem em se utilizar listas duplamente encadeadas ao invés de listas encadeadas simples. Mais a frente falaremos sobre listas duplamente encadeadas e podemos voltar aqui para reanalizar o problema.

Da mesma forma que podemos implementar uma pilha usando arrays, podemos também implementar filas. No entanto a implementação pode ser pouco eficiente. Tente implementar uma fila em arrays e liste os problemas encontrados.

Exercícios

1. Considere a representação pictográfica de uma estrutura de fila dinâmica dada abaixo:

Explique o problema em se utilizar esta estrutura. É possível implementar uma fila usando este modelo? Justifique.

2. Proponha uma maneira mais eficiente de implementar filas usando listas encadeadas simples (dica, use um ponteiro adicional)

Roteiro

Objetivos

Revisar os conceitos de filas vistos em sala de aula.

Descrição

Crie uma Estrutura (Classe) que implemente uma Fila.

• Dados do tipo double devem ser acomodados como elementos da lista;
• Crie Funções para:
  • criar uma fila vazia;
  • inserir um novo elemento;
  • retirar o elemento da cabeça da fila;
  • verificar qual é o elemento na cabeça da fila;
  • verificar se a fila está vazia;
  • verificar o número de elementos na fila.