[403] Pilhas e Filas na Prática

Com as listas encadeadas dominadas, temos a base para construir estruturas mais especializadas. Hoje conhecemos duas das mais importantes e onipresentes da computação: a pilha e a fila. Elas não são estruturas fundamentalmente novas — no fundo, são listas com regras. O que as define não é como guardam os dados, mas a disciplina que impõem sobre como os dados entram e saem. Essa disciplina, aparentemente uma limitação, é exatamente o que as torna tão úteis, e você as encontrará por trás de recursos que usa todo dia, do "desfazer" do seu editor à fila de impressão.

Pilha: o último a entrar é o primeiro a sair

Uma pilha (stack) funciona como uma pilha de pratos: você adiciona pratos no topo e retira do topo. O último prato colocado é o primeiro a ser retirado. Essa regra tem um nome: LIFO (Last In, First Out — último a entrar, primeiro a sair). A pilha tem apenas duas operações essenciais: empilhar (push), que adiciona um elemento no topo, e desempilhar (pop), que remove e retorna o elemento do topo.

Você já conhece uma pilha intimamente, aliás: a pilha de chamadas que estudamos nas aulas A Pilha e o Heap: Onde Cada Coisa Vive e Recursão: Quando uma Função Chama a Si Mesma é exatamente isso. Quando uma função chama outra, a nova entra no topo; quando retorna, sai do topo. A recursão desempilha na ordem inversa das chamadas justamente porque a pilha é LIFO. Agora vamos construir a nossa.

Implementando uma pilha com lista encadeada

A forma mais elegante de implementar uma pilha é sobre uma lista encadeada, onde o "topo" é a cabeça da lista. Por quê? Porque inserir e remover no início de uma lista é a operação mais rápida que temos (a lição da aula Listas Encadeadas: A Estrutura que Só Existe com Ponteiros) — e é exatamente o que push e pop precisam:

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

typedef struct No {
    int valor;
    struct No *proximo;
} No;

typedef struct {
    No *topo; // o topo da pilha é a cabeça da lista
} Pilha;

void inicializar(Pilha *p) {
    p->topo = NULL; // pilha vazia
}

// push: adiciona no topo (início da lista)
int push(Pilha *p, int valor) {
    No *novo = malloc(sizeof(No));
    if (novo == NULL) return 0; // falha
    novo->valor = valor;
    novo->proximo = p->topo; // aponta para o antigo topo
    p->topo = novo;          // vira o novo topo
    return 1; // sucesso
}

// pop: remove e retorna o topo
int pop(Pilha *p, int *valor) {
    if (p->topo == NULL) return 0; // pilha vazia: nada a remover
    No *removido = p->topo;
    *valor = removido->valor;      // devolve o valor via ponteiro
    p->topo = removido->proximo;   // o topo passa a ser o próximo
    free(removido);                // libera o nó
    return 1;
}

int esta_vazia(Pilha *p) {
    return p->topo == NULL;
}

Repare como push e pop são apenas inserção e remoção no início da lista, com nomes que refletem a disciplina LIFO. O push coloca o novo nó como topo; o pop retira o topo e faz o próximo assumir. Ambos são operações de tempo constante — rápidas independentemente do tamanho da pilha. Note também o padrão de pop: ele devolve o valor via um ponteiro (int *valor) e usa o retorno da função para sinalizar sucesso ou falha (pilha vazia), o idioma robusto que vimos ao longo do curso.

Vendo a pilha em ação

int main(void) {
    Pilha p;
    inicializar(&p);

    push(&p, 10);
    push(&p, 20);
    push(&p, 30); // pilha (topo->base): 30, 20, 10

    int valor;
    while (pop(&p, &valor)) {
        printf("Saiu: %d\n", valor);
    }
    // Saiu: 30 / Saiu: 20 / Saiu: 10  — ordem inversa da entrada!
    return 0;
}

