FIFO significa First-In, First-Out — "o primeiro a entrar é o primeiro a sair". Isso se relaciona diretamente com dequeue: essa operação sempre remove o elemento que está na fila há mais tempo (a frente), nunca o elemento inserido mais recentemente.

Porque, se a fila ficou vazia após a remoção, f->final ainda estaria apontando para o nodo que acabou de ser removido e liberado com free() — um dangling pointer (ver Material Extra — Conceitos de Linguagens de Programação). Se uma próxima chamada de enqueue tentasse usar f->final->prox = novo sem essa verificação, estaria escrevendo em um bloco de memória já liberado, um comportamento indefinido.

A pilha restringe tudo a uma única extremidade (o topo): tanto inserção quanto remoção acontecem ali, gerando o comportamento LIFO. A fila usa duas extremidades diferentes — uma para inserir (final), outra para remover (frente) — gerando o comportamento FIFO.

Um exemplo prático: em um sistema de atendimento (como uma fila de banco), usar uma pilha por engano faria com que o último cliente a chegar fosse sempre o primeiro a ser atendido, deixando os clientes mais antigos esperando indefinidamente enquanto novos clientes continuassem chegando — claramente incorreto para esse tipo de problema, que exige o comportamento FIFO de uma fila de verdade.

Porque tanto enqueue quanto dequeue continuam operando sobre um único ponteiro por vez, sem percorrer a lista: enqueue só lê e escreve em f->final, e dequeue só lê e escreve em f->frente. Ter dois ponteiros na struct, em vez de um, não significa que uma operação precise mexer nos dois ao mesmo tempo em todos os casos (exceto quando a fila está vazia ou fica vazia) — cada ponteiro atende a uma ponta, de forma independente.

int filaParaVetor(const FilaEnc *f, Produto vetor[]) {
    Nodo *aux = f->frente;
    int i = 0;

    while (aux != NULL) {
        vetor[i] = aux->dado;
        i++;
        aux = aux->prox;
    }

    return i;
}

Basta percorrer a lista com um ponteiro auxiliar, do mesmo jeito que já fazíamos em imprime (Aula 4) — sem alterar f->frente nem remover nenhum nodo, a fila permanece intacta após a chamada.

void inverterFila(FilaEnc *f) {
    PilhaEnc p;
    Produto valor;

    inicializa(&p);

    // esvazia a fila, empilhando cada elemento removido
    while (!estaVazia(f)) {
        dequeue(f, &valor);
        push(&p, valor);
    }

    // desempilha de volta para a fila, já na ordem inversa
    while (!estaVazia(&p)) {
        pop(&p, &valor);
        enqueue(f, valor);
    }
}

Como a pilha inverte a ordem (LIFO) e a fila preserva a ordem de entrada (FIFO), o truque é usar a pilha como uma etapa intermediária: tudo que sai da fila em uma ordem, entra na pilha e sai dela na ordem inversa — que é justamente o que queremos ao devolver os elementos para a fila.

int filasIguais(const FilaEnc *f1, const FilaEnc *f2) {
    Nodo *aux1 = f1->frente;
    Nodo *aux2 = f2->frente;

    while (aux1 != NULL && aux2 != NULL) {
        // structs não podem ser comparadas com "!=" em C; comparamos campo a campo
        if (aux1->dado.cod != aux2->dado.cod)
            return 0;
        aux1 = aux1->prox;
        aux2 = aux2->prox;
    }

    // iguais somente se as duas terminaram ao mesmo tempo (mesmo tamanho)
    return aux1 == NULL && aux2 == NULL;
}

Usamos dois ponteiros auxiliares, um para cada fila, avançando os dois em paralelo. Como dado é um Produto (uma struct), não podemos compará-lo diretamente com != — por simplicidade, comparamos apenas o campo cod, assumindo que ele identifica o produto de forma única. Se em algum momento os códigos diferirem, as filas já não são iguais. Ao final, é preciso conferir se ambos os ponteiros chegaram a NULL ao mesmo tempo — se um deles ainda tiver elementos e o outro não, as filas têm tamanhos diferentes e não podem ser iguais.

