Estrutura de dados -filas

     ¨ ¦ £¡
©§¥ ¤¢

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 de dados”, 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 ou cheia. 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 (circulares ou 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 para