Programação Tutorial , , ,

Conceitos, operações e implementações de filas

Uma fila (queue) é uma estrutura de dados linear utilizada para armazenar elementos segundo uma ordem específica de entrada e saída. Sua característica fundamental é que o elemento inserido primeiro tende a ser também o primeiro elemento removido. Essa política é conhecida como First In, First Out (FIFO), ou “primeiro a entrar, primeiro a sair” (Cormen et al., 2012).

Esse comportamento aparece naturalmente em diferentes sistemas computacionais: filas de impressão, processamento de requisições, escalonamento de tarefas, buffers de comunicação e sistemas de atendimento. Martins (2009), por exemplo, apresenta filas estáticas e dinâmicas e emprega como aplicação justamente um sistema de controle de senhas de atendimento.

Neste artigo, utilizaremos como cenário uma clínica médica. Quando pacientes chegam à recepção, recebem uma senha e entram em uma fila. Desconsiderando prioridades médicas por enquanto, o paciente que chegou primeiro deverá ser atendido primeiro.

O que são filas?

Como dissemos, uma fila é uma estrutura linear na qual as inserções e remoções acontecem em extremidades diferentes. Novos elementos entram no fim da fila, enquanto a remoção ocorre no início da fila (Cormen et al., 2012).

Em nosso cenário, considere três pacientes chegando à clínica nesta ordem:

Ana → Bruno → Carla

Depois das três chegadas, podemos representar a fila da seguinte maneira:

INÍCIO              FIM
  ↓                  ↓
[Ana] → [Bruno] → [Carla]

Quando o médico chama o próximo paciente, Ana é removida:

INÍCIO      FIM
  ↓          ↓
[Bruno] → [Carla]

Se Diego chegar posteriormente, ele entra no fim da fila, após a paciente Carla:

INÍCIO                FIM
  ↓                    ↓
[Bruno] → [Carla] → [Diego]

Portanto, a fila não permite escolher arbitrariamente qual elemento será retirado quando se deseja preservar sua semântica tradicional. A ordem de atendimento decorre da própria organização da estrutura.

Operações primitivas de uma fila

Uma fila pode ser entendida como um Tipo Abstrato de Dados — TAD. Um TAD estabelece um conjunto de dados e as operações permitidas sobre eles, independentemente da forma concreta utilizada para armazená-los (Ziviani, 2007).

As operações fundamentais de uma fila são as seguintes.

Enfileirar (Enqueue)

Insere um novo elemento no fim da fila.

Inicialmente a fila é composta por:

Ana → Bruno


Em seguida, chega a Carla e a fila fica:

Ana → Bruno → Carla

Desenfileirar (Dequeue)

Remove o elemento localizado no início da fila.

A fila é composta por:

Ana → Bruno → Carla


Após atender Ana, fica:

Bruno → Carla

Consultar o primeiro elemento

Também podemos consultar o paciente que será atendido sem removê-lo.

Fila:

Ana → Bruno → Carla

Neste exemplo, a consulta retorna:

Ana

Essa operação costuma aparecer com os nomes de:

front
peek
first

Em português, podemos chamara a função de:

consultarPrimeiro(...)

Verificar se a fila está vazia

Antes de remover ou consultar um elemento, é necessário verificar se existe algum elemento armazenado.

filaVazia(...)

Tentar retirar um elemento de uma fila vazia caracteriza uma condição conhecida como underflow.

Verificar se a fila está cheia

Essa operação é particularmente importante em implementações com tamanho fixo:

filaCheia(...)

Se um vetor comporta cinco pacientes e as cinco posições disponíveis já estão ocupadas, uma nova inserção não pode ser realizada sem tratamento apropriado. Essa condição é denominada overflow.

Implementação de filas

A política FIFO é independente da maneira como os elementos são armazenados. Uma fila pode ser construída utilizando diferentes representações.

Martins (2009) apresenta tanto implementação estática quanto dinâmica de filas e relaciona a abordagem dinâmica ao uso de ponteiros. Neste artigo estudaremos duas formas particularmente importantes:

