Fila

Fila

1. Estrutura FIFO(first in, first out)

2. Os elementos são utilizados sequencialmente na ordem que são armazenados.

3. Novos elementos são armazenados no final da fila.

4. Tem marcadores de início e de fim.

5. Métodos

   • isFull
     • Verificar se a fila está cheia.
   • isEmpty
     • Verificar se a fila está vazia.
       • Se inicio e/ou fim estiverem apontando para -1(estática).
   • Size
     • Verificar e retornar o tamanho da fila.
       • Estática: apontador fim -1; Dinâmica: fazer um contador ou percorrer toda a estrutura contando.
   • Enqueue (Enfileirar)
     • Adicionar um elemento a fila.
       • Consiste em inserir um elemento no final da fila e atualizar a posição dos marcadores da fila .
         • Se a fila for estática, verificar se ela não está cheia.
         • Se ela estiver vazia, adicionar como primeiro elemento e inicio e fim apontam para tal elemento.
         • Se não estiver vazia, adiciona o elemento depois do último e acrescenta o fim.
   • Dequeue (Desenfileirar)
     • Se a fila for estática, verificar se ela não está vazia.
     • Consistem em remover o elemento do início da fila.
       • Se inicio e fim marcarem o mesmo elemento(que aponta apenas um elemento na fila, remove este e inicio e fim passam a ser -1.)
         • Caso contrário, remove o elemento do início e incrementa início.
           • Fazer a reorganização da fila, fazendo os elementos "andarem um para frente".
       • O elemento é retornado.
   • Front (Peek)
     • Retorna o primeiro valor da fila.
       • Não precisa de parâmetros.

6. Fila circular

   • Evita ter que fazer a reorganização da fila.
     • As posições do primeiro e do último elemento são definidas dinamicamente.
       • O primeiro elemento da fila inicialmente ocupa a posição 0, e à medida que elementos são desenfileirados o início passa a ser a posição seguinte. As posições disponíveis são ocupadas com novas inserções e, desta maneira, quando a última posição do vetor está ocupada, mas existem posições disponíveis, o ciclo de preenchimento volta para a posição 0.
         • Pode-se criar uma variável qtd,a qual é incrementada ou decrementada a medida que inserem-se ou removem-se elementos da fila.
           • Assim , para criar a fila faça : – fim = primeiro = qtd = 0; Para verificar se a fila está cheia faça : – Se qtd = m então fila cheia; Para verifica se a fila está vazia faça : – Se qtd == 0 então fila vazia;
       • Início e fim são deslocados de acordo com as operações realizadas.