Filas (Queues)

Filas são estruturas de dados do tipo FIFO (First In, First Out), onde o primeiro elemento inserido é o primeiro a ser removido. São fundamentais em sistemas de controle de processos, buffers de comunicação e gerenciamento de tarefas.

Fila Linear

• Implementada com vetores ou listas ligadas.
• Inserções no final (enqueue) e remoções no início (dequeue).
• Em implementações estáticas, pode haver desperdício de memória após várias remoções.

Exemplo de Fila Linear Dinâmica

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

// Estrutura de um nó da fila
typedef struct Node {
  int dado;
    struct Node* proximo;
} Node;

// Estrutura da fila
typedef struct Fila {
  Node* frente;
    Node* tras;
} Fila;

// Inicializa a fila
void inicializarFila(Fila* f) {
  f->frente = NULL;
  f->tras = NULL;
}

// Verifica se a fila está vazia
int estaVazia(Fila* f) {
  return (f->frente == NULL);
}

// Enfileirar (inserir no final)
void enfileirar(Fila* f, int valor) {
  Node* novo = (Node*)malloc(sizeof(Node));
  novo->dado = valor;
  novo->proximo = NULL;

  if (f->tras == NULL) {
    f->frente = novo;
    f->tras = novo;
  } else {
    f->tras->proximo = novo;
    f->tras = novo;
  }
}

// Desenfileirar (remover do início)
int desenfileirar(Fila* f) {
  if (estaVazia(f)) {
    printf("Fila vazia!\n");
      return -1;
    }

    Node* temp = f->frente;
    int valor = temp->dado;

    f->frente = f->frente->proximo;
    if (f->frente == NULL) {
      f->tras = NULL;
    }

    free(temp);
    return valor;
}

// Exibe os elementos da fila
void exibirFila(Fila* f) {
  Node* atual = f->frente;
  printf("Fila: ");
  while (atual != NULL) {
    printf("%d ", atual->dado);
      atual = atual->proximo;
  }
  printf("\n");
}

// Exemplo de uso
int main() {
  Fila f;
  inicializarFila(&f);

  enfileirar(&f, 10);
  enfileirar(&f, 20);
  enfileirar(&f, 30);
  exibirFila(&f);

  printf("Desenfileirado: %d\n", desenfileirar(&f));
  exibirFila(&f);

  return 0;
}

Fila Circular

É uma variação da fila linear em que o final da estrutura se conecta ao início, formando um ciclo.

Características:

• Evita desperdício de memória ao reutilizar espaços liberados.
• Ideal para sistemas embarcados, buffers de comunicação serial (UART), controle de tarefas em tempo real e automação de processos com ciclos contínuos.
• Implementada com vetores, usando dois índices:
  • inicio: posição do primeiro elemento.
  • fim: posição da próxima inserção.
• Os índices são atualizados usando aritmética modular.

Vantagens:

• Uso eficiente da memória.
• Operações com complexidade constante: \( \mathcal{O}(1) \).
• Aplicável em sistemas com tempo real, como:
  • Filas de leitura de sensores;
  • Controle de produção em linha;
  • Sistemas de aquisição de dados contínuos.

Exemplo de Fila Circular Estática

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

#define TAMANHO 5  // Capacidade da fila

typedef struct {
  int dados[TAMANHO];
  int inicio;
  int fim;
  int contador;
} FilaCircular;

// Inicializa a fila
void inicializarFila(FilaCircular* f) {
  f->inicio = 0;
  f->fim = 0;
  f->contador = 0;
}

// Verifica se está cheia
int estaCheia(FilaCircular* f) {
  return f->contador == TAMANHO;
}

// Verifica se está vazia
int estaVazia(FilaCircular* f) {
  return f->contador == 0;
}

// Enfileira elemento
int enfileirar(FilaCircular* f, int valor) {
  if (estaCheia(f)) {
    printf("Fila cheia!\n");
    return 0;
  }

  f->dados[f->fim] = valor;
  f->fim = (f->fim + 1) % TAMANHO;  // Volta ao início se atingir o fim
  f->contador++;
  return 1;
}

// Desenfileira elemento
int desenfileirar(FilaCircular* f, int* valor) {
  if (estaVazia(f)) {
    printf("Fila vazia!\n");
    return 0;
  }

  *valor = f->dados[f->inicio];
  f->inicio = (f->inicio + 1) % TAMANHO;
  f->contador--;
  return 1;
}

// Exibe a fila
void exibirFila(FilaCircular* f) {
  printf("Fila: ");
  if (estaVazia(f)) {
    printf("(vazia)\n");
    return;
  }

  int i = f->inicio;
  for (int j = 0; j < f->contador; j++) {
    printf("%d ", f->dados[i]);
    i = (i + 1) % TAMANHO;
  }
  printf("\n");
}

// Exemplo de uso
int main() {
  FilaCircular fila;
  inicializarFila(&fila);

  enfileirar(&fila, 10);
  enfileirar(&fila, 20);
  enfileirar(&fila, 30);
  enfileirar(&fila, 40);
  enfileirar(&fila, 50);
  exibirFila(&fila);

  int valor;
  desenfileirar(&fila, &valor);
  printf("Desenfileirado: %d\n", valor);

  enfileirar(&fila, 60);  // Deve reutilizar o espaço liberado
  exibirFila(&fila);

  return 0;
}

Comparando os tipos de filas

Considerações para Implementação

• Deve-se reservar uma posição extra ou usar uma variável auxiliar para distinguir entre fila cheia e vazia.
• Pode ser implementada de forma estática (com vetor fixo) ou dinâmica (com ponteiros e alocação), conforme os recursos do sistema.

Filas circulares são frequentemente utilizadas em sistemas industriais com recursos limitados e exigência de desempenho previsível — um cenário comum na Engenharia de Controle e Automação.