16_filas_em_estrutura_de_dados

Prévia do material em texto

Filas Professor Sérgio Furgeri 
Página 1 
Filas 
 
Fila é um tipo de lista linear onde as inserções são realizadas num extremo (final da Fila) e 
as remoções restritas ao outro (começo da Fila). 
 
O primeiro a entrar é o primeiro a sair e último a entrar é também o último a sair (FIFO - 
First-In/First-Out). 
 
A ordem de saída corresponde diretamente à ordem de entrada dos elementos. 
 
Exemplo Físico: 
 
 
 
Patindo da palavra ingles queue que significa fila, são denominadas duas operações básicas 
suportadas pelas Filas: 
 
• Enqueue: insere um elemento no final da Fila. 
• Dequeue: remove um elemento do começo da Fila. 
 
Exemplo de Instruções 
 
Enqueue (F, x) → aumenta o tamanho da Fila F, acrescentando o elemento x no seu final. 
 
Dequeue (F, x) → diminui o tamanho da Fila F, removendo e retornando o elemento 
posicionado no começo da Fila. 
 
 
Exemplo do uso das instruções da Fila (representação gráfica) 
 
Operação Estado da Fila Resultado 
----------------- F:[ ] --------------- 
Enqueue(F, a) F:[ a ] --------------- 
Enqueue(F, b) F:[ a, b ] --------------- 
Enqueue(F, c) F:[ a, b, c ] --------------- 
Enqueue(F, d) F:[ a, b, c, d ] --------------- 
Dequeue(F) F:[ b, c, d ] a 
Dequeue(F) F:[ c, d ] b 
Enqueue(F, e) F:[ c, d, e ] --------------- 
Fila de caixa bancário
Filas Professor Sérgio Furgeri 
Página 2 
Enqueue(F, f) F:[ c, d, e, f ] --------------- 
Enqueue(F, Dequeue (F)) F:[ d, e, f ] c 
 F:[ d, e, f , c ] --------------- 
Dequeue(F) F:[ e, f , c ] d 
Dequeue(F) F:[ f , c ] e 
Dequeue(F) P:[ c ] f 
 
 
Representação gráfica de Filas 
 
 
 
Implementação de Filas em Pascal 
 
A implementação das Filas é viável quanto temos três recursos básicos: 
→ Espaço de memória para armazenar os elementos; 
→ Uma referência ao primeiro elemento da coleção; 
→ Uma referência à primeira posição livre, após o último elemento da fila. 
 
De acordo com as características da Fila, poderemos usar: 
• um vetor para alocar o espaço de memória seqüêncial. 
• duas variáveis inteiras para referenciar o primeiro elemento e a primeira 
posição disponível no final da fila. 
 
Para ser criada uma Fila pode ser usada a estrutura RECORD: 
 
const MAX = 50; 
type Elem = char; 
 Fila = record 
 começo: integer; 
 final : integer; 
 memo : array[1..MAX] of Elem; 
 end; 
var F: Fila; 
 
 
 
Exemplo de armazenamento de uma fila F:[ a, b, c ] 
 
 
 
 
a b c d ...F: 
começo final
Filas Professor Sérgio Furgeri 
Página 3 
 
 
- Inicializar a fila, indicando que está vazia; 
- À medida que elementos são inseridos, o índice F.final se desloca para direita, 
acontecendo da mesma forma para o índice F.comeco, que indicará a próxima 
posição disponível. 
- O índice F.comeco irá sempre “perseguir” F.final, até quando a fila não conter mais 
nenhum elemento, pois teremos F.comeco igual a F.final. A seguir a representação 
de esvaziamento da fila: 
 
 
Algoritmo para Manipulação da Fila: 
 
a) Inicialização da Fila 
 
procedure Qinit(var F: Fila); 
begin 
 F.comeco:= 1; 
 F.final:= 1; 
end; 
 
Considerações: 
• Indicar o valor 1 a F.comeco e F.final deixando-os iguais e também mostrando 
que a fila está vazia e a primeira posição do vetor F.memo está disponível para 
inserção. 
• Inicia com valor 1 pois o vetor vai de 1..MAX, não podendo haver valor na 
posição 0. 
 
