04.Filas

Prévia do material em texto

Aula 04
Filas
Rodolfo Carneiro Cavalcante
Universidade Federal de Alagoas – UFAL
Campus Arapiraca
4 de Maio de 2015
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 1 / 42
Suma´rio
1 Introduc¸a˜o
2 Implementac¸a˜o com Arranjos
3 Implementac¸a˜o com Estruturas Auto-Referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 2 / 42
Introduc¸a˜o
Suma´rio
1 Introduc¸a˜o
2 Implementac¸a˜o com Arranjos
3 Implementac¸a˜o com Estruturas Auto-Referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 3 / 42
Introduc¸a˜o
Introduc¸a˜o
Uma fila e´ um tipo abstrato de dados muito utilizado em
programac¸a˜o, assim como as pilhas
Uma fila e´ uma lista linear em que todas as inserc¸o˜es sa˜o realizadas
em um extremo da lista e as retiradas sa˜o realizadas no outro extremo
First-in, first-out (FIFO) – primeiro a entrar, primeiro a sair
Similar a uma fila indiana, como a fila do banco
As pessoas que chegam primeiro sa˜o atendidas primeiro
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 4 / 42
Introduc¸a˜o
Introduc¸a˜o
Exemplos de utilizac¸a˜o
Controle de tarefas em espera em um Sistema Operacional
Va´rias tarefas competem para utilizar um recurso compartilhado e
escasso, como a impressora
O sistema operacional cria uma fila de impressa˜o para armazenar as
solicitac¸o˜es que chegam
Fila de repasse em um roteador
Quando um pacote chega ao enlace de entrada de um roteador, este
deve conduzi-lo ate´ o enlace de sa´ıda apropriado
Uma tabela de repasse e´ utilizada para verificar qual a porta de sa´ıda
do pacote com base em seu cabec¸alho
Se existem va´rios pacotes a serem repassados, estes devem esperar em
uma fila nas portas de entrada ou de sa´ıda
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 5 / 42
Introduc¸a˜o
Operac¸o˜es sobre o TAD Fila
Criar uma fila vazia
Enfileirar – inserir um item x no fim da fila
Desenfileirar – retornar o primeiro item da fila
Verificar se esta´ vazia
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 6 / 42
Introduc¸a˜o
Implementac¸a˜o
Existem va´rias opc¸o˜es de estruturas de dados que podem ser usadas
para implementar uma fila
As mais utilizadas sa˜o:
implementac¸a˜o por meio de arranjos (vetor)
implementac¸a˜o por meio de estruturas auto-referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 7 / 42
Implementac¸a˜o com Arranjos
Suma´rio
1 Introduc¸a˜o
2 Implementac¸a˜o com Arranjos
3 Implementac¸a˜o com Estruturas Auto-Referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 8 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Utilizac¸a˜o de um vetor para armazenar itens
Itens sa˜o armazenados em posic¸o˜es consecutivas de memo´ria
Inserc¸o˜es acontecem no fina do vetor
Retiradas acontecem no in´ıcio do vetor
Vetor deve ter tamanho suficiente para armazenar itens da fila
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 9 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Quando implementamos uma pilha com arranjo, havia um ı´ndice para
guardar o topo da pilha
as operac¸o˜es sempre aconteciam naquela posic¸a˜o de memo´ria
Agora precisamos guardar o ı´ndice do primeiro e do u´ltimo item da
fila
a inserc¸a˜o acontece no ı´ndice do ultimo elemento +1
a retirada acontece no ı´ndice do primeiro elemento
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 10 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Qual o problema com esse tipo de implementac¸a˜o?
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 11 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Qual o problema com esse tipo de implementac¸a˜o?
A operac¸a˜o de enfileirar faz a parte de tra´s da fila se expandir
A operac¸a˜o desenfileirar faz a parte da frente da fila se contrair
A fila tende a caminhar pela memo´ria do computador
Ocupa espac¸o na parte de tra´s e descarta espac¸o na parte da frente
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 12 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Qual o problema com esse tipo de implementac¸a˜o?
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 13 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Qual o problema com esse tipo de implementac¸a˜o?
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 14 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Como resolver o problema?
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 15 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Como resolver o problema?
Circular os ı´ndices de primeiro e u´ltimo para o in´ıcio do vetor
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 16 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Como resolver o problema?
Fila circular
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 17 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Em um TAD pilha, como saber se a pilha esta´ vazia?
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 18 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Em um TAD pilha, como saber se a pilha esta´ vazia?
Basta verificar se o topo e´ igual ao tamanho ma´ximo.
E no caso da fila circular?
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 19 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Em um TAD pilha, como saber se a pilha esta´ vazia?
Basta verificar se o topo e´ igual ao tamanho ma´ximo.
E no caso da fila circular?
Basta verificar se primeiro = ultimo + 1
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 20 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 1: Estrutura de dados Fila (arranjo)
template <class T> class Fila{
private:
T* itens;
int inicio, fim, maxTam;
public:
Fila(int maxTam);
bool vazia();
void imprime();
void enfileira(T item);
T desenfileira();
};
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 21 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
A estrutura que guarda a fila e´ um vetor
T* itens;
O ı´ndice inicio indica a primeira posic¸a˜o da fila
O ı´ndice fim guarda a posic¸a˜o do fim da fila
O tamanho ma´ximo da fila (maxTam) e´ usado para indicar o limite
do vetor
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 22 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 2: Estrutura de dados Fila: criar fila vazia
template <class T> Fila<T>::Fila(int maxTam){
this->inicio = this->fim = 0;
this->maxTam = maxTam;
this->itens = new T[this->maxTam];
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 23 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
O construtor da classe Fila faz as devidas inicializac¸o˜es
o inicio da pilha sera´ a posic¸a˜o 0
o fim da pilha sera´ a posic¸a˜o 0 tambe´m
o tamanho ma´ximo sera´ passado como paraˆmetro para o construtor
o vetor itens e´ inicializado dinamicamente
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 24 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 3: Estrutura de dados fila: verificar se esta´ vazia
template <class T> bool Fila<T>::vazia(){
return this->inicio == this->fim;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 25 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 4: Estrutura de dadosfila: enfileirar no fim da fila
enfileira(item){
se (fim + 1)%maxTam == inicio
imprima(“fila cheia!”);
senao{
itens[fim] = item;
fim = (fim+1)%maxTam;
}
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 26 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
E´ importante notar que, na implementac¸a˜o original de fila circular,
na˜o da´ para se distinguir uma fila vazia de uma fila cheia
Se fim == inicio, a fila pode estar vazia ou cheia
Soluc¸a˜o: deixar um espac¸o vazio
Assim, quando fim + 1 == inicio, significa que a fila esta´ cheia
E´ importante notar tambe´m que essa verificac¸a˜o na˜o e´ feita com os
ı´ndices diretamente
utilizamos aritme´tica modular para manipular os ı´ndices
dessa forma, conseguimos circular nos ı´ndices sem precisar verificar se
estamos nos limites do vetor itens
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 27 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 5: Estrutura de dados fila: desenfileirar na frente da fila
desenfileira(){
se(nao vazia){
item = itens[inicio];
inicio = (inicio+1)%maxTam;
retorne item;
}
senao
imprima(“lista vazia”);
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 28 / 42
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Considerac¸o˜es sobre implementac¸a˜o de filas com arranjos
Da mesma forma que acontece com a implementac¸a˜o de pilhas, temos
Economia de memo´ria – apontadores sa˜o impl´ıcitos e na˜o precisam
ser armazenados na memo´ria
Problema: tamanho da fixo e´ fixo
aplicac¸o˜es que na˜o possuem previsa˜o sobre crescimento da fila
requerem realocac¸a˜o de memo´ria
operac¸a˜o de alto custo de tempo e memo´ria
criar nova a´rea com mais posic¸o˜es e copiar todos os itens para esta a´rea
Nestes casos, a soluc¸a˜o e´ o uso de filas com estruturas
auto-referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 29 / 42
Implementac¸a˜o com Estruturas Auto-Referenciadas
Suma´rio
1 Introduc¸a˜o
2 Implementac¸a˜o com Arranjos
3 Implementac¸a˜o com Estruturas Auto-Referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 30 / 42
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Fila e´ organizada em ce´lulas
Cada ce´lula guarda um item de dado e uma refereˆncia para a pro´xima
ce´lula
Permite utilizar posic¸o˜es na˜o cont´ıguas de memo´ria
Na˜o e´ necessa´rio definir a priori o tamanho ma´ximo da fila
A fila guarda uma refereˆncia para a ce´lula do in´ıcio e do fim
As demais ce´lulas apontam para a pro´xima ce´lula da fila
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 31 / 42
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 32 / 42
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Para inserir um item
cria-se uma nova ce´lula xn para o item
faz a fila apontar para a nova ce´lula como sendo o fim da fila
faz essa nova ce´lula apontar para NULL
Para desenfileirar um item
desliga-se a ce´lula x1
faz a pro´xima ce´lula ser o in´ıcio da fila
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 33 / 42
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Cada ce´lula da fila conte´m um item e uma refereˆncia para a pro´xima
ce´lula
Algoritmo 6: Estrutura de dados Fila: ce´lula
template <class T> class Celula{
public:
T item;
Celula* prox;
Celula(){
prox = NULL;
}
};
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 34 / 42
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
A classe Celula possui um campo item para guardar o item a ser
armazenado na pilha
Possui um ponteiro prox que aponta para a pro´xima ce´lula da pilha
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 35 / 42
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 7: Estrutura de dados Fila
template <class T> class Fila{ private:
Celula<T> *inicio, *fim;
int tam;
public:
Fila();
bool vazia();
void imprime();
void enfileira(T item);
T desenfileira();
int tamanho();
};
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 36 / 42
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
A fila guarda um ponteiro para a ce´lula do in´ıcio e um ponteiro para a
ce´lula do fim da fila
A varia´vel tam e´ utilizada para se guardar o tamanho atual da fila,
sem precisar percorreˆ-la
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 37 / 42
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 8: Estrutura de dados Fila: Construtor e operac¸a˜o vazia
template <class T> Fila<T>::Fila(){
this->inicio = new Celula<T>;
his->fim = this->inicio;
}
template <class T> bool Pilha<T>::vazia(){
return this->inicio == this->fim;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 38 / 42
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Existe uma ce´lula cabec¸a que aponta para a primeira ce´lula
Apesar de a ce´lula cabec¸a na˜o conter informac¸a˜o, e´ conveniente
fazeˆ-la com a mesma estrutura que uma outra ce´lula qualquer, para
simplificar as operac¸o˜es sobre a fila
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 39 / 42
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 9: Estrutura de dados Fila: enfileirar
enfileira(item){
fim->prox = new Celula();
fim = fim->prox;
fim->item = item;
tam++;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 40 / 42
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 10: Estrutura de dados Pilha: desenfileirar
desenfileira(){
se(nao vazia){
Celula* aux = inicio->prox;
inicio->prox = aux->proximo;
item = aux->item;
delete aux;
tam−−;
retorne item
} senao
retorne NULO;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 41 / 42
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Considerac¸o˜es sobre estruturas auto-referenciadas
Mesmas considerac¸o˜es feitas para pilhas
Implementac¸a˜o u´til em aplicac¸o˜es em que na˜o existe previsa˜o sobre o
crescimento da pilha
Desvantagem – utilizac¸a˜o de memo´ria extra para armazenar as
refereˆncias (os ponteiros prox)
Rodolfo Carneiro Cavalcante (UFAL) Aula 04Filas 4 de Maio de 2015 42 / 42
	Introdução
	Implementação com Arranjos
	Implementação com Estruturas Auto-Referenciadas