#define CAPACIDADE 5

typedef struct {
    Produto dados[CAPACIDADE];
    int frente;
    int qtd; // quantidade de elementos atualmente na fila
} FilaVet;

void inicializa(FilaVet *f) {
    f->frente = 0;
    f->qtd = 0;
}

int estaVazia(const FilaVet *f) {
    return f->qtd == 0;
}

int enqueue(FilaVet *f, Produto valor) {
    int posicaoFinal;

    if (f->qtd == CAPACIDADE) // overflow
        return 0;

    posicaoFinal = (f->frente + f->qtd) % CAPACIDADE; // "dá a volta" no vetor
    f->dados[posicaoFinal] = valor;
    f->qtd++;
    return 1;
}

int dequeue(FilaVet *f, Produto *valorRemovido) {
    if (estaVazia(f)) // underflow
        return 0;

    *valorRemovido = f->dados[f->frente];
    f->frente = (f->frente + 1) % CAPACIDADE; // "dá a volta" também aqui
    f->qtd--;
    return 1;
}

A struct guarda qtd em vez de um índice final porque, em uma fila circular, a condição frente == final seria ambígua: poderia significar tanto "fila vazia" quanto "fila cheia" (quando o índice deu a volta inteira no vetor e coincidiu de novo com frente). Guardar a quantidade de elementos diretamente resolve essa ambiguidade: fila vazia é qtd == 0, fila cheia é qtd == CAPACIDADE, independente da posição relativa dos índices.

Com apenas um ponteiro para o início (frente), enqueue precisaria percorrer a fila inteira até o último nodo para encaixar o novo elemento — O(n). Com apenas um ponteiro para o final (final), dequeue não conseguiria avançar para o segundo elemento sem percorrer a lista a partir do início — ou seria impossível sem um ponteiro para o início. Em listas simplesmente encadeadas, a única forma de ter ambas as operações O(1) é manter dois ponteiros.

Porque cada operação mexe em apenas um ponteiro por vez em quase todos os casos: enqueue só lê e escreve em f->final, e dequeue só lê e escreve em f->frente. Os dois ponteiros só precisam ser atualizados juntos nas situações excepcionais: quando a fila estava vazia antes de um enqueue (o novo nodo é ao mesmo tempo frente e final), ou quando a fila fica vazia após um dequeue (é preciso zerar também f->final). Fora desses casos, as operações são independentes — daí o O(1).

Após o último dequeue, f->frente passa a ser NULL (fila vazia), mas f->final ainda aponta para o nodo que acabou de ser removido e liberado com free(). Esse é um dangling pointer: um ponteiro que aponta para memória já devolvida ao sistema operacional. Se enqueue for chamado em seguida, a condição if (f->final != NULL) é verdadeira (o ponteiro não é NULL, apenas inválido), então f->final->prox = novo escreve em um bloco já liberado — comportamento indefinido que pode corromper silenciosamente outras alocações ou causar segmentation fault.

Na variante que desloca: ao remover o primeiro elemento, todos os demais precisam ser movidos uma posição para a esquerda para que frente fique sempre no índice 0 — isso custa O(n) por dequeue.
Na variante que apenas avança o índice: dequeue é O(1), mas o espaço da posição 0 fica para sempre inutilizado. Após k remoções, as primeiras k posições do vetor são espaço desperdiçado; mesmo que a fila contenha poucos elementos, as novas inserções podem ser recusadas por "overflow" quando o índice final alcança o fim do vetor — mesmo havendo espaço livre no início. A fila circular (aritmética modular) resolve esse problema.

A pilha inverte a ordem de entrada; a fila a preserva. Isso ilustra diretamente porque a pilha é útil para "desfazer" operações (saída na ordem inversa) e a fila é útil para escalonamento justo por ordem de chegada.

