Estrutura de dados -filas

Disponível somente no TrabalhosFeitos
  • Páginas : 8 (1951 palavras )
  • Download(s) : 0
  • Publicado : 15 de maio de 2012
Ler documento completo
Amostra do texto
     ¨ ¦ £¡
©§¥ ¤¢ 

1. Filas
Uma Fila é uma estrutura de dados do tipo FIFO (First In First Out), cujo funcionamento é
inspirado no de uma fila “natural”, na qual o primeiro elemento a ser inserido é sempre o
primeiro elemento a ser retirado. Um exemplo de uma fila é o caso de uma “fila de
supermercado”.

1.1. Método
A implementação de uma fila como um “tipo abstracto dedados”, permite a definição
abstracta dos aspectos essenciais de comportamento e funcionamento de um objecto sem
definição de quai quer aspectos de implementação. Uma fila tem por norma as seguintes
funcionalidade:
Colocar e retirar dados da fila.
add – guardar um elemento na fila
remove – retirar um elemento da fil
top – retornar o elemento do topo da fila
Testar se a fila está vazia oucheia.
full – Verificar se a fila está cheia (não pode guardar mais elementos).
empty – Verificar se a fila está vazia (não contém elementos)
Inicializar ou limpar:
construct – Colocar a fila num estado “pronto” a ser utilizada
A implementação de uma fila pode ser efectuada através da utilização de diferentes
estruturas de dados (vectores, listas ligadas, árvores, etc.). De seguida,apresenta-se duas
implementação de uma fila através da utilização de vectores e listas ligadas.
B
B
B
B
B

B

Características das filas:
Os dados são armazenados pela ordem de entrada
C

Tipos de filas:
Filas de espera (queues)
o com duplo fim (deque “double-ended queue)
Filas de espera com prioridades (priority queues)
C
C

Implementação das filas:
usando vectores / arrays (circularesou não)
utilizando um apontador para nós de informação (lista ligada)
C
C

1 de 10

¥ ¡ ! @
#A$$)

99 387¥ 5¥1!31) ' ¦ !¥ ! ¡
§(§$§6"4(&%$#¢" 

S R Q R Q PI H FE
©§G ¤¢D

2. Filas de espera
2.1. Implementação em C++ usando arrays
2.1.1. Fila usando arrays
Vantagens:
Facilidade de implementação.
f

Desvantagens:
Vectores possuem um espaço limitado paraarmazenamento de dados.
Necessidade de definir um espaço grande o suficiente para a fila.
Necessidade de um indicador para o inicio e para o fim da fila.
f
f
f

Método de Implementação:
A adição de elementos à fila resulta no incremento do indicador do fim da fila
A remoção de elementos da fila resulta no incremento do indicador do inicio da
fila
Logicamente, assim, obtém-serapidamente falta de espaço na fila para a inserção de
mais elementos! Solução?
f
f

Soluções comuns:
Juntar os elementos sempre à esquerda, cada vez que se faz u a remoção! (NÃO)
“Imaginar” o array como sendo um array circular, isto é, unir o fim do array ao
inicio da array! ( Melhor Implementação)
f
f

2.1.2. Fila usando “array circular”
0

1

2

3

4

5

6

7

8

9Estruturas de dados necessárias:
Indicador do in cio da fila “ inicio”
Indicar do fim da fila fim”
Espaço para armazenar os elementos da fila dados“
Quantidade máxima de elementos da fila MAXFILA”
f
f
f
f

Depois de estabelecido as necessidades estruturas de dados para a sua implementação,
apresenta-se o modo de funcionamento:
Inicialmente a fila encontra-se vazia, o que quer dizer que:inicio = = 0
fim = = 0
f

f
f

2 de 10

G UE V e
#A$$X

dd `cbG aGYV`YX RW HU RVGQ V E
§(§$§6"4(&%$#¢"U T

v u t u t sr q ih
©§p ¤¢g
Isto é, a fila encontra-se vazia quando inicio == fim
‰

Depois de adicionar e remover alguns elementos (ex.: adicionar 10, remover 2,
adicionar 2 elementos), a fila encontra-se cheia, donde obtém-se que:
Inicio = = 2 (10 + 2,porque temos uma lista circular)
Fim = = 2 (número de elementos removidos)
Isto é, a fila encontra-se cheia quando inicio == fim
‰
‰

PROBLEMA:

Como distinguir entre fila cheia e fila vazia????

Soluções comuns:
Manter sempre uma posição vazia no array entre o indicador de inicio e o
indicador de fim, obrigando a definir uma capacidade de MAXFILA+1” para se
obter uma capacidade de...
tracking img