Fila circular com vetor
Fila dinâmica com nós encadeados

A expressão fila dinâmica normalmente se refere justamente a uma fila construída com nós ligados por ponteiros. Portanto, “fila dinâmica” e “fila com nós” não constituem necessariamente duas estruturas diferentes; são duas formas de descrever a mesma estratégia de implementação.

Filas estáticas e o problema do vetor linear

Imagine inicialmente um vetor com cinco posições:

Índice:     0       1       2       3       4

          [Ana] [Bruno] [Carla] [     ] [     ]
            ↑              ↑
          início          fim

Depois do atendimento de Ana e Bruno:

Índice:     0       1       2       3       4

          [     ] [     ] [Carla] [     ] [     ]
                            ↑
                          início

As primeiras posições estão livres, mas simplesmente deslocar todos os elementos para a esquerda após cada remoção seria desnecessário e produziria custo adicional.

Uma solução mais eficiente é tratar o vetor como uma estrutura circular.

Fila circular

Em uma fila circular, após a última posição do vetor, considera-se que a próxima posição é novamente a primeira.

Para um vetor de cinco posições:

0 → 1 → 2 → 3 → 4
↑                 ↓
└─────────────────┘

Essa técnica permite reutilizar posições que foram liberadas anteriormente. Cormen et al. (2012) apresentam precisamente essa representação circular de filas utilizando um arranjo, mantendo indicadores para início e fim.

Uma forma simples de calcular a próxima posição é utilizar o operador módulo:

fim = (fim + 1) % CAPACIDADE;

Se:

fim = 3
CAPACIDADE = 5

então:

(3 + 1) % 5 = 4

A próxima posição será 4.

Se:

fim = 4

teremos:

(4 + 1) % 5 = 0

O índice retorna ao início do vetor.

Essa é a essência da circularidade.

Controle de uma fila circular

Uma implementação didática pode manter três variáveis:

int inicio;
int fim;
int quantidade;

de forma que:

  • inicio indica onde está o próximo elemento que deverá sair.
  • fim indica a próxima posição disponível para inserção.
  • quantidade registra quantos elementos estão atualmente armazenados.

Assim:

quantidade == 0

significa fila vazia.

Enquanto:

quantidade == CAPACIDADE

significa fila cheia.

Esse terceiro contador simplifica um problema clássico: sem alguma convenção adicional, inicio == fim poderia significar tanto uma fila vazia quanto uma fila completamente preenchida.

Filas dinâmicas e filas com nós

Uma alternativa ao vetor consiste em criar os elementos dinamicamente conforme eles chegam. Martins (2009) caracteriza essa abordagem pelo uso de ponteiros, fazendo com que sua capacidade deixe de depender de um vetor previamente dimensionado e passe a depender essencialmente da memória disponível.

Cada elemento da fila pode ser representado por um nó:

+------------------+-----------+
| Paciente         | Próximo   |
+------------------+-----------+

Imagine:

inicio
  ↓
[Ana | •] → [Bruno | •] → [Carla | nullptr]
                                      ↑
                                     fim

Cada nó possui os dados de um paciente e um ponteiro para o próximo nó.

Podemos representar isso em C++ com:

struct No {
    Paciente paciente;
    No* proximo;
};

Além disso, a estrutura da fila mantém dois ponteiros:

struct FilaDinamica {
    No* inicio;
    No* fim;
};

Assim, o ponteiro inicio permite localizar rapidamente o próximo paciente, enquanto o ponteiro fim permite inserir rapidamente um novo paciente.

Esse detalhe é fundamental, pois se mantivéssemos apenas o ponteiro para inicio, seria necessário percorrer todos os nós até encontrar o último sempre que um paciente chegasse. Isso gastaria bastante recurso computacional dependendo do tamanho da fila. Com ambos os ponteiros na struct, enfileirar e desenfileirar podem ser operações do tipo O(1).

