Estrutura de dados - Fila

1 Filas

Estrutura de dados bastante usada em computação é a fila. Na estrutura de fila, os acessos aos elementos também seguem uma regra. O que diferencia a fila da pilha é a ordem de saída dos elementos: enquanto na pilha “o último que entra é o primeiro que sai”, na fila “o primeiro que entra é o primeiro que sai” (a sigla FIFO – first in, first out – é usada para descrever essa estratégia). A idéia fundamental da fila é que só podemos inserir um novo elemento no final da fila e só podemos retirar o elemento do início.
A estrutura de fila é uma analogia natural com o conceito de fila que usamos no nosso dia a dia: quem primeiro entra numa fila é o primeiro a ser atendido (a sair da fila). Um exemplo de utilização em computação é a implementação de uma fila de impressão. Se uma impressora é compartilhada por várias máquinas, deve-se adotar uma estratégia para determinar que documento será impresso primeiro. A estratégia mais simples é tratar todas as requisições com a mesma prioridade e imprimir os documentos na ordem em que foram submetidos – o primeiro submetido é o primeiro a ser impresso.

As filas podem usar vetores estáticos para armazenar os dados, mas como pode ser constatado na figura acima, se formos inserindo e retirando dados de um vetor estático, podemos rapidamente alcançar o “topo” deste vetor. Uma solução para este problema é a criação das chamadas FILAS CIRCULARES.

1.1 Operações básicas:
Criação
Destruição
Inserção de um elemento
Remoção de um elemento
Localização de um elemento para consulta ou alteração
Ordenação de uma lista
Intercalação de duas listas
Concatenação de duas listas
Divisão de uma lista em duas

1.2 Implementação de fila com vetor

Como no caso da pilha, nossa primeira implementação de fila será feita usando um vetor para armazenar os elementos. Para isso, devemos fixar o número máximo N de elementos na fila. Podemos observar que o processo de inserção e remoção em extremidades opostas fará com