b) Limites da Fila 
F.comeco 
F.final 
F.memo 
F: 1 4 a b c ... 
1 2 3 4 ... max
Fila no seu estado inicial 
F: 1 4 a b c ... 
1 2 3 ... max
Removendo o elemento a 
F: 2 4 a b c ... 
1 2 3 ... max 
Removendo o elemento c 
F: 4 4 a b c ... 
1 2 3 ... max 
Removendo o elemento b 
F: 3 4 a b c ... 
1 2 3 ... max
Filas Professor Sérgio Furgeri 
Página 4 
 
function QisEmpty(var F: Fila): boolean; 
begin 
 QisEmpty:= (F.comeco = F.final); 
end; 
 
function QisFull(var F: Fila): boolean; 
begin 
 QisFull:= (F.final > max); 
end; 
 
Considerações: 
• Por que usar função no lugar de procedimento? 
• Quando a Fila está vazia? 
• Quando a Fila está cheia? 
• A passagem por referência é dada, mas não obrigatória, uma vez que não 
existe a necessidade de se alterar o valor da Fila. Entretanto, não é necessário criar 
uma nova variável para copiar a pilha na memória (quanto > MAX > Tempo) 
 
c) Inserindo elementos na Fila 
 
procedure Enqueue(var F:Fila; x: Elem); 
begin 
 if not QisFull(F) then 
 begin 
 F.memo[F.final]:=x; 
 F.final:=F.final +1; 
 end 
 else 
 writeln(‘Queue Overflow’); 
end; 
 
Considerações: 
• Há espaço para uma nova inserção? Se não, mensagem “Queue Overflow” 
• Insere um novo elemento no final da Fila. 
• Incrementa o valor do final. 
 
 
d) Retirando elementos da Fila 
 
function Dequeue(var F: Fila): Elem; 
begin 
 if not QisEmpty(F) then 
 begin 
 Dequeue:= F.memo[F.comeco]; 
 F.comeco:= F.comeco + 1; 
 end 
 else 
 writeln(“Queue Underflow”); 
end; 
 
Considerações: 
Filas Professor Sérgio Furgeri 
Página 5 
• A Fila está vazia? 
• Remover sempre do começo da Fila. 
• Retorna o elemento decrementado do começo da Fila. 
• Se tentar remover um elemento da Fila vazia, mensagem “Queue Underflow”. 
 
 
Problemas na Inplementação Seqüencial de Filas 
 
Exemplo: 
- uma determinada fila com capacidade de armazenamento de 5 elementos (max = 5). 
 
 
- Sempre que um elemento é removido, o índice que indica o começo desloca-se para 
a direita. 
- Se inicialmente ele vale 1, após todos os elementos derem sido removidos da Fila a 
situação será: 
 
 
- Onde: a função QisFull( ) indica que não há espaço livre (F.final > max) se for 
inserir um elemento e a função QisEmpty dirá que a fila está vazia (F.comeco = 
F.final) se tentarmos remover um elemento. 
- Deperdício de memória e Problemas de lógica. 
 
 
Solucionando Problemas de Implementação Seqüencial 
 
- Acrescentar uma variável que sirva de contador para saber quanto elementos 
contém a Fila. 
- Inicialmente a variável deve ser zerada. 
- Deve ser atualização sempre que for adicionado ou removido algum elemento. 
 
F: 1 6 a b c d e 
1 2 3 4 5 
Representação de um fila cheia
F: 1 6 a b c d e 
1 2 3 4 5 
Representação de um fila: está cheia ou vazia? 
1 2 3 4 5 
F: 3 2 5 a b c d 
Filas Professor Sérgio Furgeri 
Página 6 
- O desperdício de espaço pode ser sanado com uma posição prontamente disponível, 
ou seja, a posição 1 estar localizada imediatamente após a posiçao max, indicando 
que a fila está cheia e não há espaço livre conforme a representação abaixo: 
 
 
- Alocando a área de memória conforme a figura acima, um índice i com valor 
max+1 apontaria primeira posição, com valor max+2 apontaria a segunda posição e 
assim por diante, porém as células de memória são dispostas de forma linear e não 
em círculo. 
- Para isso, é necessário que sempre que for incrementado e seu valor ultrapassar a 
constante max, seu valor será definido com 1. 
 
procedure adc(var i:integer); 
 begin 
 i:= i+1; 
 if i>max then i:= 1; 
end; 
 
 
Implementação Circular para Filas 
 
Obs: 
- Note que a rotina adc, não estará disponível aos usuários em Filas.tpu, pois não está 
declarada na seção interface sendo assim exclusivamente de uso restrito da unidade. 
- Serão usadas para incremento e decremento as rotinas predefinidas pela linguagem 
Pascal, inc() e dec() respectivamente.unit Filas; 
 