Inserção em uma fila dinâmica

Suponha inicialmente:

Ana → Bruno

onde fim aponta para Bruno. Então, chega a Carla. Primeiro, cria-se um novo nó:

[Carla | nullptr]

Depois, o antigo último nó passa a apontar para Carla:

Ana → Bruno → Carla

Finalmente:

fim = Carla

Um caso especial ocorre quando o primeiro paciente é inserido. Como não existia nenhum nó anteriormente:

inicio = novo;
fim = novo;

Assim, o único elemento é simultaneamente o primeiro e o último da fila.

Remoção em uma fila dinâmica

Considere:

inicio
  ↓
[Ana] → [Bruno] → [Carla]
                     ↑
                    fim

Para atender Ana, guardamos temporariamente seu endereço:

No* removido = fila.inicio;

Depois fazemos o início avançar:

fila.inicio = fila.inicio->proximo;

Obtendo:

inicio
  ↓
[Bruno] → [Carla]
             ↑
            fim

Finalmente, a memória do nó removido deve ser liberada:

delete removido;

Lembrando que esse último passo é essencial em C++, pois objetos criados dinamicamente com new devem ser liberados quando não forem mais necessários.

Um caso especial importante: a retirada do último elemento

Considere uma fila contendo somente Ana:

inicio
  ↓
[Ana]
  ↑
 fim

Após sua remoção:

inicio = nullptr

Nesse momento, fim também deve ser atualizado:

fila.fim = nullptr;

Caso contrário, fim permaneceria apontando para uma região de memória que já foi liberada.

Esse tipo de referência inválida é conhecido como dangling pointer e pode causar comportamento indefinido no programa.

Implementação completa em C++17

O programa a seguir reúne os conceitos discutidos em um único arquivo. A função main() demonstra tanto uma fila circular estática quanto uma fila dinâmica com nós, utilizando o cenário de pacientes de uma clínica médica.

#include <iostream>
#include <string>

using namespace std;

const int CAPACIDADE = 5;

struct Paciente {
    int senha;
    string nome;
};

// ======================================================
// FILA CIRCULAR
// ======================================================

struct FilaCircular {
    Paciente dados[CAPACIDADE];

    int inicio = 0;
    int fim = 0;
    int quantidade = 0;
};

bool filaCircularVazia(const FilaCircular& fila) {
    return fila.quantidade == 0;
}

bool filaCircularCheia(const FilaCircular& fila) {
    return fila.quantidade == CAPACIDADE;
}

bool enfileirarCircular(
    FilaCircular& fila,
    Paciente paciente
) {
    if (filaCircularCheia(fila)) {
        return false;
    }

    fila.dados[fila.fim] = paciente;

    fila.fim =
        (fila.fim + 1) % CAPACIDADE;

    fila.quantidade++;

    return true;
}

bool desenfileirarCircular(
    FilaCircular& fila,
    Paciente& paciente
) {
    if (filaCircularVazia(fila)) {
        return false;
    }

    paciente =
        fila.dados[fila.inicio];

    fila.inicio =
        (fila.inicio + 1) % CAPACIDADE;

    fila.quantidade--;

    return true;
}

bool consultarPrimeiroCircular(
    const FilaCircular& fila,
    Paciente& paciente
) {
    if (filaCircularVazia(fila)) {
        return false;
    }

    paciente =
        fila.dados[fila.inicio];

    return true;
}

void mostrarFilaCircular(
    const FilaCircular& fila
) {
    cout << "Fila circular: ";

    if (filaCircularVazia(fila)) {
        cout << "vazia" << endl;
        return;
    }

    for (
        int i = 0;
        i < fila.quantidade;
        i++
    ) {
        int posicao =
            (fila.inicio + i)
            % CAPACIDADE;

        cout
            << fila.dados[posicao].senha
            << " - "
            << fila.dados[posicao].nome;

        if (i < fila.quantidade - 1) {
            cout << " | ";
        }
    }

    cout << endl;
}

