Analise de algoritimos

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 abstrato de dados”, permite a definição abstrata dos aspectos essenciais de comportamento e funcionamento de um objeto sem definição de quaisquer aspectos de implementação. Uma fila tem por norma as seguintes funcionalidades:
Colocar e retirar dados da fila.
• add – guardar um elemento na fila
• remove – retirar um elemento da fila
• 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 efetuada através da utilização de diferentes estruturas de dados (vetores, listas ligadas, árvores, etc.).

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

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

Implementação das filas:

• usando vectores / arrays (circulares ou não)
• utilizando um apontador para nós de informação (lista ligada)

Implementação de fila com vetor
Como no caso da pilha, nossa primeira implementação de fila será feita usando um vetor para armazenar os elementos. Para isso, devemos fixar o número máximo N de elementos na fila. Podemos observar que o processo de inserção e remoção em extremidades opostas fará com que a fila “ande” no vetor. Por exemplo, se inserirmos os elementos 1.4, 2.2, 3.5, 4.0 e depois retirarmos dois elementos, a fila não estará mais nas posições iniciais do vetor.