Filas: Definição, Propriedades e Implementação

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

*
Filas
Profª: Karina Dutra de Carvalho Lemos
*
Definição
Uma fila é uma lista linear em que todas as inserções são realizadas em um extremo da lista, e todas as retiradas e geralmente todos os acessos são feitos no outro extremo da lista. 
O modelo intuitivo de uma fila é o de uma fila de espera em que as pessoas no início da fila (que chegaram primeiro) são servidas primeiro e as pessoas que chegam entram no fim da fila. 
*
Propriedades
·o primeiro item a ser inserido é o primeiro item que pode ser retirado da lista. 
·Por esta razão as filas são chamadas de fifo, termo formado a partir de “first-in, first-out). 
· Existe uma ordem linear para filas que é a “ordem de chegada”.
*
Utilização
As filas são utilizadas em sistemas operacionais para regular a ordem na qual tarefa deve receber processamento e recursos devem ser alocados a processos. Fila de Prioridades em algoritmos específicos. 
*
Alguns procedimentos
1. FFVazia(fila). Faz a fila ficar vazia.
2.Vazia(fila). Função que retorna true se fila estiver vazia; senão retorna false.
3.Enfileira(x,Fila). Insere o item x no final da fila.
4. Desenfileira(Fila,x). Retorna o item x no início da fila, retirando-o da fila.
*
Implementação de Filas por arranjo
Em uma implementação através de arranjos os itens da fila são armazenados em posições contíguas de memória. Devido às características da fila, a operação enfileira faz a parte de trás da fila expandir-se, e a operação desenfileira faz a parte da frente da fila contrair-se. 
*
A solução para o problema de caminhar pelo espaço alocado para uma fila é imaginar o array como um círculo, onde a primeira posição segue a última.
Para enfileirar um item basta mover o apontador trás uma posição no sentido horário; para desenfileirar um item basta mover o apontador frente uma posição no sentido horário.
*
*
Existe um pequeno problema: não há forma de distinguir uma fila vazia de uma fila cheia, pois nos dois casos os apontadores frente e trás apontam para a mesma posição no círculo. 
Uma saída é não utilizar todo o espaço disponível no array, deixando uma posição vazia. Neste caso a fila está cheia quando (trás + 1 = frente), o que significa que existe uma célula vazia entre o fim e o início da fila.
*
Implementação
const
maxtam=10;
Type
 Apontador = integer;
 Tipoitem = Record 
 chave:string ou real ou ...; 
 end;
 TipoFila = Record 
 item: array [1..MAXTAM] of tipoitem;
 frente: apontador;
		 tras: apontador;
 end;
*
Operações sobre Filas usando Arranjo
1- Procedimento para fazer a fila ficar vazia:
 
Procedure FFVazia(var Fila:TipoFila);
Begin
 Fila.frente:=1;
 Fila.tras:=fila.frente;
End;
*
Operações sobre filas
usando Arranjo
2- Função para verificar se a filas esta vazia:
 
Function vazia(var Fila:tipoFila):boolean;
Begin
 Vazia:= (fila.frente=fila.tras);
End;
*
Operações sobre filas usando Arranjo
3- Procedimento para enfileirar um elemento no fim da fila:
 
Procedure Enfileira(x:tipoitem; var fila:tipofila);
Begin
 If ((fila.tras mod maxtam) +1 = fila.frente)
 Then writeln(‘Erro: fila está cheia!’)
 Else begin
 fila.item[fila.tras]:=x; 
 fila.tras:= (fila.tras mod maxtam) + 1
 End;
End;
*
Operações sobre fila usando Arranjo
4- Procedimento para desenfileirar um elemento do inicio da fila
Procedure Desenfileira(var fila:tipofila; var item:tipoitem);
Begin
 If vazia(fila)
 Then writeln(‘Erro: fila vazia! ’)
 Else begin
 Item:=fila.item[fila.frente];
 fila.frente:=(fila.frente mod maxtam) + 1;
 end; 
End;