// ======================================================
// FILA DINAMICA COM NOS
// ======================================================

struct No {
    Paciente paciente;
    No* proximo;
};

struct FilaDinamica {
    No* inicio = nullptr;
    No* fim = nullptr;
};

bool filaDinamicaVazia(
    const FilaDinamica& fila
) {
    return fila.inicio == nullptr;
}

void enfileirarDinamica(
    FilaDinamica& fila,
    Paciente paciente
) {
    No* novo =
        new No{paciente, nullptr};

    if (filaDinamicaVazia(fila)) {
        fila.inicio = novo;
        fila.fim = novo;
    } else {
        fila.fim->proximo = novo;
        fila.fim = novo;
    }
}

bool desenfileirarDinamica(
    FilaDinamica& fila,
    Paciente& paciente
) {
    if (filaDinamicaVazia(fila)) {
        return false;
    }

    No* removido = fila.inicio;

    paciente =
        removido->paciente;

    fila.inicio =
        fila.inicio->proximo;

    if (fila.inicio == nullptr) {
        fila.fim = nullptr;
    }

    delete removido;

    return true;
}

bool consultarPrimeiroDinamica(
    const FilaDinamica& fila,
    Paciente& paciente
) {
    if (filaDinamicaVazia(fila)) {
        return false;
    }

    paciente =
        fila.inicio->paciente;

    return true;
}

void mostrarFilaDinamica(
    const FilaDinamica& fila
) {
    cout << "Fila dinamica: ";

    if (filaDinamicaVazia(fila)) {
        cout << "vazia" << endl;
        return;
    }

    No* atual = fila.inicio;

    while (atual != nullptr) {

        cout
            << atual->paciente.senha
            << " - "
            << atual->paciente.nome;

        if (atual->proximo != nullptr) {
            cout << " | ";
        }

        atual = atual->proximo;
    }

    cout << endl;
}

void liberarFilaDinamica(
    FilaDinamica& fila
) {
    Paciente paciente;

    while (
        desenfileirarDinamica(
            fila,
            paciente
        )
    ) {
        // Remove todos os nos.
    }
}

// ======================================================
// PROGRAMA PRINCIPAL
// ======================================================

int main() {

    cout
        << "=== FILA CIRCULAR ==="
        << endl;

    FilaCircular filaCircular;

    Paciente atendido;

    enfileirarCircular(
        filaCircular,
        {101, "Ana"}
    );

    enfileirarCircular(
        filaCircular,
        {102, "Bruno"}
    );

    enfileirarCircular(
        filaCircular,
        {103, "Carla"}
    );

    mostrarFilaCircular(
        filaCircular
    );

    if (
        desenfileirarCircular(
            filaCircular,
            atendido
        )
    ) {
        cout
            << "Atendido: "
            << atendido.senha
            << " - "
            << atendido.nome
            << endl;
    }

    enfileirarCircular(
        filaCircular,
        {104, "Diego"}
    );

    enfileirarCircular(
        filaCircular,
        {105, "Elisa"}
    );

    mostrarFilaCircular(
        filaCircular
    );

    cout << endl;

    cout
        << "=== FILA DINAMICA ==="
        << endl;

    FilaDinamica filaDinamica;

    enfileirarDinamica(
        filaDinamica,
        {201, "Fernanda"}
    );

    enfileirarDinamica(
        filaDinamica,
        {202, "Gabriel"}
    );

    enfileirarDinamica(
        filaDinamica,
        {203, "Helena"}
    );

    mostrarFilaDinamica(
        filaDinamica
    );

    if (
        desenfileirarDinamica(
            filaDinamica,
            atendido
        )
    ) {
        cout
            << "Atendido: "
            << atendido.senha
            << " - "
            << atendido.nome
            << endl;
    }

    mostrarFilaDinamica(
        filaDinamica
    );

    liberarFilaDinamica(
        filaDinamica
    );

    return 0;
}

Quando executamos o código acima, obteremos o seguinte resultado:

