FIFO — First In, First Out

Fila: entrada no back, saída no front

A fila é um tipo abstrato no qual somente o elemento inserido há mais tempo pode ser removido.

enqueue · dequeue · front

Contrato da fila

  • enqueue(valor) adiciona um elemento no back/tail.
  • dequeue() remove e retorna o elemento do front/head.
  • front() consulta o próximo elemento sem removê-lo.
  • FIFO preserva a ordem de chegada.

Implementações corretas

Uma fila pode usar um array circular ou uma lista encadeada com referências para as duas pontas.

Remover o primeiro elemento de um std::vector funciona logicamente, mas exige deslocar os demais elementos e custa O(n).

Laboratório: fila simplesmente encadeada

front aponta para a primeira célula e back para a última. Cada célula guarda o endereço da próxima; a última aponta para nullptr.

Enqueue no back e dequeue no front

Operação
Ordem do front ao back

    C++: std::queue

    deque fornece inserções e remoções nas duas extremidades com desempenho aproximadamente O(1). Para fila, usamos somente o back para entrada e o front para saída.

    C++17fila pronta
    #include <queue>

std::queue<int> fila;

fila.push(10);
fila.push(20);

int primeiro = fila.front();
fila.pop();

    Fila encadeada

    Manter front e back permite enqueue e dequeue em O(1), inclusive quando a fila tem muitos elementos.

    C++17ligações essenciais
    #include <memory>
#include <stdexcept>

class FilaEncadeada {
    struct No {
        int valor;
        std::unique_ptr<No> proximo;
        explicit No(int valor) : valor(valor), proximo(nullptr) {}
    };

    std::unique_ptr<No> inicio;
    No* fim = nullptr;

public:
    void enqueue(int valor) {
        auto novo = std::make_unique<No>(valor);
        No* endereco = novo.get();

        if (fim) fim->proximo = std::move(novo);
        else inicio = std::move(novo);

        fim = endereco;
    }

    int dequeue() {
        if (!inicio) throw std::runtime_error("fila vazia");
        int valor = inicio->valor;
        inicio = std::move(inicio->proximo);
        if (!inicio) fim = nullptr;
        return valor;
    }
};

    Referências usadas