Filas
Estrutura de Dados
Marco Antonio Montebello Júnior
[email protected]
Listas Lineares
Listas Lineares
Pilha
Fila
Entrada restrita
Estrutura de Dados
Fila Dupla
Saída restrita
Fila versus Pilha
SAÍDA
FIM
SAÍDA
ENTRADA
Elemento 2
TOPO
Elemento 2
Elemento 1
Elemento 2
Elemento 1
ENTRADA
INÍCIO
Estrutura de Dados
BASE
Filas

Operações primitivas que manipulam as filas:
InicializaFila (q) ou init(q)
Faz a fila q ficar vazia
FilaVazia(q) ou empty(q)
Retorna V se a fila q está vazia
FilaCheia(q) ou full(q)
Retorna V se a fila q está cheia
InsereFila(q,x) ou insert(q,x)
Insere o elemento x no final da fila q
Remove o PRIMEIRO elemento da fila,
RemoveFila(q) ou remove(q) retornando o conteúdo do elemento
como valor da função
Estrutura de Dados
Filas

Representando filas em Linguagem C:




Podemos utilizar vetor
Apoio de 2 variáveis: inic e fim
inic – Primeiro elemento da fila
fim – Último elemento da fila
#define MAXQUEUE 100
struct queue {
int item[MAXQUEUE];
int inic, fim;
};
struct queue q;
Estrutura de Dados
Filas






Ignorando momentaneamente a possibilidade de
overflow e underflow:
Operação InsereFila(q, x):
q.item [++ q.fim] = x
Operação RemoveFila(q):
x = q.item [q.inic ++];
No momento que a fila é criada, q.fim é definido como –1 e q.inic como 0
A fila está vazia sempre que q.fim < q.inic
Número de elementos na fila é sempre igual ao valor de q.fim - q.inic + 1
Estrutura de Dados
Filas – Problema Clássico

Problema clássico da fila vazia sem possibilidade de
inserir novos elementos:
q.item
q.item
q.item
q.item
4
E
3
D
2
C
1
B
0
q.inic = 0
q.fim = -1
A
q.fim=2
C
q.inic=0
Estrutura de Dados
q.inic=
q.fim=2
C
q.fim =4
q.inic =2
Filas – Solução 1

Remanejar todos os elementos quando remover um
elemento:
RemoveFila(q);
x = q.item [ 0 ];
for (i = 0; i < q.fim; i++)
q.item[ i ] = q.item[ i + 1 ];
q.fim --;



O campo q.inic não é necessário porque o elemento na posição 0 do vetor está sempre no
início da fila. A fila vazia é representada por q.fim igual a –1
Podemos verificar que pode existir um grande esforço computacional para a movimentação
de 500, 1000, 10.000, 1.000.000 elementos
Esta solução escolhida parece ser bastante ineficiente
Estrutura de Dados
Filas Circulares





Solução mais elegante para resolver problema das
filas.
A idéia é armazenar os elementos na fila como um
círculo.
Primeiro elemento do vetor vem logo depois do
último.
Se o último elemento estiver ocupado, um novo
valor pode ser inserido no primeiro elemento do
vetor.
Elemento novo não será incluído numa fila circular
somente se não houver de fato espaço na mesma.
Estrutura de Dados
Filas Circulares
q.item
4
E
3
D
2
C
q.fim=4
q.item
q.Item
E
E



q.inic=4
q.item
E
q.inic=4
G
q.fim=1
D
f.inic=2
C
1
0
q.item
q.inic=2
q.fim=0
F
F
q.fim=0
F
G
q.fim=1
F
q.inic=0
No momento (4), q.fim < q.inic (1 < 4), é verdadeira – fila vazia?
Solução: q.inic deve apontar para o elemento anterior ao primeiro.
Assim, a condição para a fila estar vazia passa a ser q.fim = q.inic
Estrutura de Dados
Filas Circulares
Declaração da Fila
#define MAXQUEUE 100
struct queue
{
int item [MAXQUEUE];
int inic, fim;
};
struct queue q;
Estrutura de Dados
Filas Circulares
Inicialização da Fila
void InicializaFila(struct queue *pq)
{
pqinic = MAXQUEUE – 1;
pqfim = MAXQUEUE – 1;
}
Estrutura de Dados
Filas Circulares
Fila Vazia
int FilaVazia(struct queue *pq)
{
if(pqinic == pqfim)
return(1); //Verdadeiro(V)
else
return(0); //False(F)
}
Estrutura de Dados
Filas Circulares
Retirar Elementos
int RemoveFila (struct queue *pq)
{
if(FilaVazia(pq))
{
printf(“Underflow na fila!\n”);
exit(1);
}
if(pqinic == MAXQUEUE – 1)
pqinic = 0;
else
(pqinic)++;
return(pqitems[pqinic]);
}
Estrutura de Dados
Filas Circulares
Inserir Elementos




Problema para testar se a fila está cheia.
Solução: sacrificar um elemento da fila.
Se o vetor da fila tiver 100 elementos, poderá
armazenar 99 elementos
A tentativa de inserir o centésimo elemento irá
gerar o estouro da fila
Estrutura de Dados
Filas Circulares
Inserir Elementos
void InsereFila(struct queue *pq, int x)
{
if(pqfim == MAXQUEUE – 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items[pqfim] = x;
return;
}
Estrutura de Dados
Filas Circulares
Inserir Elementos
q.item
q.item
E
E
4
E
3
D
D
D
2
C
C
C
1
0
q.fim=4
q.item
q.inic=1
F
q.inic=1
G
q.fim=0
F
Estrutura de Dados
q.Inic =
q.fim = 1
InsereFila versus RemoveFila

Teste de overflow em InsereFila():



Ocorre somente depois que pqfim é incrementado
em uma unidade
1o. Incrementa depois verifica
Teste de underflow em RemoveFila():


Ocorre assim que a rotina é chamada, só então
pqinic é incrementado em uma unidade
1o. Verifica depois incrementa
Estrutura de Dados