=== FILA CIRCULAR ===
Fila circular: 101 - Ana | 102 - Bruno | 103 - Carla
Atendido: 101 - Ana
Fila circular: 102 - Bruno | 103 - Carla | 104 - Diego | 105 - Elisa

=== FILA DINAMICA ===
Fila dinamica: 201 - Fernanda | 202 - Gabriel | 203 - Helena
Atendido: 201 - Fernanda
Fila dinamica: 202 - Gabriel | 203 - Helena

Observe que, nas duas implementações, a política FIFO foi preservada.

Entendendo a fila circular no código

O trecho central da inserção está em:

fila.dados[fila.fim] = paciente;

fila.fim = (fila.fim + 1) % CAPACIDADE;

Primeiro, o paciente é armazenado na posição indicada por fim. Depois, fim avança circularmente.

Considere:

CAPACIDADE = 5
fim = 4

Então:

fila.fim = (4 + 1) % 5;

produz:

fila.fim = 0;

Portanto, a próxima inserção poderá voltar ao início do vetor caso aquela posição já tenha sido liberada.

Entendendo a fila dinâmica no código

A inserção começa criando dinamicamente um nó:

No* novo = new No{paciente, nullptr};

Se a fila estiver vazia:

fila.inicio = novo;
fila.fim = novo;

Nes caso, existe apenas um paciente:

inicio
  ↓
[Ana]
  ↑
 fim

Caso já existam elementos:

fila.fim->proximo = novo;
fila.fim = novo;

O novo nó é conectado ao antigo último elemento e passa a representar o novo final da fila.

Complexidade das operações

Quando corretamente implementadas, as principais operações de uma fila podem ser realizadas em tempo constante, conforme descrito na Tabela 1 (Cormen et al., 2012).

OperaçãoFila circularFila dinâmica
EnfileirarO(1)O(1)
DesenfileirarO(1)O(1)
Consultar primeiroO(1)O(1)
Verificar se está vaziaO(1)O(1)
Percorrer toda a filaO(n)O(n)

A diferença principal entre as duas implementações, portanto, não está necessariamente no custo das operações básicas, mas na maneira como a memória é administrada.

Fila circular ou fila dinâmica?

Uma fila circular utiliza uma quantidade previamente reservada de memória. Sua implementação é particularmente apropriada quando existe um limite máximo conhecido. Por exemplo, num cenário onde:

Sala de espera:
máximo de 30 pacientes

o vetor poderia reservar exatamente esse espaço. Já a fila dinâmica cria nós conforme necessário, de forma que:

Paciente chega
      ↓
novo nó é criado
      ↓
nó entra no fim da fila

Em termos didáticos, podemos separar as duas lógicas da seguintes maneira:

Fila circular
→ capacidade previamente definida
→ não utiliza new/delete para cada elemento
→ índices controlam início e fim
Fila dinâmica
→ cresce conforme necessário
→ utiliza alocação dinâmica
→ nós são ligados por ponteiros
→ exige cuidado com gerenciamento de memória

Casos especiais e erros comuns

Tentar retirar um paciente de uma fila vazia

Considere:

Fila: vazia

Executar diretamente a função desenfileirar(...) sem verificar o estado da fila poderia resultar em acesso inválido. Por isso utilizamos:

if (filaDinamicaVazia(fila)) {
    return false;
}

Essa situação é tradicionalmente denominada underflow.

Inserir em uma fila estática cheia

Se: CAPACIDADE = 5 e já existem cinco pacientes, uma sexta inserção não deve sobrescrever os dados existentes. Por isso, verificamos a situação antes com:

if (filaCircularCheia(fila)) {
    return false;
}

Esse problema corresponde ao overflow.

Confundir início com fim

Uma fila possui duas extremidades com responsabilidades distintas:

REMOVE                           INSERE
  ↓                                ↓
INÍCIO                            FIM

Inserir no início e retirar no fim altera a semântica da estrutura. Uma fila FIFO tradicional deve obedecer a seguinte lógica:

