cap07ED LISTAS LINEARES FILA E PILHA

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
Estrutura de Dados
José Marcos Barbosa da Silveira
jmarcosbs@hotmail.com
*
*
Objetivos
Entender os fundamentos e aplicações de Filas. 
*
*
FILAS
Fundamentos 
Uma fila é um tipo especial de lista linear em que inserções são realizadas num extremo, ficando as remoções restritas ao outro. O extremo onde os elementos são inseridos é denominado final da fila, e aquele de onde são removidos é denominado começo da fila.
Também conhecida como FIFO (“First-In/First-Out”).
 Ex: Fila de caixa bancário.
entra
começo
final

sai
OPERAÇÕES BÁSICAS
 - Inserir um novo elemento na fila;
 - Remover um elemento da fila.
*
*
INSERÇÃO
	- Inserir(f,5) insere o elemento no começo da fila se houver espaço disponível e a fila aumenta de tamanho;
 	- Não retorna resultado.
 
REMOÇÃO
	- Remover um elemento da fila;
	- Remover(f) remove o elemento do final da fila e a fila diminui de tamanho;
	- Retorna o elemento que foi removido.
Operações
*
*
REPRESENTAÇÃO LINEAR DE ESTADOS SUCESSIVOS
 OPERAÇÃO ESTADO DA FILA RESULTADO
----------------------------------------------------------- 
 init(F) F:[]
 Inserir(F,1) F:[1] 
 Inserir(F,2) F:[1,2] 
 Inserir(F,3) F:[1,2,3]
 Inserir(F,4) F:[1,2,3,4] 
 Remover(F) F:[2,3,4] 1
 Remover(F) F:[3,4] 2
 Inserir(F,5) F:[3,4,5] 
 Inserir(F,6) F:[3,4,5,6]
 Inserir(F,Remover(F)) F:[4,5,6] 3
 F:[4,5,6,3]
 Remover(F) F:[5,6,3] 4
 Remover(F) F:[6,3] 5
 REmover(F) F:[3] 6
*
*
CRESCIMENTO DA FILA
	A inserção de elementos numa fila está limitada à memória máxima (quando usar arranjo) reservada pelo programador para a fila.
	
FILA VAZIA
	Uma fila é dita vazia quando não possui nenhum elemento.
 	
OPERAÇÕES ESSENCIAIS SOBRE FILAS
	- Inicialização de uma fila - init(f)
	- Verificação se a fila está cheia - cheia(f)
	- Verificação se a fila está vazia - vazia(f)
*
*
INICIALIZAÇÃO DA FILA
	- init(f) é um procedimento que Inicializa a fila definindo um estado inicial válido.
	
FILA VAZIA
	- vazia(f) é uma função lógica;
	- Retorna V se a fila está vazia.
FILA CHEIA
	- cheia(f) é uma função lógica;
	- Retorna V se a fila está cheia, ou seja, se ainda houver espaço para a inclusão de um elemento. 
	
*
*
IMPLEMENTAÇÃO DE UMA FILA
	- Os elementos de uma fila são armazenados sequencialmente;
	- A inclusão e remoção de elementos da fila não devem exigir movimentação de dados;
	- O esquema de alocação de memória sequencial é adequado.
	
FORMA DE REPRESENTAR UMA FILA NA MEMÓRIA
	- É necessário um índice para indicar a posição corrente do primeiro elemento da fila;
	- É necessário um índice para indicar a posição seguinte ao último elemento da fila;
	- É necessário um vetor para armazenar os elementos;
	- É declarado um registro contendo os índices e o vetor.
*
*
IMPLEMENTAÇÃO DE UMA FILA
CÓDIGO EM C++
const int MAX=10;
 struct tipoitem{
 int cpf;
 char nome[30];
 };
typedef struct tipoitem TipoItem;
 struct tipofila{
 tipoitem item[MAX];
 int comeco;
 int final;
 };	
