Fila circular

Assunto: Lista Circular

“Dobrar” o vetor de forma que as suas extremidades se encontrem

Vamos modificar a implementação das operações e da estrutura utilizada para representar uma fila utilizando uma organização circular (conforme os conceitos discutidos até então);

Observe a seguinte situação (considerando uma fila normal, de tamanho N implementada sobre um vetor):
– São inseridos N elementos na fila;
– Em seguida são retirados n-2 elementos;
– Tenta-se incluir mais um elemento;

O que acontece?
– A fila acusará fila cheia! Mas há espaço no vetor!
– Isso é um problema da regra que define a fila? Não!
– O problema decorre da forma utilizada para representar a fila: o VETOR;

Antes de mais nada, uma fila circular é uma fila e portanto suas operações acontecem da seguinte forma:
– Inclusões: no final da fila;
– Retiradas: no início da fila;
– A diferença está na forma de tratar a organização física da fila. A interface é a mesma da fila tradicional.

Definição Conceitual

Precisamos controlar o tamanho da Fila de outra forma !!

Funcionamento

• As condições “fila cheia” e “fila vazia” também devem ser alteradas:
• Uma fila está cheia se o campo que foi adicionado para controlar o tamanho for igual ao tamanho do vetor;
• Uma fila está vazia se o tamanho for igual a zero;

Observa-se que na fila com incremento circular a parte ocupada do vetor pode chegar a última posição.

Implementação:

• Para reaproveitar as primeiras posições livres do vetor podemos incrementar o vetor de forma “circular”.
• Se o último elemento da fila ocupa a última posição do vetor, inserimos os novos elementos a partir do início do vetor.

Se modificarmos a organização física da fila e a implementação de suas operações o problema pode ser resolvido.
Vamos imaginar um “vetor dobrado” de forma que o fim do vetor se encontre com o início.

Arquivo “FilaCircular.h”

#define MAX 5

typedef struct { int inicio; int