Na fila “o primeiro que entra é o primeiro que sai” (a sigla FIFO - first in, first out – é usada para descrever essa estratégia).
A idéia fundamental da fila é que só podemos inserir um novo elemento no final da fila, e só podemos retirar o elemento do início.
Poderíamos citar exemplos durante horas, devido às aplicações existentes no mundo real:
- Fila de Banco;
- Fila de carros num estacionamento;
- Fila de impressão;
- Fila de processos num Sistema Operacional (envolve prioridades…)
Existem duas operações básicas que devem ser implementadas numa estrutura fila:
- a operação para inserir um novo elemento, inserindo-o no fim (enqueue);
- a operação para retirar um elemento, removendo-o do início (dequeue).
Ilustração do funcionamento conceitual de uma fila Q.
Conjunto de valores:
- Elementos quaisquer a ser perfilados.
Operações Básicas:
- ENQUEUE: Insere um elemento.
- DEQUEUE: Remove um elemento.
- VAZIA: Verifica se a fila está vazia.
Assim como em pilhas, há várias implementações possíveis de uma fila.
Vamos ver primeiramente uma implementação em que sabemos o limite da fila, e utilizaremos um vetor.
Estrutura básica de uma Fila:
typedef struct {
int inicio;
int fim;
int dados[50];
} Fila;
Operação Vazia:
int empty(Fila *f) {
return (f->inicio > f->fim);
}
Operação ENQUEUE:
void enqueue(Fila *f, int x) {
if(f->fim == (max-1)) {
printf("\n Fila Cheia!\n");
} else {
f->fim++;
f->dados[f->fim] = x;
}
}
Operação DEQUEUE:
int dequeue(Fila *f) {
int removido;
if(empty(f)) {
printf("\n\n Fila Vazia!!!\n\n");
} else {
removido = f->dados[f->inicio];
f->inicio++;
return removido;
}
}
Um grande abraço e até o próximo post!