Filas
 São utilizadas em aplicações onde são impostos
critérios para a inserção e retirada de elementos cuja
ordem não depende da ordem natural dos valores dos
dados.
FIFO “first in first out”: o primeiro elemento a ser
retirado é o primeiro que tiver sido inserido, ex.:
fila de banco.
Filas
 As filas exigem acesso às duas extremidades do vetor:
a) começo - onde é feita a retirada; e
b) fim - onde é feita a inserção.
 Definição de filas - forma geral:
tipo
fila_vet :: reg (comeco:int; termino:int;
elementos: vet [1..10] de dado);
var
f: fila_vet;
i,j: dado;
Operações básicas
 Inicialização
f.comeco <- 1;
f.termino <- 0;
 Inserção
Se f.termino =10 entao erro {excesso de elementos}
Senao inicio
f.termino <- f.termino + 1;
f.elementos[f.termino] <- i;
fim;
Definindo e inicializando filas
Operações básicas
 Retirada:
Se f.termino < f.comeco
entao nada
{ fila vazia }
Senao
f.comeco <- f.comeco + 1;
 Consulta ao elemento no começo da fila
Se f.termino < f.comeco entao erro {fila vazia}
Senao
j <- f.elementos[f.comeco];
Operações básicas Fila Simples
Tipo
fila_vet :: reg (comeco:int; termino:int;
elementos: vet [1..10] de dado);
var
f: fila_vet;
i,j: dado;
//Inicialização
f.comeco <- 1;
f.termino <- 0;
//Inserção
Se f.termino =10 entao erro {excesso de elementos}
Senao inicio
f.termino <- f.termino + 1;
f.elementos[f.termino] <- i;
fim;
//Retirada:
Se f.termino < f.comeco
entao nada
{ fila vazia }
Senao
f.comeco <- f.comeco + 1;
//Consulta ao elemento no começo da fila
Se f.termino < f.comeco entao erro {fila vazia}
Senao
j <- f.elementos[f.comeco];
Representação na memória
 Após a inicialização, a fila vazia tem o seguinte
aspecto:
 A atribuição do valor 1 inicial a f.comeco é para
garantir que f.termino < f.comeco notando que se
f.comeco = f.termino não indica fila vazia e sim uma
fila com somente um elemento. A inserção dos
elementos: 26,18,12,9,3,11,4,2,13 faz:
Representando na memória
 Havendo 4 retiradas da fila temos:
Como a retirada envolve o incremento de f.comeco nota-se
que a fila vai se deslocando da esquerda para a direita do
vetor.
 Para inserir mais um elemento (17, por exemplo) soma-se 1
a f.termino, o qual passa a conter o índice 10, posição em
que colocamos o valor 17. Se agora quisermos inserir mais
um valor, isso não será possível (f.termino = 10 indica erro
se for tentada uma inserção) o que de certo modo é
absurdo, já que as posições 1 a 4 estão livres
Resolvendo inconsistências
 Para permitir a reutilização de posições já ocupadas,
inserimos mais um componente “f.tamanho” que
indica quantos elementos existem na fila no
momento. Portanto as operações serão executadas
conforme os algoritmos:
 Inicialização:
f.comeco <- 1;
f.termino <- 0;
f.tamanho <- 0;
Resolvendo inconsistências
 Inserção:
Se f.tamanho = 10 entao erro {excesso de elementos}
Senao inicio
f.tamanho <- f.tamanho + 1;
f.termino <- (f.termino mod 10) + 1;
f.elementos[f.termino] <- i;
fim;
Antes de incrementar f.termino tomamos o resto de sua
divisão pelo n° de elementos do vetor, ex.: para inserir
mais um elemento, f.termino será calculado por
10 mod
10 + 1 e o novo elemento será inserido na primeira posição
do vetor.
Resolvendo inconsistências
 Retirada:
Se f.tamanho = 0 entao nada {fila vazia}
Senão inicio
f.tamanho <- f.tamanho - 1;
f.comeco <- (f.comeco mod 10) + 1;
fim;
 Consulta:
Se f.tamanho = 0 entao erro {fila vazia}
Senao
j <- f.elementos[f.comeco];
Operações básicas Fila Circular
Tipo
fila_vet :: reg (comeco:int; termino:int;
elementos: vet [1..10] de dado);
var
f: fila_vet;
/* Inicialização: */
i,j: dado;
f.comeco <- 1;
f.termino <- 0;
/* Inserção:
*/
Se f.tamanho = 10 entao erro {excesso de elementos}
Senao inicio
f.tamanho <- f.tamanho + 1;
f.termino <- (f.termino mod 10) + 1;
f.elementos[f.termino] <- i;
fim;
/* Retirada:
*/
Se f.tamanho = 0 entao nada {fila vazia}
Senão inicio
f.tamanho <- f.tamanho - 1;
f.comeco <- (f.comeco mod 10) + 1;
fim;
/* Consulta:
*/
Se f.tamanho = 0 entao erro {fila vazia}
Senão
j <- f.elementos[f.comeco];