FILAS (Queues)
-Estrutura linear de acesso seqüencial que ordena seus
elementos pela seqüência cronológica de sua entrada;
-Estrutura FIFO (First In First Out) a ordem de saída é a
mesma ordem de entrada (o 1o a chegar será o 1o a sair da
fila);
-Diferentemente da pilha uma fila pode ser manipulada pelas
duas extremidades, conhecidas como inicio e fim (ou frente e
cauda, etc);
- Restrições quanto à manipulação: inserções sempre no final,
remoções sempre do início da fila;
FILA ESTÁTICA (SOBRE UM VETOR) C/ DESCRITOR
1) Sem compactação
typedef struct {
void **vetFila;
int comprimentoDoVetor;
int tamInfo; /* tamanho da informação */
int inicio;
/*indexa o início da fila */
int fim;
/*indexa o final da fila */
} Fila;
Inserções incrementam o FIM, remoções incrementam o INICIO
(INICIO e FIM variando);
a) Inicialização: FIM = -1, INICIO = 0;
b) Tamanho da Fila = FIM – INICIO + 1;
c) Fila vazia : FIM < INICIO;
inicio fim
a)
b)
0
0
-1
-1
c)
d)
e)
f)
g)
h)
...
)
0
0
0
1
2
3
...
2
0
1
2
2
2
2
...
3
vetFila[ 4 ]
0 1 2 3
X0
X0 X1
X0 X1 X2
X1 X2
X2
...
...
... ...
Y m Yn
Interpretação
fila recém criada
tentativa de
remoção  ERRO:
fila vazia
inseriu X0
inseriu X1
inseriu X2
removeu
removeu
removeu
...
tentativa de
inserção  ERRO
(?!?!): fila cheia ???
2) Compactando a Fila — Movimentação de Dados
A cada remoção move-se toda a fila na direção do seu inicio de
forma a preencher o espaço deixado pela remoção:
for (i=0; i < tamanhoFila; i++)
memcpy(p->vetFila[i],p->vetFila[i+1],p->tamInfo);
p->final -= p->inicio;
p->inicio = 0;
Portanto: As inserções incrementam o FIM mas o INICIO fica
fixo no início do vetor (zero);
a) Tamanho da fila  FIM - INICIO + 1 = FIM - 0 +1 =
FIM+1;
b) Inicialização: FIM = -1, INICIO = 0;
c) Fila vazia : FIM < INICIO;
d) Fila cheia : FIM = comprimentoDoVetor - 1
inicio fim
0
a)
b)
c)
d)
e)
f)
g)
h)
i)
vetFila[4]
1
2
3
0
0
0
0
-1
0
1
2
2
X0
X0
X0
0
1
X1
X2
0
0
2
2
X1
X2
X2
0
1
X2
X3
0
0
2
3
X2
X2
X3
X3
X1
X1
X1
X2
X2
X3
X3
X4
X4
X5
Interpretação
fila recém criada
inseriu X0
inseriu X1
inseriu X2
removeu e
compactou
(moveu fila à
esquerda)
inseriu X3
removeu e
compactou
(moveu fila à
esquerda)
inseriu X4
inseriu X5 
fila realmente
cheia !!!!!!
3) Solução híbrida - Compactando na hora certa
INICIO variável, como feito na alternativa 1, aliado à compactação
como em 2.
Ao invés da compactação ocorrer a cada remoção, o critério para
realiza-la seria detectar um falso sinal de “fila cheia”:
inserção( )
/* fila cheia fim== comprimentoDoVetor-1 */
Se (fila cheia)
/* tamanhoDaFila = FIM - INICIO + 1 */
Se(tamanhoDaFila < comprimentoDoVetor)
for(i=0; i < tamanhoDaFila; i++)
memcpy(p->vetFila[i],p>vetFila[i+inicio],p->tamInfo);
p->final -= p->inicio;
p->inicio = 0;
inserção no final da fila;
Senão
FILA realmente cheia;
inicio fim
0
a)
b)
0
0
-1
-1
c)
d)
e)
f)
0
0
0
0
1
2
2
0
0
0
1
2
3
3
3
3
1
1
g)
h)
i)
X0
X0
X0
X0
X2
X2
vetFila[4]
1
2
3
X1
X1
X1
X1
X3
X3
X2
X2
X2
X2
X2
X4
X3
X3
X3
X3
Interpretação
fila recém criada
remoção 
ERRO: fila vazia
inseriu X0
inseriu X1
inseriu X2
inseriu X3
removeu
removeu
inserção X4:
compactou e
insere
Independentemente da opção 2 ou 3, a
compactação da Fila pode ser uma operação
bastante lenta.
Se a estrutura possuir N posições e a
fila de dados possuir N-1 elementos,
serão necessárias N-2 movimentos,
dos N-2 elementos desde o final da
fila.
4) Fila Circular
Considera o vetor como um arranjo circular, como se o
seu final se ligasse ao seu início, não havendo
interrupção.
Na implementação sobre um vetor (ESTÁTICA) a fila
circular torna-se bastante vantajosa, pois viabiliza a
reutilização das posições desocupadas sem a
necessidade de movimentação de dados.
CONSEQÜÊNCIA:
FIM < INICIO NÃO MAIS IMPLICA EM FILA VAZIA
inicio fim
2
5
2
0
vetFila[ 6 ]
0 1 2 ... 5
.... .... X0 ... X3
operação
Interpretação
.....
......
J)
K)
J)
X4 .... X0 ... X3 insere X4 fim < inicio fila Não
em modo
vazia
Fila circular
K)
Aqui consideraremos que a partir do INICIO alcança-se o FIM
explorando a fila no sentido horário: X0,X1,X2,X3,X4
E agora...
Se FIM < INICIO não mais implica em fila VAZIA !
Como testar tal condição ?
Acrescentando-se um campo tamanhoDaFila à
estrutura interna do TDA fila, o qual serviria como
parâmetro para definir se o estado da fila é vazia ou
cheio independentemente de INICIO e FIM.
a) Inicialização: FIM = -1, INICIO = 0;
b)Tamanho da fila  dado explicito na estrutura;
c) Fila vazia : tamanho da fila = 0;
d) Fila cheia : tamanho da fila = comprimentoDoVetor
Estrutura Fila Circular Estática:
typedef struct {
void **vetFila;
int comprimentoDoVetor;
int tamInfo;
int inicio; /* indexa o início da Fila */
int fim; /*indexa o final da Fila */
int tamanhoDaFila; /* testes de vazia/cheia */
} Fila;
inicio
fim tamanho
0
a)
b)
c)
d)
e)
f)
g)
h)
i)
j)
k)
0
0
0
0
1
1
2
3
3
3
3
-1
0
1
2
2
3
3
0
1
2
2
0
1
2
3
2
3
2
1
2
4
4
l)
m)
n)
o)
0
1
2
3
2
2
2
2
3
2
1
0
X0
X0
X0
X4
X4
X4
X4
X4
vetFila[ 4 ]
1
2
3
X1
X1
X1
X1
X5
X5
X5
X5
X5
X2
X2
X2
X2
X6
X6
X6
X6
X6
X3
X3
X3
X3
X3
X3
Interpretação
fila recém criada
inseriu X0
inseriu X1
inseriu X2
removeu
inseriu X3
removeu
inseriu X4
inseriu X5
inseriu X6
inserção X7 
ERRO: fila CHEIA
removeu
removeu
removeu
removeu:
tamanho = 0 
fila VAZIA !!!
inserção( )
SE (tamanho atual da fila < tamanho do vetor)
/* há espaço no início do vetor */
SE (FIM = = tamanho do vetor-1)
/* utilize o aspecto circular */
FIM = 0;
memcpy(p->vetFila[FIM],novo,p->tamInfo);
SENÃO
memcpy(p->vetFIla[++FIM],novo,p->tamInfo);
tamanho atual da fila ++
SENÃO
fila realmente cheia!!
Alternativa p/ controle da “circularidade”:
Sentido da
circulação
SE (FIM == tamanhoDovetor - 1)
FIM = (FIM+1)%tamanho do vetor
vetor[FIM] = novo
tamanho atual da fila ++
Remoção( )
SE(tamanho da fila = = 0)
fila vazia
SENÃO
SE (INICIO = = tamanho do vetor)
INICIO = 0
SENÃO
INICIO++
tamanho da fila - Alternativa p/ controle da “circularidade”:
SENÃO
Sentido da
circulação
INICIO = (INICIO+1)%tamanho do vetor
tamanhoDaFila - -
(Outra alternativa para gerenciar inicio/fim na fila circular)
b) Abrir mão de um espaço na fila fazendo INICIO ser
sempre uma posição antes do inicio real da Fila, então:
se INICIO = = FIM => fila vazia como em (a);
se (FIM+1) = = INICIO => fila cheia como em (m);
inicio fim
a)
b)
0
0
-1
-1
c)
d)
e)
f)
g)
h)
i)
j)
k)
m)
0
0
0
1
1
2
3
3
3
3
0
1
2
2
3
3
3
0
1
1
vetFila[TAM], TAM
== 4
0
1
2
3
X0
X0
X0
X4
X4
X4
X1
X1
X1
X1
X5
X5
X2
X2
X2
X2
X3
X3
X3
X3
X3
X3
Observações
fila recém criada
tentou
uma
remoção => ERRO:
fila vazia
inseriu X0
inseriu X1
inseriu X2
remoção
inseriu X3
remoção
remoção
inseriu X4
inseriu X6
tentou a inserção
X6 => ERRO: fila
cheia
inserção e remoção para Fila Circular como em (B):
remocao( )
insercao( )
if (FIM= =INICIO)
if(FIM == MAX-1)
erro fila vazia
FIM = 0;
else
else
if( INICIO= = MAX-1)
FIM++;
INICO = 0;
if ((FIM +1) = = INICIO)
else
erro fila cheia
INICIO++;
else
memcpy(fila[FIM],novo,tamInfo);