Uma fila com prioridade é preferível quando a ordem de atendimento não depende apenas da chegada, mas de uma chave de prioridade. Exemplo concreto: escalonamento de processos em sistemas operacionais modernos — processos de baixa latência (leitura de teclado) devem ser atendidos antes de processos de processamento intensivo em lote (renderização de vídeo), independentemente de quem chegou primeiro. Com FIFO puro, um processo pesado que chegou antes bloquearia todos os mais leves que chegaram depois.

Produto jogoHotPotato(Produto pessoas[], int n, int k) {
    FilaEnc f;
    Produto p;
    int i, j;
    inicializa(&f);

    for (i = 0; i < n; i++)
        enqueue(&f, pessoas[i]);

    while (tamanho(&f) > 1) {
        for (j = 0; j < k - 1; j++) { // passa k-1 vezes
            dequeue(&f, &p);
            enqueue(&f, p);
        }
        dequeue(&f, &p); // elimina quem segurou a batata
    }

    frente(&f, &p);
    return p;
}

int ehPalindromo(char *str, int n) {
    FilaEnc f;
    PilhaEnc p;
    Produto c, da_fila, da_pilha;
    int i;
    inicializa(&f);
    inicializa(&p);

    for (i = 0; i < n; i++) {
        c.cod = str[i];
        enqueue(&f, c);
        push(&p, c);
    }

    for (i = 0; i < n; i++) {
        dequeue(&f, &da_fila);
        pop(&p, &da_pilha);
        if (da_fila.cod != da_pilha.cod)
            return 0;
    }

    return 1;
}

A fila retorna os caracteres na ordem original (FIFO); a pilha na ordem inversa (LIFO). Se todos os pares coincidirem, a string é palíndromo.

void intercalar(FilaEnc *f1, FilaEnc *f2, FilaEnc *resultado) {
    Produto p;

    while (!estaVazia(f1) && !estaVazia(f2)) {
        dequeue(f1, &p); enqueue(resultado, p);
        dequeue(f2, &p); enqueue(resultado, p);
    }

    while (!estaVazia(f1)) { dequeue(f1, &p); enqueue(resultado, p); }
    while (!estaVazia(f2)) { dequeue(f2, &p); enqueue(resultado, p); }
}

void dividirFila(FilaEnc *f, FilaEnc *pares, FilaEnc *impares) {
    Produto p;

    while (!estaVazia(f)) {
        dequeue(f, &p);
        if (p.cod % 2 == 0)
            enqueue(pares, p);
        else
            enqueue(impares, p);
    }
}

FilaEnc copiarFila(FilaEnc *f) {
    FilaEnc aux, copia;
    Produto p;
    inicializa(&aux);
    inicializa(&copia);

    // esvazia f em aux, construindo copia ao mesmo tempo
    while (!estaVazia(f)) {
        dequeue(f, &p);
        enqueue(&aux, p);
        enqueue(&copia, p);
    }

    // restaura f a partir de aux
    while (!estaVazia(&aux)) {
        dequeue(&aux, &p);
        enqueue(f, p);
    }

    return copia;
}

int simularAtendimento(FilaEnc *fila, int *tempoTotalEspera) {
    Produto cliente;
    int tempoAtual = 0;
    int contagem = 0;
    *tempoTotalEspera = 0;

    while (!estaVazia(fila)) {
        dequeue(fila, &cliente);
        *tempoTotalEspera += tempoAtual; // espera = momento em que começa a ser atendido
        tempoAtual += cliente.cod;       // duração do atendimento deste cliente
        contagem++;
    }

    return contagem;
}

Exemplo: 3 clientes com durações [4, 2, 3]. Esperas: 0 (1º começa imediatamente) + 4 (2º espera o 1º) + 6 (3º espera os dois anteriores) = 10. Tempo médio de espera: 10/3 ≈ 3,33.