typedef struct tipofila TipoFila;	
*
*
INICIALIZAÇÃO DE UMA FILA
	- Colocar o valor 0 nos índices f.comeco e f.final
	- Se f.comeco e f.final são iguais a 0 a fila está vazia.
CÓDIGO EM C++
void init(TipoFila &f){
	f.comeco=0;
	f.final=0;
}
COMENTÁRIOS
	- Procedimento pois não há necessidade de retorno;
	- Parâmetro é passado por referência pois deseja-se modificar o valor de f.começo e f.final. 
		
*
*
VERIFICAÇÃO SE UMA FILA ESTÁ VAZIA
	- Verificar se f.comeco=f.final, se é verdade a fila estará vazia.
CÓDIGO EM C++
int vazia(TipoFila &f){
	if(f.comeco==f.final)return 0;
	else
	 return 1;
}
COMENTÁRIOS
	- Função pois há necessidade de retorno;
	- Parâmetro passado por referência. 
	
*
*
VERIFICAÇÃO SE UMA FILA ESTÁ CHEIA
	- Verificar se f.final>MAX, se é verdade a fila está cheia.
CÓDIGO EM C++
 int cheia(TipoFila &f){
 	if(f.final>=MAX)return 1;
	else
	 return 0;
 }
COMENTÁRIOS
	- Função pois há necessidade de retorno;
	- Parâmetro passado por referência. 
*
*
INSERIR UM ELEMENTO NUMA FILA 
	- Verificar se a fila está cheia, caso negativo inserir, senão não efetivar a inserção e enviar mensagem. 
CÓDIGO EM C++
void push(TipoFila &f, int cpf, char nome[]){
	if(cheia(f)==0){
 f.item[f.final].cpf=cpf;
 strcpy(f.item[f.final].nome,nome);
 f.final=f.final+1;
	}	
	else
		printf("Fila Cheia");
}
COMENTÁRIOS
	- Procedimento pois não há necessidade de retorno;
	- Parâmetro passado por valor pois não precisa ser 		 modificado.
*
*
REMOVER UM ELEMENTO DE UMA FILA 
	- Verificar se a fila está vazia, caso negativo remover, senão não efetivar a remoção e enviar mensagem.
 
CÓDIGO EM C++
TipoItem pop(TipoFila &f){
	if(vazia(f)==1){
		f.comeco= f.comeco+1;
		return (f.item[f.comeco-1]);
	}
	else
		printf("Fila Vazia");
}
COMENTÁRIOS
	- Função pois há necessidade de retorno do elemento removido;
	- A remoção é lógica, mas o elemento não pode ser acessado.
	
*
*
PROBLEMA NA IMPLEMENTAÇÃO SEQUENCIAL DE UMA FILA 
	- Ao analisar uma das situações da fila criada anteriormente, pode-se observar o seguinte paradoxo: 
 	- a inserção não será permitida pois f.final>MAX e a 
 fila está cheia;
		- a remoção também não será permitida pois f.comeco=
 f.final e a fila está vazia. 
	- A implementação não é eficiente, há desperdício de memória e problemas quanto à lógica;
	- Outro tipo de implementação deverá ser buscado.	
F.comeco F.memo[n]
P:
 6 6 a g b d e
F.final
 1 2 3 4 5 posições 
*
*
SOLUÇÃO PARA A IMPLEMENTAÇÃO SEQUENCIAL DE UMA FILA
 
 - Para eliminar o erro lógico acrescenta-se uma variável 
 para conter o número de elementos presentes na lista;
 - Esta variável será inicializada com 0 e a cada inserção 
 ela será incrementada e a cada remoção ela será decrementada;
 - Para eliminar o desperdício de memória, a posição de um 
 elemento removido é disponibilizada para receber um novo elemento a ser inserido; 
 - O artifício a ser utilizado é considerar a existência da posição 1 logo após a posição MAX;
 - Este artifício conduz a uma Fila Circular;
 - Esta fila só estará cheia quando todo o espaço de armazenamento estiver ocupado.
	
