Estrutura de Dados - Filas

Prévia do material em texto

*
*
Filas
*
*
Filas
Outro caso particular de Lista Linear
Conjunto ordenado de itens onde as inclusões só podem ser feitas em uma extremidade (fim da fila) e as remoções só podem ser feitas na outra extremidade (início da fila) 
Exemplo real clássico: fila de pessoas esperando atendimento em um banco: as pessoas do início da fila são atendidas antes e as que chegam depois, entram no fim da fila
*
*
Filas
Devido às características das operações da fila, o primeiro elemento inserido será o primeiro a ser retirado
A política de inserção e remoção de dados à maneira de uma fila é conhecida como "FIFO" (First In, First Out)
Filas são usadas tipicamente quando deseja-se processar itens de acordo com sua ordem de chegada
*
*
Filas
Aplicação em Computação: Fila de Impressão
Exemplo:
início
início
início
fim
fim
fim
A
C
*
*
Filas – Operações Básicas
Seja F uma fila, e e um elemento:
insere(F, e): e é inserido no final da fila F
retira(F, e): retira o elemento mais antigo da fila F (o elemento que está no início de F) e retorna seu valor através de e
vazia(F): indica se a fila está vazia ou não
comp(F): retorna o número de elementos na fila F (comprimento da fila)
*
*
Filas - Exemplo
início
início
início
fim
fim
fim
A
C
fila
insere(fila,A);
insere(fila,B);
insere(fila,C);
ok=retira(fila,e);
*
*
Fila – Funções Básicas
Funções Básicas:
vazia(&fila);
inicia(&fila);
retira(&fila, &e);
insere(&fila, e);
*
*
Filas
2ª PARTE
*
*
Filas - Implementações
Diversas formas de implementar, que se distinguem por:
natureza dos elementos
maneira como elementos são armazenados
operações disponíveis
Duas formas clássicas: 
Listas Seqüenciais (Vetor)
Lista Encadeada
*
*
Filas em Listas Seqüenciais
Problema: vetor tem tamanho fixo e limitado, enquanto que a fila cresce com a necessidade, sem limite
	Solução: limitar o tamanho máximo da fila ao tamanho do vetor
Problema: impossível remover elemento de uma fila vazia
	Solução: utilizar a função vazia(F) antes de remover elemento
Problema: controlar início e fim da fila
	Solução: incluir dois campos (ini e fim) para armazenar a posição do início e do fim da fila
*
*
Filas com Vetor
#define MAX 100
typedef int tp_item;
typedef struct {
	tp_item item[MAX];
	int ini,fim;
} tp_fila;
tp_fila fila;
*
*
Filas com Vetor
Considerações Iniciais:
	fila.fim=-1; /* posição do último elemento */
	fila.ini=0; /* posição do primeiro elemento */
Fila Vazia:
	(fila.fim<fila.ini)
Fila Lotada:
	(fila.fim==MAX-1)
No de elementos:
	(fila.fim-fila.ini+1)
Função insere:
	f.item[++f.fim]=e;
Função retira:
	*e=f.item[f.ini++];
*
*
Filas com Vetor
Problema:
ini e fim avançam à medida em que são feitas inclusões e remoções
pode acontecer de a fila ter espaço mas ser considerada lotada (situação 4)!!
ini: 0
fim: -1
MAX: 5
A
B
C
ini: 0
fim: 2
MAX: 5
C
ini: 2
fim: 2
MAX: 5
C
D
E
ini: 2
fim: 4
MAX: 5
(1)
(2)
(4)
(3)
 A B C
 A B
 D E
0 1 2 3 4 
*
*
e=f.item[0];
 for (i=0; i<fila.fim; i++)
	fila.item[i]=fila.item[i+1];
Filas com Vetor
Solução 1: modificar retira para deslocar a fila no sentido do início do vetor a cada remoção e eliminar o campo fila.ini  início é sempre no 0
 
fim: -1
MAX: 5
A
B
C
fim: 2
MAX: 5
C
fim: 0
MAX: 5
C
D
E
fim: 2
MAX: 5
(1)
(2)
(4)
(3)
 A B C
 A B
 D E
Fila vazia:
 (fila.fim==-1)
*
*
Filas com Vetor
Problemas com a Solução 1:
Cada eliminação envolve deslocar todos os elementos restantes da fila  Ineficiência
	(principalmente para grandes filas)
A definição da operação de remoção envolve a manipulação de apenas um elemento e a sua implementação deve refletir este fato, sem envolver operações adicionais
*
*
Filas com Vetor
Outra Solução?
*
*
Fila Circular
Solução 2: visualizar o vetor que armazena a fila como um círculo  Fila Circular
	se o último elemento da fila ocupa a última posição do vetor, um novo elemento pode ser inserido no início do vetor
 
