Fila Circular

Em sua forma mais simples a fila é uma estrutura de dados fácil de programar, entretanto, percebe-se rapidamente que a aparente simplicidade esconde algumas complicações.

 Como a questão da representação na memória, pode-se representar a fila como um vetor ou uma lista encadeada, no primeiro caso um problema singular ocorre, se você continua adicionando elementos no fim da fila e eliminando os do inicio, os dados da fila percorrera toda a memória.

Quando se usa vetores para implementar filas, podemos contornar este problema transformando em um vetor circular, de forma que ao acessar o ultimo elemento do vetor, continua-se a partir do primeiro, obtendo assim a fila circular, resultando na situação abaixo:

Legenda
	inicio
	fim

insert(A);

A

insert(B);

A

B

insert(C);

A

B

C

x = remove();

B

C

insert(D);

B

C

D

insert(E);

B

C

D

E

y = remove();

C

D

E

insert(F);

F

C

D

E

O código modifica o exemplo anterior para incluir o suporte ao buffer circular, a necessidade de indicar o status de fila cheia, as variáveis que apontam para o inicio e fim, podem apontar para a mesma posição do vetor em duas situações, quando a fila está vazia ou cheia:

Status = livre

inicio
fim

Status = cheia

			inicio
F	G	H	D	E
			fim

O tipo de dados abstrato fila inclui agora o status da fila

#define SIZE_QUEUE      8 #define FREE            0 #define FULL            1 typedef struct tagSQUEUE {       char  cBuf[SIZE_QUEUE];       int   iIni;       int   iEnd;       char  cSts; } SQUEUE;

Para a rotina que insere elementos na fila:

1.       Apenas irá armazenar se não estiver cheia.

2.       Após inserir o dado, verifica se o índice de fim passou o limite do vetor, sendo o caso reinicia o contador.

3.       Ultima verificação é para ver se o índice de fim alcançou o inicio o que caracteriza como fila cheia.

void insertQ(SQUEUE *sPtr, int iVal) {       if (sPtr->cSts == FULL)             return;       sPtr->cBuf[sPtr->iEnd++] = iVal;       if (sPtr->iEnd >= SIZE_QUEUE)             sPtr->iEnd = 0;       if (sPtr->iEnd == sPtr->iIni)             sPtr->cSts = FULL;  }

Para remover elementos da fila:

1.       Verificamos se a fila está vazia ao analisar os indicadores de posição do inicio e fim em conjunto do status.

2.       Como feito anteriormente na rotina insere com o valor da posição final, certificamos que o valor da posição inicial não ultrapassou o limite do vetor, reiniciando a posição caso tenha alcançado o fim.

3.       Sempre que um elemento é retirado significa que existe espaço livre na fila, atualiza o valor de status.

int removeQ(SQUEUE *sPtr) {       int iTmp;       if (sPtr->iEnd == sPtr->iIni && sPtr->cSts == FREE)             return -1;       iTmp = sPtr->cBuf[sPtr->iIni++];       if (sPtr->iIni >= SIZE_QUEUE)             sPtr->iIni = 0;       sPtr->cSts = FREE;       return iTmp;   }

                O código abaixo repete o do ultimo exemplo, incluída uma pequena alteração nas rotinas abaixo para aperfeiçoar valendo-se do fato que o tamanho da fila permite operações de mascara de bit.

Decimal		Binário
iIni	iIni & 7	iIni	iIni & 7
6	6	0110	110
7	7	0111	111
8	0	1000	000

                Ao rodar o programa, o resultado será:

C:\Projects\CircQueue\Debug>CIRCQUEUE         A         A       B                 B QUEUE EMPTY                         C                         C       D                         C       D       E                         C       D       E       F                         C       D       E       F       G                         C       D       E       F       G       H         I               C       D       E       F       G       H         I       J       C       D       E       F       G       H QUEUE FULL         I       J       C       D       E       F       G       H