interface 
 
 const max = 50; 
 type Elem = char; 
 Fila = record 
 total : integer; 
 comeco: integer; 
 final : integer; 
 memo: array[1..max] of Elem; 
 end; 
a 
b
c 
de 
1
2
3
45
6 
... 
max começo 
final 
Representação circular de uma fila 
Filas Professor Sérgio Furgeri 
Página 7 
 
 procedure Qinit(var F: Fila); 
 function QisEmpty(var F: Fila): boolean; 
 function QisFull(var F: Fila): boolean; 
 procedure Enqueue(var F: Fila) x: Elem; 
 function Dequeue(var F: Fila): Elem; 
 
implementation 
 
 procedure Qinit(var F: Fila); 
 begin 
 F.total:= 0; 
 F.comeco:= 1; 
 F.final:= 1; 
 end; 
 
 function QisEmpty(var F: Fila): boolean; 
 begin 
 QisEmpty:= (F.total = 0); 
 end; 
 
 function QisFull(var F: Fila): boolean; 
 begin 
 QisFull:= (F.total = max); 
 end; 
 
 procedure abc(var i:integer); 
 begin 
 i:= i+1; 
 if i>max then i:= 1; 
 end; 
 
 procedure Enqueue(var F:Fila; x: Elem); 
 begin 
 if not QisFull(F) then 
 begin 
 F.memo[F.final]:=x; 
 adc(F.final); 
 inc(F.total); 
 end 
 else 
 writeln(‘Queue Overflow’); 
 end; 
 
 function Dequeue(var F: Fila): Elem; 
 begin 
 if not QisEmpty(F) then 
 begin 
 Dequeue:= F.memo[F.comeco]; 
 adc(F.comeco); 
 dec(F.total); 
 end 
 else 
 writeln(‘Queue Underflow’); 
 end; 
end. 
 
 
Filas Professor Sérgio Furgeri 
Página 8 
Exercícios 
 
1. Mostre a situação de uma fila F, inicialmente vazia. Após a execução de cada uma 
das seguintes operações: 
 
Enqueue(F, a); Enqueue(F, b); Enqueue(F, c); 
Enqueue(F, d); Dequeue(F); Dequeue(F); 
Enqueue(F, e); Dequeue(F); Enqueue(F, f); 
Dequeue(F); Enqueue(F, g); Enqueue(F, Dequeue(F)); 
 
2. O impasse filavazia/cheia, na implementação circular, foi solucionado com o uso de 
uma variável contadora. Uma outra forma de resolver o problema seria impedir que 
o índice final alcançasse o índice começo, deixando sempre pelo menos uma 
posição livre entre o primeiro e o último elemento da fila. Apresente uma nova 
implementação circular para o tipo Fila que se baseie neste princípio para detectar 
fila vazia/cheia. 
 
3. Vimos que uma fila dupla é uma lista linear na qual os elementos podem ser 
inseridos ou removidos de qualquer extremo. Baseando-se na implementação 
circular apresentada para filas, codifique uma unidade de rotinas para manipulaçao 
de filas duplas. A unidade deve conter rotinas para inicializar, testar fila vazia/cheia, 
inserir à esquerda, inserir à direita, remover à esquerda e também à direita. 
 
4. Dependendo do conjunto de operações que decidimos aplicar sobre uma variável do 
tipo fila dupla, ela poderá se comportar como uma pilha ou então como uma fila. 
Isto seria vantajoso numa aplicação que precisasse usar tanto pilhas quanto filas, 
pois bastaria ter uma implementação de fila dupla. Mostre como uma fila dupla 
pode funcionar como: 
a) uma pilha 
b) uma fila 
 
5. É possível que uma única fila dupla seja utilizada para representar duas pilhas 
distintas. Admitindo que a implementação solicitada no exercício 3 esteja 
disponível, utilize as operações de fila dupla para desenvolver rotinas para 
inicializar, inserir e remover objetos destas pilhas. 
 
6. Seria possível utilizar uma fila dupla para representar duas filas simples? 
 
7. Considerando que você tem a disposição duas pilhas. Mostre como elas podem ser 
utilizadas em conjunto para simular o funcionamento de uma fila. [Dica: utilize uma 
pilha como espaço de armazenamento e a outra como espaço auxiliar para 
operações de movimentação de dados].