Aula 5 – Estr. Clássicas

Aula 5 – Estr. Clássicas - Fila
Universidade Federal de Santa Maria
Colégio Agrícola de Frederico Westphalen
Curso Superior de Tecnologia em Sistemas para Internet
Prof. Bruno B. Boniati – www.cafw.ufsm.br/~bruno
FIFO - First In First Out
• Para que um elemento entre na fila ele será
sempre colocado em uma extremidade
denominada final (término, fim);
• Para que um elemento seja retirado da fila, ele
sairá de uma outra extremidade denominada
começo (início, frente);
FIFO
• First in, first out
• Os elementos da fila são retirados na mesma
ordem em que foram introduzidos: o primeiro a
entrar é o primeiro a sair;
• Não são permitidas operações sobre quaisquer
nodos, somente sobre aqueles definidos pela
organização da fila.
• Controle de acesso a recursos compartilhados
(fila de impressão, por exemplo)
• Política de escalonamento de processos
baseada em prioridades;
Sistema
Operacional
• Definição das prioridades em uma lista de
downloads;
• Agendamento de tarefas;
• Troca de mensagens em um sistema distribuído;
• Leitura do buffer do teclado;
• Enfileiramento de pacotes no equipamento de
rede, antes de submetê-los ao enlace;
• Etc.
• Uma fila permite basicamente duas operações:
Enfileirar (inserir um elemento na fila)
Desenfileirar (retirar um elemento da fila)
• Antes de pensar os algoritmos, precisamos:
Pensar em uma estratégia de armazenamento da
estrutura;
Pensar na interface das operações que irão
manipular os dados da estrutura;
• Para representar fisicamente uma fila podemos
usar diferentes estratégias:
Contigüidade física – com o uso de vetores;
Alocação dinâmica ou encadeamento – com a
utilização de ponteiros;
• Vamos adotar a opção 1 (utilização de vetores)
em função da simplicidade dos algoritmos;
• A organização lógica da fila independe da
estratégia de armazenamento.
#define MAX 100
typedef struct fila {
int comeco;
int final;
int vetor[MAX];
} Fila;
De que forma
posso representar
uma fila?
• Inicialmente precisamos:
Qual é a
interface do
TAD Fila?
Criar e inicializar uma fila;
Enfileirar (inserir) um elemento;
Desenfileirar (retirar) um elemento;
Destruir uma fila (liberar a memória
ocupada pela mesma);
• Saber se a fila está vazia;
• Saber se a fila está cheia;
• etc...
•
•
•
•
Fila* criaFila();
void liberaFila(Fila* p);
int inserir(Fila* p, int v);
int retirar(Fila* p, int* v);
int estahVazia(Fila* p);
int estahCheia(Fila* p);
•
•
•
•
•
•
•
•
•
• Vetor[5]:
começo
final
0
1
3
2
1
3
0
2
4
5
12
40
30
20
Insere 12
Insere 40
Insere 30
Retira
Insere 20
Retira
Retira
Insere 10
Insere 9
• Erro! Fila cheia
10
Fila* criaFila();
• Aloca memória para a estrutura física;
• Inicializa os controles de início e o fim da fila;
• Retorna um ponteiro para a estrutura criada;
void liberaFila(Fila* p);
• Recebe um ponteiro para uma estrutura do tipo
fila e libera a memória ocupada por ela;
int estahVazia(Fila* p);
•
O início e o fim da fila estão na mesma
posição;
int estahCheia(Fila* p);
•
O fim da fila está na última posição!
int inserir(Fila* p, int v);
• Recebe um ponteiro para uma estrutura do tipo
fila e um valor a ser enfileirado;
• Verifica se a fila já não está cheia;
• Se não está, então ...
Coloca o elemento na posição indicada pelo fim
Incrementa o valor do fim;
• A função inserir() retorna 1 (um) se o valor foi
enfileirado ou então retorna 0 (zero) se não foi
possível enfileirar;
int retirar(Fila* p, int* v);
• Recebe um ponteiro para uma estrutura do tipo
fila e um ponteiro para uma variável inteira;
• Verifica se a fila já não está vazia;
• Se não está, então ...
Retira o elemento da posição indicada pelo início;
Incrementa o valor do início;
• A função retirar() retorna 1 (um) se o valor foi
retirado da fila ou então retorna 0 (zero) se não
foi possível retirá-lo;
a = criaFila();
inserir(a,10);
inserir(a,20);
inserir(a,30);
int x;
retirar(a, &x);
printf("Elemento '%d' retirado",x);
liberaFila(a);
Exercícios para fixação
• Dado um labirinto representado por uma matriz NxN,
contendo -1 em posições onde há um obstáculo, 1 nas
posições onde há ouro e 0 nas posições livres. Escreva
um programa para percorrer o labirinto e determinar
quanto ouro existe no mesmo.
0
1
2
3
4
5
6
0
-1
-1
-1
-1
-1
-1
-1
1
-1
0
0
-1
0
-1
-1
2
-1
0
0
0
0
1
-1
3
-1
-1
-1
0
0
0
-1
4
-1
1
-1
0
-1
0
-1
5
-1
0
0
0
-1
0
-1
6
-1
-1
-1
-1
-1
-1
-1
Coloca na fila a posição inicial (x,y)
Enquanto a fila não está vazia
Remove a posição do início da fila
Para cada posição vizinha que é
acessível e que não foi visitada,
coloque na fila e marque como
visitada.
“Dobrar” o vetor de forma que as suas extremidades se encontrem
• Observe a seguinte situação (considerando uma fila
normal, de tamanho N implementada sobre um vetor):
São inseridos N elementos na fila;
Em seguida são retirados n-2 elementos;
Tenta-se incluir mais um elemento;
O que acontece?
A fila acusará fila cheia! Mas há espaço no vetor!
Isso é um problema da regra que define a fila? Não!
O problema decorre da forma utilizada para
representar a fila: o VETOR;
• Se modificarmos a organização física da fila e a
implementação de suas operações o problema
pode ser resolvido.
• Vamos imaginar um “vetor dobrado” de forma
que o fim do vetor se encontre com o início
• Antes de mais nada, uma fila circular é uma fila
e portanto suas operações acontecem da
seguinte forma:
Inclusões: no final da fila;
Retiradas: no início da fila;
• A diferença está na forma de tratar a
organização física da fila. A interface é a mesma
da fila tradicional.
#define MAX 100
typedef struct fila {
int comeco;
int final;
int tamanho;
int vetor[MAX];
} Fila;
Precisamos
controlar o
tamanho da fila
de outra forma!
• Precisamos garantir que os indicadores de
posicionamento da fila circular (começo e final)
retornem ao início sempre que atingirem o valor
limite do tamanho do vetor;
• Algo como:
variavel = variavel + 1
se variavel > MAX então
variavel = 0
• As condições “fila cheia” e “fila vazia” também
devem ser alteradas:
• Uma fila está cheia se o campo que foi
adicionado par controlar o tamanho for igual ao
tamanho do vetor;
• Uma fila está vazia se o tamanho for igual a
zero;
Exercícios para fixação
• Modifique a implementação das operações e da
estrutura utilizada para representar uma fila
utilizando uma organização circular (conforme
os conceitos discutidos até então);