Filas
#define MAXFILA 100
typedef struct queue {
int item [ MAXFILA];
int inic, fim;
} fila;
fila q;
Operações sobre uma
fila.
q.item
4
3
2
1
q.inic = 0
0
q.fim = -1
(a)




No momento (a) a fila está vazia
q.inic=o e q.fim = -1
Quantidade de elementos = q.fim –q.inic+1
Ou seja: -1-0+1=0
q.item
4
3
2
1
0
30
q.fim = 2
20
10
q.inic = 0
(b)
No momento (b)



No momento (b) houve a inclusão de 3
elementos - 10, 20 e 30
Quantidade de elementos = q.fim –q.inic+1
Ou seja: 2 – 0 + 1 = 3
q.item
4
3
2
30
q.inic = q.fim =2
1
0
(c)





No momento (c) houve a remoção dos
elementos 10 e 20
q.fim = q.inic
30 é o primeiro e o último elemento
Quantidade de elementos = q.fim –q.inic+1
Ou seja: 2 – 2 + 1 = 1
q.item
50
q.fim = 4
4
3
2
40
30
q.inic = 2
1
0
(d)
No momento (d) existem 4 -2 + 1 =3
 Não é possível inserir outros elementos,
pois o elemento 50 ocupa a última posição do
vetor
 Existem 2 posições livres
 Para deslocar os elementos no vetor exige
grande esforço computacional
X=q.item[0];
For (k=0;k< q.fim; k++)
q.item[k]=q.item[k+1];
q.Fim --;

Fila circular
q.item
50
q.fim = 4
4
40
3
30
q.inic = 2
2
1
0
(a)
q.item
50
4
40
3
2
30
q.inic = 2
1
0
60
q.fim = 0
(b)
q.item
50
q.inic = 4
4
3
2
1
0
60
q.fim = 0
(c)
q.item
50
q.inic = 4
70
q.fim = 1
4
3
2
1
0
60
(d)
q.item
4
3
2
1
0
70
q.fim = 1
60
q.inic = 0
(e)
Como verificar se a fila está
vazia



q.inic é o índice do vetor que é exatamente
anterior ao primeiro elemento da fila
q.fim é o índice do último elemento da fila
Se q.inic=q.fim, temos uma fila vazia
Ilustração da
operação da inserção
na fila
q.item
50
q.fim = 4
4
40
3
30
q.inic = 1
2
1
0
(a)
q.item
50
4
40
3
2
30
1
q.inic = 1
0
60
q.fim = 0
(b)
q.item
50
4
40
3
2
30
1
70
0
q.inic = q.fim = 1
60
(c)
#define MAXFILA 100
typedef struct queue {
int item [ MAXFILA];
int inic, fim;
} fila ;
Main ()
fila q;
void inicFila (fila *pq)
{
pq→inic = MAXFILA -1;
pq→fim = MAX FILA -1;
}
int filaVazia (fila *pq)
{
if(pq →inic==pq →fim)
return (1) ; /*1 é verdadeiro* /
else
return (0) ; / *0 é falso*/
) /* fim filaVazia*/
if (filaVazia (&q)==1)
/* tratamento adequado quando a fila está vazia
*/
else
/* tratamento adequado quando a fila não está vazia
*/
int remFila(fila*pq)
{
if(filaVazia (pq) )
{
printf(“Underflow na fila!\n”);
exit ( 1) ;
}
If (pq → inic = = MAXFILA -1 )
pq → inic = 0;
else
( pq →inic) ++;
return (pq → item [ pq → inic] ) ;
} /*fim remove */
void insFila ( fila *pq, int x)
{
/*realiza a movimentação para abrir espaço para novo elemento */
if (pq → fim = = MAXFILA – 1)
pq → fim = 0 ;
else
(pq → fim ) ++ ;
/*verifica ocorrência de estouro */
if (pq → fim = = pq → inic) {
printf (“Ocorreu overflow na fila!\n”);
exit ( 1 ) ;
}
pq → item [ pq → fim] = x;
}