Estrutura de dados II
Carlos Oberdan Rolim
Ciência da Computação
Sistemas de Informação
Filas (queues)
O que é uma fila?
1
4
3
2
Fila
1
2
3
4
O que é uma fila?
Fila
1
2
3
4
O que é uma fila?
1
Fila
2
3
4
O que é uma fila?
2
1
Fila
3
4
O que é uma fila?
2
1
3
Fila
4
TAD Fila
É uma lista linear em que todas as inserções de novos
elementos são realizadas numa extremidade da lista e todas
as remoções de elementos são feitas na outra extremidade da
lista.
Tipo Abstrato de dados com a seguinte característica:
O primeiro elemento a ser inserido é o primeiro a ser
retirado/ removido
(FIFO – First in First Out)
Elemento inserido torna-se o último da fila
Analogia: fila bancária, fila do cinema.
Usos: Sistemas operacionais: fila de impressão,
processamento
TAD Fila
Operações:
1. inicFila(Fila x). Inicializa a fila
2 Enfileira(Fila, x). Insere o item x no final da fila.
3. Desenfileira(Fila). Retorna o item no início da fila,
retirando-o da fila.
4. vazia(Fila). Esta função retorna true se a fila está
vazia; senão retorna false.
Estrutura para representar uma fila
A fila pode ser representada por um vetor.
O vetor é utilizado para armazenar os elementos da fila
juntamente com duas variáveis inic e fim que representam
inicio e fim da fila
#define MAXFILA 100
struct queue {
int item[MAXFILA];
int inicio, fim;
}
Declaração da fila q
struct queue q;
Inserção de um elemento
Considerar inicialmente sem a hipótese de overflow ou
underflow
Inserir faz o fim da fila incrementar em uma posição
indicando onde o próximo elemento vai entrar
Enfileira(q, x) faz a inserção de x na fila q
q.item[++ q.fim] = x;
Remoção de um elemento
Considerar inicialmente sem a hipótese de overflow ou
underflow
Remover faz o inicio da fila incrementar indicando qual o
próximo elemento a sair
Desenfileira(q) Retorna o item no início da fila, retirando-o da
fila
x = q.item[q.inicio ++];
A chamada a essa função seria
x = Desenfileira(q);
Inicio e fim da fila
No momento em que a fila é criada q.fim = -1 e q.inicio = 0
Fila vazia sempre que q.fim < q.inicio
O número de elementos é sempre igual ao valor q.fim –
q.inicio + 1
Com essas considerações consideramos que a fila ao ser
inicializada tem sempre 0 elementos ( -1 + 0 + 1 = 0)
Inicio e fim da fila
A medida que se inserem elementos na fila q a posição final
da fila é incrementada
q.fim++;
Na remoção é a vez do inicio da fila ser decrementado
q.inicio++;
Analisando esse processo notamos que o valor de q.inicio
caminha em direção a q.fim até o momento que q.fim tornase menor do que q.inicio
Neste caso é sinalizado que a fila q está vazia
Lembre-se que a condição q.fim < q.inicio define a fila vazia
Inconvenientes da Fila
Implementação simplista pode gerar alguns inconvenientes
q.item
q.item
q.item
q.item
4
4
4
4
50
3
3
3
3
40
2
2
30
fim=2
Inicio=2 2
30
1
1
20
1
1
0
fim=-1 0
10
0
0
30
Inicio=0
Inicio=0
(a)
fim=2
2
(b)
(c)
(d)
fim=4
Inicio=2
Inconvenientes da Fila
a)Fila vazia
q.inicio = 0 q.fim = -1
Numero de elemtos = q.fim – q.inicio + 1  -1 -0 + 1 = 0
b) Inclusão de 3 elementos no final da fila
q.inicio = 0 q.fim = 2
Numero de elemtos = q.fim – q.inicio + 1  2 -0 + 1 = 3
c) Remoção de 2 elementos do inicio da fila
q.inicio = 2 q.fim = 2
Numero de elemtos = q.fim – q.inicio + 1  2 -2 + 1 = 1
d) Inclusão de 2 novos elementos no final da fila
q.inicio = 2 q.fim = 4
Numero de elemtos = q.fim – q.inicio + 1  4 -2 + 1 = 3
Inconvenientes da Fila
E se quisermos inserir mais elementos ??
Não existe possibilidade pois o elemento 50 já ocupa a última posição
Porém existem 2 posições livre no inicio do vetor (pos 0 e pos 1)
Como dito uma fila vazia ocorre quando q.fim < q.inicio
Situação absurda de termos espaço livre no vetor e não podermos
inserir mais elementos devido a implementação simplista
Possibilidade para contornar seria modificar a operação
Desenfileira(q) de modo que ao remover um elemento
movimenta a fila como um todo em direção ao inicio do vetor
x = q.item[0];
for(k=0; k < q.fim; k++)
q.item[k] = q.item[k+1];
q.fim--;
Solução ineficiente para grande quantidade de valores
Fila circular
Solução mais elegante para resolver problema visto
anteriormente
Idéia do primeiro elemento vir logo após o último dando a
impressão de circulo
Se o último elemento estiver ocupado um novo elemento poderá ser
incluido depois dele, nesse caso o primeiro, desde que esteja
obviamente vazio
Fila circular
Mecanismo da fila circular
q.item
q.item
q.item
q.item
50
Inicio=4
1
70
fim=1
0
60
50
4
40
3
40
3
3
30
Inicio=2 2
30
Inicio=2 2
2
1
50
3
2
fim=4
1
1
0
0
(a)
60
(b)
fim=0
0
50
Inicio=4 4
4
4
60
(c)
fim=0
(d)
Fila circular
Pode-se perceber que o problema da inclusão foi resolvido
Entretanto no instante (d) q.fim < q.inicio (1 < 4) poderiamos
concluir que a fila está vazia o que não é o fato
Devido a implementação da fila circular não podemos mais
simplesmente comparar se q.fim é menor que q.inicio para
saber se a fila está vazia
Como determinar se a fila está vazia ?
Solução: nova convenção para q.inicio. Assume-se que
q.inicio é o indice do vetor que é exatamente anterior ao
primeiro elemento da fila, em vez de ser o indice do próprio
primeiro elemento
Como q.fim é o indice do último elemento da fila a
convenção adotada faz com que a fila seja vazia quando
q.inicio = q.fim
Fila Circular
Estrutura e inicialização
#define MAXFILA 100
struct queue {
int item[MAXFILA];
int inicio, fim;
};
struct queue q;
q.Inicio = q.fim = MAXFILA – 1;
Último elemento do vetor
ao invés de -1 e 0
Inicialização da fila
void inicFila(struct queue *pq){
pq  inicio = MAXFILA – 1;
pq  fim = MAXFILA – 1;
}
Fila vazia ou Fila cheia
•Quando for operação de inserir
se Inicio == fim pilha cheia
•Quando operação de remoção
se inicio == fim pilha vazia
int isfull(struct queue * pq){
if(pq  inicio == pq  fim)
return 1; // verdadeiro – fila vazia ou cheia
else
return 0; // falso – fila não está vazia nem cheia
}
Uso:
if(filaVazia(&q))
/* tratamento para fila vazia */
else
/* tratamento para fila não vazia */
Inserção de um elemento
q.item
4
50
3
40
2
30
1
20
0
10
Inicio = fim = 1
Overflow pode ser confundido com underflow
Fila vazia quando q.inicio == q.fim
Novo impasse: Como determinar se a fila está cheia ou vazia ?
Solução: sacrificar a ultima posição para diferenciar situações.
Significa que o vetor aumenta somente até um elemento abaixo
do tamanho máximo do vetor
Inserção de um elemento
void insFila(struct queue *pq, int x){
if(pq->fim==max-1)
pq->fim=0;
else
pq->fim++;
/* verifica a ocorrencia de estouro */
if(isfull(pq)){
printf("queue overflow\n");
pq->fim--;
}else
pq->data[pq->fim]=x;
}
Remoção de um elemento
int remFila(struct queue *pq) {
if(isfull(pq)){
printf("queue underflow\n");
return 0;
}
if(pq->inicio==max-1)
pq->inicio=0;
else
pq->inicio++;
return pq->data[pq->inicio];
}
Inserção / Remoção de um elemento
A grande diferença entre a função de inserir e remover é que
o teste de estouro em insFila() ocorre depois que qfim é
atualizado.
O teste de underflow em remFila() ocorre imediatamente
quando a função é disparada, só então pqinicio é
atualizado
Código completo
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
# define max 5
display(&q); /* mostra a fila */
printf("-> %d \n", remFila(&q));
printf("-> %d \n", remFila(&q));
printf("-> %d \n", remFila(&q));
printf("-> %d \n", remFila(&q));
printf("-> %d \n", remFila(&q)); /* underflow*/
struct queue{
int data[max];
int inicio,fim;
};
void insFila(struct queue *pq, int x);
int remFila(struct queue *pq);
int isfull(struct queue *pq);
void display(struct queue *pq);
void iniFila(struct queue *pq);
display(&q);
getch();
return 0;
int main() {
struct queue q;
iniFila(&q); /* inicializa fila */
insFila(&q, 2);
insFila(&q, 3);
insFila(&q, 4);
insFila(&q, 5);
insFila(&q, 6); /* overflow */
}
void iniFila(struct queue *pq){
pq->inicio = pq->fim = max-1;
}
void insFila(struct queue *pq, int x){
if(pq->fim==max-1)
pq->fim=0;
else
pq->fim++;
if(isfull(pq)){
printf("queue overflow\n");
pq->fim--;
}else
pq->data[pq->fim]=x;
}
int remFila(struct queue *pq) {
if(isfull(pq)){
printf("queue underflow\n");
return 0;
}
if(pq->inicio==max-1)
pq->inicio=0;
else
pq->inicio++;
return pq->data[pq->inicio];
}
int isfull(struct queue *pq){
if(pq->inicio==pq->fim)
return 1;
else
return 0;
}
void display(struct queue *pq){
int i;
if(pq->inicio==pq->fim){
printf("Fila vazia\n");
return;
}
i=pq->inicio;
if(pq->inicio==max-1)
i=0;
else
i++;
while(1){
printf("%d\n",pq->data[i]);
if(i==pq->fim)
break;
if(i==max-1)
i=0;
else
i++;
} /* end while*/
}