Filas C++

Filas

Filas
Uma fila é um conjunto ordenado de itens a partir do qual podem-se eliminar itens numa extremidade
(chamada início da fila) e no qual podem-se inserir itens na outra extremidade (chamada final da fila).
Na fila “o primeiro que entra é o primeiro que sai”
(a sigla FIFO – first in, first out – é usada para descrever essa estratégia). A ideia fundamental da fila é que só podemos inserir um novo elemento no final da fila e só podemos retirar o elemento do início.

Filas
a) insere(fila, A); insere(fila, B); insere(fila, C);
b) x = retira(fila);
c) insere(fila, D); insere(fila, E)

Filas
Operações primitivas
O arquivo fila.h, que representa a interface do tipo, pode conter as seguintes operações: typedef struct fila Fila;
Fila* cria (void); //aloca dinamicamente a estrutura de fila void insere (Fila* f, float v); /* insere novo elemento ao final da fila */ float retira (Fila* f); //retira o elemento do início int vazia (Fila* f);
//informa se a fila está ou não vazia void libera (Fila* f); /* destrói a estrutura liberando a memória alocada */

Filas

Implementação de fila com vetor

Filas
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 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.2, 3.4, 5.6 e 7.8 e depois retirarmos dois elementos a fila ficaria da seguinte forma:

2

início

4

1

1

7 fim Após inserção de quatro elementos

início

7 fim Após retirar dois elementos

Filas
Com essa estratégia, é fácil observar que, em um dado instante, a parte ocupada do vetor pode chegar à última posição. Para reaproveitar as primeiras posições livres do vetor sem implementarmos uma arrumação trabalhosa dos elementos, podemos incrementar as posições do vetor de forma “circular”: se o último elemento da fila ocupa a última