Estruturas de dados: fila

1. Conceitos Fundamentais da Fila

A fila é uma estrutura de dados linear que segue o princípio FIFO (First In, First Out), onde o primeiro elemento inserido é o primeiro a ser removido. Essa característica a torna ideal para situações onde a ordem de chegada determina a ordem de atendimento.

Uma analogia clássica é a fila de banco: o primeiro cliente a chegar é o primeiro a ser atendido. Outro exemplo é o buffer de impressão, onde documentos são enviados para impressão na ordem em que foram submetidos.

As operações básicas de uma fila são:
- enqueue (inserir): adiciona um elemento ao final da fila
- dequeue (remover): remove o elemento do início da fila
- front (consultar): retorna o primeiro elemento sem removê-lo

2. Implementação com Array (Fila Estática)

A implementação mais simples utiliza um array de tamanho fixo. Definimos uma estrutura com o array, índices front e rear, e um contador opcional.

#include <stdio.h>
#include <stdbool.h>
#define MAX 5

typedef struct {
    int dados[MAX];
    int front;
    int rear;
    int tamanho;
} Fila;

void criar_fila(Fila *f) {
    f->front = 0;
    f->rear = -1;
    f->tamanho = 0;
}

bool fila_vazia(Fila *f) {
    return f->tamanho == 0;
}

bool fila_cheia(Fila *f) {
    return f->tamanho == MAX;
}

bool enfileirar(Fila *f, int valor) {
    if (fila_cheia(f)) return false;
    f->rear = (f->rear + 1) % MAX;
    f->dados[f->rear] = valor;
    f->tamanho++;
    return true;
}

bool desenfileirar(Fila *f, int *valor) {
    if (fila_vazia(f)) return false;
    *valor = f->dados[f->front];
    f->front = (f->front + 1) % MAX;
    f->tamanho--;
    return true;
}

O principal problema dessa abordagem é o desperdício de espaço quando rear atinge o final do array, mesmo havendo posições livres no início. A solução é a fila circular.

3. Fila Circular com Array

Na fila circular, rear e front "dão a volta" no array usando a operação módulo. Para distinguir fila cheia de vazia, podemos usar uma posição reservada ou um contador de elementos.

#include <stdio.h>
#include <stdbool.h>
#define TAMANHO 5

typedef struct {
    int dados[TAMANHO];
    int front;
    int rear;
} FilaCircular;

void criar_fila_circular(FilaCircular *f) {
    f->front = 0;
    f->rear = 0;
}

bool fila_vazia_circular(FilaCircular *f) {
    return f->front == f->rear;
}

bool fila_cheia_circular(FilaCircular *f) {
    return (f->rear + 1) % TAMANHO == f->front;
}

bool enfileirar_circular(FilaCircular *f, int valor) {
    if (fila_cheia_circular(f)) return false;
    f->dados[f->rear] = valor;
    f->rear = (f->rear + 1) % TAMANHO;
    return true;
}

bool desenfileirar_circular(FilaCircular *f, int *valor) {
    if (fila_vazia_circular(f)) return false;
    *valor = f->dados[f->front];
    f->front = (f->front + 1) % TAMANHO;
    return true;
}

void imprimir_fila_circular(FilaCircular *f) {
    int i = f->front;
    while (i != f->rear) {
        printf("%d ", f->dados[i]);
        i = (i + 1) % TAMANHO;
    }
    printf("\n");
}

A fila circular resolve o desperdício de espaço, mas ainda tem tamanho fixo. Quando rear alcança front, a fila está cheia — uma posição fica sempre vazia para diferenciar cheia de vazia.

4. Implementação com Lista Encadeada (Fila Dinâmica)

A fila dinâmica usa nós alocados em tempo de execução, permitindo crescimento ilimitado (limitado apenas pela memória disponível).

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct No {
    int dado;
    struct No *prox;
} No;

typedef struct {
    No *front;
    No *rear;
} FilaDinamica;

void criar_fila_dinamica(FilaDinamica *f) {
    f->front = NULL;
    f->rear = NULL;
}

bool fila_vazia_dinamica(FilaDinamica *f) {
    return f->front == NULL;
}

void enqueue(FilaDinamica *f, int valor) {
    No *novo = (No*) malloc(sizeof(No));
    if (novo == NULL) return;
    novo->dado = valor;
    novo->prox = NULL;

    if (fila_vazia_dinamica(f)) {
        f->front = novo;
    } else {
        f->rear->prox = novo;
    }
    f->rear = novo;
}

bool dequeue(FilaDinamica *f, int *valor) {
    if (fila_vazia_dinamica(f)) return false;

    No *temp = f->front;
    *valor = temp->dado;
    f->front = f->front->prox;

    if (f->front == NULL) {
        f->rear = NULL;
    }

    free(temp);
    return true;
}

A inserção (enqueue) ocorre no final (rear), e a remoção (dequeue) no início (front). A memória é liberada após a remoção, evitando vazamentos.

5. Operações Auxiliares e Casos Especiais

Consultar primeiro elemento (peek):

bool peek(FilaDinamica *f, int *valor) {
    if (fila_vazia_dinamica(f)) return false;
    *valor = f->front->dado;
    return true;
}

Tamanho atual da fila (versão dinâmica):

int tamanho_fila(FilaDinamica *f) {
    int count = 0;
    No *atual = f->front;
    while (atual != NULL) {
        count++;
        atual = atual->prox;
    }
    return count;
}

Esvaziar fila dinâmica e liberar memória:

void esvaziar_fila(FilaDinamica *f) {
    No *atual = f->front;
    while (atual != NULL) {
        No *temp = atual;
        atual = atual->prox;
        free(temp);
    }
    f->front = NULL;
    f->rear = NULL;
}

6. Comparação entre Implementações

Característica Fila Estática (Array) Fila Dinâmica (Lista)
Tamanho máximo Fixo Limitado pela memória
Uso de memória Contínuo, sem overhead Overhead de ponteiros
Operações básicas O(1) O(1)
Redimensionamento Não suportado Automático
Fragmentação Não Pode ocorrer

Ambas as implementações oferecem complexidade O(1) para enqueue, dequeue e peek. A fila estática é mais rápida em acesso direto e não tem overhead de alocação, mas sofre com limitação de tamanho. A fila dinâmica é mais flexível, mas consome mais memória por nó (armazenamento do ponteiro).

7. Aplicações Práticas em C

Simulação de escalonamento Round-Robin:

Em sistemas operacionais, a fila é usada para gerenciar processos prontos para execução. Cada processo recebe um quantum de tempo e, ao final, retorna ao final da fila.

typedef struct {
    int id;
    int tempo_restante;
} Processo;

void round_robin(FilaDinamica *fila, int quantum) {
    while (!fila_vazia_dinamica(fila)) {
        Processo p;
        dequeue(fila, &p);

        if (p.tempo_restante > quantum) {
            p.tempo_restante -= quantum;
            enqueue(fila, p);
        } else {
            printf("Processo %d concluído\n", p.id);
        }
    }
}

Buffer de comunicação serial:

Em sistemas embarcados, filas armazenam caracteres recebidos via UART para processamento posterior, evitando perda de dados.

Gerenciamento de tarefas:

Em microcontroladores, filas organizam tarefas assíncronas como leitura de sensores, acionamento de atuadores e comunicação com periféricos.

A escolha entre implementação estática ou dinâmica depende do contexto: sistemas com memória limitada e tamanho conhecido favorecem arrays; sistemas que precisam de flexibilidade e crescimento dinâmico favorecem listas encadeadas.

Referências