Empilhamos 10, 20, 30 e desempilhamos na ordem 30, 20, 10 — o inverso da entrada, a marca registrada do LIFO. Esse comportamento é a base de muitos recursos: o "desfazer" (undo) empilha suas ações e as reverte na ordem inversa; o navegador empilha as páginas visitadas para o botão "voltar"; interpretadores usam pilhas para avaliar expressões. Sempre que você precisa reverter uma sequência ou processar "o mais recente primeiro", a pilha é a estrutura natural.

Fila: o primeiro a entrar é o primeiro a sair

A fila (queue) segue a disciplina oposta, e igualmente intuitiva: como uma fila de banco, quem chega primeiro é atendido primeiro. Essa regra se chama FIFO (First In, First Out — primeiro a entrar, primeiro a sair). A fila tem duas operações: enfileirar (enqueue), que adiciona no fim, e desenfileirar (dequeue), que remove do início.

Aqui há um detalhe de implementação importante. Como a fila adiciona numa ponta e remove na outra, uma lista encadeada com apenas o ponteiro da cabeça seria ineficiente (adicionar no fim exigiria percorrer tudo, como vimos na aula Listas Encadeadas: A Estrutura que Só Existe com Ponteiros). A solução é guardar dois ponteiros: um para o início (frente, de onde se remove) e outro para o fim (trás, onde se adiciona):

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

typedef struct No {
    int valor;
    struct No *proximo;
} No;

typedef struct {
    No *frente; // de onde removemos (o primeiro da fila)
    No *tras;   // onde adicionamos (o último da fila)
} Fila;

void inicializar(Fila *f) {
    f->frente = NULL;
    f->tras = NULL;
}

// enqueue: adiciona no fim
int enqueue(Fila *f, int valor) {
    No *novo = malloc(sizeof(No));
    if (novo == NULL) return 0;
    novo->valor = valor;
    novo->proximo = NULL; // será o último, então aponta para NULL

    if (f->tras == NULL) {     // fila vazia: novo é frente e trás
        f->frente = novo;
        f->tras = novo;
    } else {
        f->tras->proximo = novo; // liga o antigo último ao novo
        f->tras = novo;          // o novo vira o último
    }
    return 1;
}

// dequeue: remove do início
int dequeue(Fila *f, int *valor) {
    if (f->frente == NULL) return 0; // fila vazia
    No *removido = f->frente;
    *valor = removido->valor;
    f->frente = removido->proximo;   // a frente avança
    if (f->frente == NULL) {         // a fila ficou vazia
        f->tras = NULL;              // precisa zerar o trás também
    }
    free(removido);
    return 1;
}

O ponteiro duplo é a chave da eficiência. Adicionar no fim (enqueue) usa f->tras para chegar direto ao último nó, sem percorrer a lista; remover do início (dequeue) usa f->frente. Ambas as operações são de tempo constante graças aos dois ponteiros. Preste atenção aos casos especiais tratados com if: quando a fila está vazia, o novo elemento é tanto a frente quanto o trás; e quando o último elemento é removido, precisamos zerar o tras também, senão ele ficaria apontando para memória liberada.

Vendo a fila em ação

int main(void) {
    Fila f;
    inicializar(&f);

    enqueue(&f, 10);
    enqueue(&f, 20);
    enqueue(&f, 30); // fila (frente->trás): 10, 20, 30

    int valor;
    while (dequeue(&f, &valor)) {
        printf("Atendido: %d\n", valor);
    }
    // Atendido: 10 / Atendido: 20 / Atendido: 30  — mesma ordem da entrada!
    return 0;
}

Enfileiramos 10, 20, 30 e desenfileiramos na mesma ordem: 10, 20, 30. Essa preservação da ordem de chegada é o que torna a fila indispensável quando a justiça temporal importa: filas de impressão (o primeiro documento enviado imprime primeiro), processamento de requisições em servidores, escalonamento de tarefas, buffers de dados que chegam em streaming. Sempre que "quem chegou primeiro deve ser servido primeiro" for a regra, a fila é a estrutura certa.

A lição maior: estruturas são definidas por suas regras

