Nesta aula estudamos o TAD Fila, a segunda estrutura especializada desta unidade. Assim como a pilha (Aula 9a), a fila restringe onde inserções e remoções podem ocorrer — mas em vez de restringir tudo a uma única ponta, ela usa duas pontas diferentes: uma para inserir, outra para remover.

1. O TAD Fila

Uma fila (queue) é uma lista em que inserções ocorrem sempre em uma extremidade (o final, ou rear) e remoções sempre na outra (a frente, ou front). Isso faz com que o primeiro elemento inserido seja sempre o primeiro a ser removido — comportamento conhecido pela sigla FIFO (First-In, First-Out).

frente                                    final
  |                                         |
  v                                         v
+-------+     +-------+     +-------+     +-------+
|   A   | --> |   B   | --> |   C   | --> |   D   |
+-------+     +-------+     +-------+     +-------+
 (sai daqui)                              (entra aqui)

A analogia mais comum é a de uma fila de banco ou de fila de impressão: quem chega primeiro é atendido primeiro; novas chegadas entram sempre no final da fila.

Operações

2. Implementação por lista encadeada

Assim como fizemos com a pilha (Aula 9a), implementamos a fila principal desta disciplina sobre uma lista encadeada, sem limite de capacidade. Diferente da pilha, porém, a fila precisa de acesso rápido às duas pontas — a mesma ideia de ListaDupla (Aula 6a), mas com nodos simplesmente encadeados:

typedef struct {
    int cod;
    char nome[50];
    float preco;
} Produto;

typedef struct str_Nodo Nodo;

struct str_Nodo {
    Nodo *prox;
    Produto dado;
};

typedef struct {
    Nodo *frente;
    Nodo *final;
} FilaEnc;

void inicializa(FilaEnc *f) {
    f->frente = NULL;
    f->final = NULL;
}

int estaVazia(FilaEnc *f) {
    return f->frente == NULL;
}

int enfileira(FilaEnc *f, Produto valor) {
    Nodo *novo = (Nodo*) malloc(sizeof(Nodo));
    if (novo == NULL)
        return 0;

    novo->dado = valor;
    novo->prox = NULL;

    if (f->final != NULL)
        f->final->prox = novo; // o antigo final passa a apontar para o novo nodo
    else
        f->frente = novo;      // fila estava vazia: novo nodo também é a frente

    f->final = novo;
    return 1;
}

int desenfileira(FilaEnc *f, Produto *valorRemovido) {
    Nodo *removido;

    if (estaVazia(f)) // underflow
        return 0;

    removido = f->frente;
    *valorRemovido = removido->dado;
    f->frente = removido->prox;

    if (f->frente == NULL) // a fila ficou vazia
        f->final = NULL;

    free(removido);
    return 1;
}

int tamanho(FilaEnc *f) {
    Nodo *aux = f->frente;
    int contador = 0;

    while (aux != NULL) {
        contador++;
        aux = aux->prox;
    }

    return contador;
}

Com os dois ponteiros (frente e final) sempre disponíveis na struct, tanto enfileira quanto desenfileira são O(1), e a fila cresce dinamicamente sem limite predefinido. Por isso adotamos esta implementação como principal para o TAD Fila.

3. Aplicações

• Fila de impressão: documentos são impressos na ordem em que chegaram.
• Escalonamento de processos: um sistema operacional pode atender processos na ordem de chegada (política FCFS, First-Come, First-Served).
• Atendimento e simulações: filas de banco, call centers, simulações de tráfego.
• Buffers de dados: comunicação entre um produtor e um consumidor que trabalham em velocidades diferentes (ex: leitura de rede, áudio/vídeo em streaming).
• Percurso em largura (BFS) em árvores e grafos: um algoritmo que veremos mais adiante na disciplina, e que usa uma fila para visitar elementos "por camadas".

Resumo

Exercícios

1. Explique, com suas próprias palavras, o que significa a sigla FIFO e como ela se relaciona com a operação desenfileira.
2. Na implementação por lista encadeada, por que é necessário verificar se f->frente == NULL após um desenfileira bem-sucedido, e atualizar f->final nesse caso?
3. Compare pilha (Aula 9a) e fila: as duas restringem onde inserções e remoções podem ocorrer, mas de formas diferentes. Explique essa diferença, e dê um exemplo de problema em que usar uma pilha no lugar de uma fila (ou vice-versa) produziria um resultado incorreto.
4. Por que enfileira e desenfileira continuam sendo O(1) mesmo a fila guardando dois ponteiros (frente e final) em vez de um só, como na pilha?
5. Implemente uma função int filaParaVetor(FilaEnc *f, Produto vetor[]) que copie os elementos da fila (da frente para o final) para vetor, sem remover nenhum elemento da fila, e retorne quantos elementos foram copiados.
6. Implemente uma função void inverterFila(FilaEnc *f) que inverta a ordem dos elementos de uma FilaEnc, utilizando uma PilhaEnc (Aula 9a) como estrutura auxiliar. Dica: desenfileire tudo empilhando, depois desempilhe enfileirando de volta.
7. Implemente uma função int filasIguais(FilaEnc *f1, FilaEnc *f2) que retorne 1 se as duas filas possuem exatamente os mesmos elementos, na mesma ordem, ou 0 caso contrário — sem alterar (nem remover elementos de) nenhuma das duas filas.
8. Implemente a fila circular por vetor. Defina a struct FilaVet, com um vetor de capacidade fixa (CAPACIDADE), um índice frente e uma quantidade qtd de elementos, e implemente inicializa, estaVazia, enfileira e desenfileira, usando o operador módulo (%) para calcular as posições. Explique por que a struct guarda qtd em vez de um índice final.

Sugestões de Respostas dos Exercícios

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

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

    return i;
}

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

    inicializa(&p);

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

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

int filasIguais(FilaEnc *f1, 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;
}

#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(FilaVet *f) {
    return f->qtd == 0;
}

int enfileira(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 desenfileira(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;
}

Código para Download

O TAD FilaEnc completo, exatamente como visto nesta aula, dividido em interface (filaEnc.h) e implementação (filaEnc.c), junto com um main.c de exemplo: