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
|
Nenhum comentário:
Postar um comentário