Pare um momento para notar o que realmente distingue pilha e fila. Ambas guardam elementos numa sequência encadeada — a estrutura física é quase idêntica. O que as diferencia é a disciplina de acesso: a pilha só permite mexer numa ponta (LIFO), a fila permite adicionar numa e remover na outra (FIFO). Essa é uma ideia profunda em ciência da computação: muitas estruturas de dados não são definidas por como armazenam dados, mas pelas regras que impõem sobre como acessá-los. Essas restrições não são fraquezas — são justamente o que dá a cada estrutura seu propósito e suas garantias. Uma pilha "sabe" reverter; uma fila "sabe" preservar ordem. Escolher a estrutura certa é escolher a regra certa para o seu problema.

O que vem a seguir

Hoje construímos pilha e fila sobre listas encadeadas, entendendo que elas são listas com disciplina: LIFO para a pilha (reverter, desfazer, recursão) e FIFO para a fila (preservar ordem, escalonar, processar em série). Vimos que a essência de uma estrutura de dados está tanto em suas regras quanto em seu armazenamento. Até aqui, todas as nossas estruturas foram lineares — sequências. Na próxima aula, damos um salto conceitual para uma estrutura hierárquica: a árvore binária de busca, onde cada nó pode ter dois filhos, e a organização em ramos permite buscas extraordinariamente rápidas. É onde a recursão da aula Recursão: Quando uma Função Chama a Si Mesma vai mostrar toda a sua força.

Fontes e leituras recomendadas

• The C Programming Language (K&R), Kernighan & Ritchie — estruturas de dados sobre nós encadeados
• Algorithms, Robert Sedgewick — capítulos sobre pilhas e filas (stacks and queues)
• Introduction to Algorithms (CLRS) — Cap. 10, estruturas de dados elementares
• Data Structures Using C, Tenenbaum — implementações detalhadas de pilhas e filas
• cppreference — sobre estruturas encadeadas em C — https://en.cppreference.com/w/c/language/struct

Exercícios

Exercício 1

Usando a pilha do artigo, empilhe os números de 1 a 5 e depois desempilhe todos, imprimindo cada um. Confirme que saem na ordem 5, 4, 3, 2, 1.

int main(void) {
    Pilha p;
    inicializar(&p);
    for (int i = 1; i <= 5; i++) push(&p, i);

    int v;
    while (pop(&p, &v)) printf("%d ", v); // 5 4 3 2 1
    printf("\n");
    return 0;
}

Exercício 2

Use uma pilha para verificar se uma string tem parênteses balanceados (cada ( tem seu ) correspondente). Dica: empilhe ao ver (, desempilhe ao ver ); ao final, a pilha deve estar vazia. Teste com "(a(b)c)" e "(a))".

#include <stdio.h>
#include <string.h>
// (usando a Pilha do artigo)
int balanceados(const char *s) {
    Pilha p;
    inicializar(&p);
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(') {
            push(&p, '(');
        } else if (s[i] == ')') {
            int desc;
            if (!pop(&p, &desc)) return 0; // ')' sem '(' correspondente
        }
    }
    int resto;
    int vazia = !pop(&p, &resto); // deve estar vazia ao final
    return vazia;
}
int main(void) {
    printf("%d\n", balanceados("(a(b)c)")); // 1 (balanceado)
    printf("%d\n", balanceados("(a))"));    // 0 (desbalanceado)
    return 0;
}

Exercício 3

Usando a fila do artigo, enfileire os números de 1 a 5 e desenfileire todos, imprimindo cada um. Confirme que saem na ordem 1, 2, 3, 4, 5.

int main(void) {
    Fila f;
    inicializar(&f);
    for (int i = 1; i <= 5; i++) enqueue(&f, i);

    int v;
    while (dequeue(&f, &v)) printf("%d ", v); // 1 2 3 4 5
    printf("\n");
    return 0;
}

Exercício 4

Explique por que a implementação de fila usa dois ponteiros (frente e tras), enquanto a pilha usa apenas um (topo). O que aconteceria com a eficiência da fila se ela tivesse só o ponteiro frente?

Exercício 5

Explique a diferença entre LIFO e FIFO e dê um exemplo do mundo real para cada um, diferente dos mencionados no artigo. Para cada exemplo, justifique por que a disciplina correspondente é a apropriada.