inserção → fim
remoção  → início

Portanto, tome cuidado com isso!

Deslocar todos os elementos após uma remoção

Uma implementação ingênua com vetor poderia fazer:

[Ana] [Bruno] [Carla]

Após retirar Ana:

[Bruno] [Carla] [     ]

Isso exigiria copiar Bruno e Carla para posições anteriores.

Para poucos elementos isso pode parecer irrelevante, mas repetir o processo para grandes conjuntos torna a operação de remoção O(n). Uma fila circular elimina essa necessidade ao simplesmente avançar o índice inicio.

Esquecer a circularidade

Em uma fila circular, fazer apenas:

fila.fim++;

eventualmente fará fim ultrapassar a última posição válida. O correto é:

fila.fim = (fila.fim + 1) % CAPACIDADE;

Assim, o índice volta para zero quando alcança o limite.

Esquecer de atualizar o fim da fila dinâmica

Quando o último nó for removido:

inicio
  ↓
[Ana]
  ↑
 fim

Atualize os ponteiros de inicio e fim:

inicio = nullptr
fim    = nullptr

Por isso o código contém:

if (fila.inicio == nullptr) {
    fila.fim = nullptr;
}

Não realizar essa atualização deixa fim apontando para um objeto que deixou de existir.

Esquecer de liberar memória

Considere:

No* novo = new No;

Todo nó criado com new deve eventualmente deixar de ocupar memória com:

delete removido;

Caso contrário, o programa poderá produzir vazamento de memória (em inglês, memory leak).

No exemplo apresentado, também incluímos:

liberarFilaDinamica(filaDinamica);

para garantir que os nós que ainda estiverem na fila sejam removidos antes do encerramento.

Um detalhe importante sobre filas médicas reais

O exemplo apresentado utiliza FIFO puro e básico, porém uma clínica real normalmente precisa considerar regras adicionais, tais como:

  • emergências;
  • prioridades legais;
  • especialidades médicas;
  • horários previamente agendados;
  • diferentes consultórios.

Nesse caso, não seria adequado simplesmente violar a ordem da fila básica. Uma solução de projeto poderia criar diferentes filas ou utilizar uma fila de prioridades, estrutura em que a escolha do próximo elemento considera uma chave de prioridade em vez de simplesmente sua ordem de chegada.

Conclusão

Filas são estruturas lineares fundamentadas na política FIFO, segundo a qual o primeiro elemento inserido é também o primeiro elemento removido (Cormen et al., 2012). Sua utilização é particularmente adequada para problemas nos quais a ordem de chegada deve determinar a ordem de processamento, como ocorre em sistemas de atendimento, impressão, comunicação entre processos e processamento de requisições.

As operações fundamentais são enfileirar, desenfileirar, consultar o primeiro elemento e verificar o estado da estrutura. Quando início e fim são mantidos adequadamente, essas operações podem ser realizadas em O(1).

A implementação circular utiliza um vetor de capacidade previamente definida e reutiliza posições liberadas mediante índices circulares. Já a implementação dinâmica utiliza nós e ponteiros, permitindo que a estrutura cresça conforme novas inserções sejam realizadas. Martins (2009) apresenta essas duas abordagens como implementações clássicas de filas e também associa filas dinâmicas a sistemas de controle de atendimento.

Compreender essas implementações é importante porque o estudo de estruturas de dados não consiste apenas em aprender sintaxe de programação. Ele envolve compreender como uma abstração, suas operações e sua representação em memória se relacionam para resolver adequadamente um problema computacional.

Obrigado pela leitura e bons estudos!

Referências

CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: Elsevier, 2012.

MARTINS, Paulo Roberto (org.). Algoritmos e estrutura de dados: análise e desenvolvimento de sistemas. São Paulo: Pearson Prentice Hall, 2009.

ZIVIANI, Nivio. Projeto de algoritmos: com implementações em Java e C++. São Paulo: Thomson Learning, 2007.

Tag

Artigos relacionados