*
*
SOLUÇÃO PARA A IMPLEMENTAÇÃO SEQUENCIAL DE UMA FILA
IMPLEMENTAÇÃO SEQUENCIAL CIRCULAR DE UMA FILA 	
0
1
2
3
MAX
an
an-1
4
*
*
NOVA IMPLEMENTAÇÃO SEQUENCIAL DE UMA FILA 
- Acréscimo de uma variável para conter o número de elementos presentes na lista;
- Considerar a existência da posição 1 logo após a posição MAX através da rotina adc(). 		
f.comeco f.memo[n]
 3 2 5 a g b d e
f.final
 1 2 3 4 5 posições 
f.total
 procedure adc(var i:integer); 
	 begin
	 	i:=i+1;
		if i>MAX then i:=1;
	end;	
*
*
NOVA IMPLEMENTAÇÃO SEQUENCIAL DE UMA FILA - ROTINAS
 
const int MAX=10;
 struct tipoitem{
 int cpf;
 char nome[30];
 };
typedef struct tipoitem TipoItem;
 struct tipofila{
 tipoitem item[MAX];
 int comeco;
 int final;
 int total;
 };	
typedef struct tipofila TipoFila;
	
*
*
NOVA IMPLEMENTAÇÃO SEQUENCIAL DE UMA FILA - ROTINAS
void init(TipoFila &f){
	f.comeco=0;
	f.final=0;
	f.total=0;
}
int vazia(TipoFila
&f){
	if(f.total==0)return 0;
	else
	 return 1;
}
 int cheia(TipoFila &f){
 	if(f.total==MAX)return 1;
	else
	 return 0;
}
*
*
NOVA IMPLEMENTAÇÃO SEQUENCIAL DE UMA FILA - ROTINAS
void push(TipoFila &f, int cpf, char nome[]){
	if(cheia(f)==0){
		f.item[f.final].cpf=cpf;
 strcpy(f.item[f.final].nome,nome);
 inc(f.total);
 adc(f.final);
	}	
	else
		printf("Fila Cheia");
}	
Observação: inc(f.total) é idêntica a f.total:= f.total + 1 com o código mais enxuto.
*
*
NOVA IMPLEMENTAÇÃO SEQUENCIAL DE UMA FILA - ROTINAS
TipoItem pop(TipoFila &f){
	if(vazia(f)==1){
		adc(f.comeco);
 dec(f.total);
		return (f.item[f.comeco-1]);
	}
	else
		printf("Fila Vazia");
}
Observação: dec(f.total) é idêntica a f.total:= f.total - 1 com o código mais enxuto.
	
*
*
NOVA IMPLEMENTAÇÃO SEQUENCIAL DE UMA FILA - ROTINAS
void adc(int &i){
	i=i+1;
	if(i>=MAX)i=0;
}
void inc(int &total){
	total=total+1;
}
void dec(int &total){
	total=total-1;
}	
*
*
Exercício
Fazer os procedimentos de inserção,retirada, tamanho e listar para uma lista de registros, conforme descrição abaixo:
Arranjo: CPF, Nome e Tamanho.
	 Métodos: inserir,retirar e tamanho.
Apontador: CPF e Nome.
	 Métodos: inserir e retirar.
Obs: Após cada inserção ou remoção listar os elementos da fila.
 A Fila pode ter no máximo N elementos; e
 A Fila pode não ter nenhum elemento.
*
*
Bibliografia
Veloso, P. A.S. ESTRUTURAS DE DADOS. CAMPUS, 2000.
Pereira, Silvio do Lago. Estrutura de dados Fundamentais. ÉRICA, 1996.
Bucknall, J. ALGORITIMOS E ESTRUTURAS DE DADOS COM DELPHI. BERKELEY BRASIL, 2002.
Wirth, N. ALGORITMOS E ESTRUTURAS DE DADOS. LTC, 1989.
Szwarcfiter, J. L. ESTRUTURAS DE DADOS E SEUS ALGORITMOS. LTC, 1994.