ini: 0
fim: -1
MAX: 5
A
B
C
D
ini: 0
fim: 3
MAX: 5
C
D
ini: 2
fim: 3
MAX: 5
F
G
C
D
E
ini: 2
fim: 1
MAX: 5
(1)
(2)
(4)
(3)
 A B C D
 A B
 E F G
0 1 2 3 4 
*
*
Fila Circular
Outras considerações:
Função para determinar o próximo elemento:
int prox (int pos) {
if (pos==MAX-1)
	return 0;
else
	return pos+1;	
}
*
*
Fila Circular – Fila Vazia
Determinação de Fila Vazia?
 não pode mais ser feita por (fila.fim<fila.ini)
ini: 0
fim: -1
MAX: 5
F
G
C
D
E
ini: 2
fim: 1
MAX: 5
(1)
(4)
0 1 2 3 4 
0 1 2 3 4 


*
*
Fila Circular – Fila Vazia
Problema com a Fila Circular: determinação de Fila Vazia não pode mais ser feita com (fila.fim<fila.ini)
Solução:
considerar que fila.ini é a posição anterior ao primeiro elemento da fila
Para verificar se a fila está vazia:
	(fila.ini==fila.fim)
Para inicializar  início e fim com última posição:
	fila.ini = fila.fim = MAX-1; (precede posição 0) 
*
*
Fila Circular – Fila Vazia
Solução! (fila.ini==fila.fim)
ini: 4
fim: 4
MAX: 5
A
B
C
D
ini: 4
fim: 3
MAX: 5
ini: 3
fim: 3
MAX: 5
F
G
H
E
ini: 3
fim: 2
MAX: 5
(1)
(2)
(4)
(3)
 A B C D
 A B C D
 E F G H 
0 1 2 3 4 
0 1 2 3 4 
*
*
Fila Circular – Fila Cheia
Problema: Determinação de Fila Cheia
 Situação idêntica à da Fila Vazia
Solução:
“sacrificar” uma posição do vetor, permitindo incluir apenas MAX-1 elementos
há sempre uma posição vazia para marcar início/fim da fila
Teste de Fila Cheia:
prox(fila.fim)==fila.ini
*
*
Fila Circular – Fila Cheia
Fila Vazia (fila.ini==fila.fim)

ini: 4
fim: 4
MAX: 5
A
B
C
D

ini: 4
fim: 3
MAX: 5

ini: 3
fim: 3
MAX: 5
F
G
H

E
ini: 3
fim: 2
MAX: 5
(1)
(2)
(4)
(3)
 A B C D
 A B C D
 E F G H
0 1 2 3 4 
0 1 2 3 4 
Fila Cheia (prox(fila.fim)==fila.ini)
*
*
Fila Circular – Fila Cheia
Outra Solução:
Adicionar um novo campo (tam) na estrutura para armazenar o número de elementos na fila
Fila Vazia: (fila.tam==0)
Fila Cheia: (fila.tam==MAX-1)
Solução não adotada pela maioria dos autores e programadores
*
*
Fila Circular
Funções Básicas:
vazia(&fila);
inicia(&fila);
retira(&fila, &e);
insere(&fila, e);
*
*
Fila Circular
Função vazia(&fila):
int vazia(tp_fila *f) {
	if (f->ini == f->fim)
		return 1;
	else
		return 0;
}
/* outra opção */
int vazia(tp_fila *f) {
	return (f->ini==f->fim); 
}
Função inicia(&fila):
void inicia (tp_fila *f) {
	f->ini=f->fim=MAX-1;
}
*
*
Fila Circular
int retira(tp_fila *f, tp_item *e) {
	if (vazia(f))
		return 0;
	else {
		f->ini=prox(f->ini);
		*e=f->item[f->ini];
		return 1;
	}
}
*
*
Fila Circular
int insere(tp_fila *f, tp_item e) {
	if (prox(f->fim)==f->ini)
		return 0;
	else {
		f->fim=prox(f->fim);
		f->item[f->fim] = e;
		return 1;
	}
}
*
*
Fila Circular
Como percorrer a Fila?
?
*
*
Fila Circular
if (!vazia(&fila)) {
	i=fila.ini;
	do {
		i=prox(i);
		printf("%d\t",fila.item[i]);
		} while (i!=fila.fim);
		printf("\n");
}
/*outra forma */
i=fila.ini;
while (i!=fila.fim) {
	i=prox(i);
	printf("%d\t",fila.item[i]);
} printf("\n");
Para percorrer:
*
105
*
104
*
105
*
105
*
105
*
105
*
105
*
105
*
105
*
105
*
105
*
105
*
105
*
105
*
105
*
105
*
105
*
105
*
105
*
105
*
105
*
105
*
105