Estrutura De Dados - Filas

Filas

FIFO = “First In, First Out”

As estruturas de dados podem ser organizadas de formas diferente e especiais, de acordo com a maneira com que os dados são inseridos e retirados. Um tipo particular de estrutura de dados, é a FILA, onde a inserção ocorre sempre no final da fila (final do vetor) e a retirada dos dados ocorre do início da fila (inicio do vetor). Esta noção de início/fim do vetor pode ser um pouco particular se considerarmos que usualmente as filas serão implementadas em uma estrutura de dados chamada “fila circular”, que descreveremos a seguir. Este tipo de estrutura de dados, as filas podem “similar” uma fila de pessoas (do mundo real), sendo também muito usada em diversos tipos de aplicações computacionais, onde é importante “preservar” a ordem de chegada e de atendimento como por exemplo, uma fila de impressão (nem todas filas são realmente filas, pois algumas permitem remover elementos do meio da fila, o que estaria fora do padrão), uma fila de dados a tratar, etc. Nas filas o primeiro dado a entrar nela é sempre o primeiro dado a sair (FIFO).

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.

Uma FILA CIRCULAR é uma estrutura de dados que simula de modo virtual uma fila onde o início e o fim do vetor são unidos. A figura abaixo demonstra um exemplo de como poderia ser visualizada uma fila circular usando um vetor de 10 elementos:

Portanto, em uma FILA CIRCULAR o elemento seguinte ao último elemento do vetor é virtualmente o primeiro elemento deste vetor, assim como, o elemento vizinho e anterior ao primeiro elemento deste vetor passa a ser o último elemento do vetor. Com isto, não teremos mais problema relativos ao deslocamento do início da fila que ocorre quando os elementos são retirados da fila. Podemos visualizar este comportamento da seguinte forma: à medida que o final da fila vai “subindo” no vetor em direção aos elementos de índice maior através da inserção de novos elementos, o início também irá “subindo” no vetor em direção os elementos de índice maior, “perseguindo” o final da fila. Se o final da fila alcançar o último elemento do vetor, e se o início do vetor não estiver mais ocupado, “damos a volta” e começamos a ocupar novamente o vetor a partir de seu início.

O uso de uma fila circular vai também implicar na necessidade de diferenciar entre fila completamente vazia (que pode ser vista como início da fila junto ao final da fila => início=fim) e fila completamente cheia (onde o final da fila “dá a volta” e alcança o início da fila => início=fim). Para resolver este problema devemos usar algum tipo de marcação que diferencie fila vazia de fila cheia: (a) usar um flag para sinalizar fila cheia, (b) manter atualizado um contador do número de elementos inseridos da fila, ou, (c) não permitir que o início “encoste” no final, deixando sempre uma posição do vetor livre (não ocupada).

Vamos definir a seguir um conjunto de rotinas genéricas para manipulação