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.

1
1

enqueue(Q,1)

enqueue(Q,1)

inicio = fim 

inicio = fi...
Q
Q
Text is not SVG - cannot display
2
2
1
1

enqueue(Q,2)

enqueue(Q,2)

inicio 

inicio 
Q
Q

fim 

fim 
Text is not SVG - cannot display


3
3
2
2
1
1

enqueue(Q,3)

enqueue(Q,3)

inicio 

inicio 
Q
Q

fim 

fim 
Text is not SVG - cannot display
3
3
2
2

dequeue(Q) - devolve 1 

dequeue(Q) - devolve 1 

inicio 

inicio 
Q
Q

fim 

fim 
Text is not SVG - cannot display


4
4
3
3
2
2

enqueue(Q,4)

enqueue(Q,4)...

inicio 

inicio 
Q
Q

fim 

fim 
Text is not SVG - cannot display
4
4
3
3

dequeue(Q) – devolve 2

dequeue(Q) – devolve 2...

inicio 

inicio 
Q
Q

fim 

fim 
Text is not SVG - cannot display

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!