📚 Cap 15: Pilhas (Stacks), Filas (Queues) e Deques: Fundamentos e Lógica LIFO/FIFO

🗺️ Comparação Lógica: LIFO (Pilha) vs FIFO (Fila)

flowchart TD
    subgraph PILHA ["1. Pilha (Stack): LIFO (Last-In, First-Out) 🥞"]
        direction TB
        P_IN["push(30) ⬇️"] --> P3["[30] Topo"]
        P3 --> P2["[20]"]
        P2 --> P1["[10] Base"]
        P3 -.-> P_OUT["pop() ⬆️ (Remove o 30!)"]
    end

    subgraph FILA ["2. Fila (Queue): FIFO (First-In, First-Out) 🚶‍♂️🚶‍♀️"]
        direction LR
        Q_IN["enqueue(30) ➡️ Entrada (Trás)"] --> Q3["[30]"]
        Q3 --> Q2["[20]"]
        Q2 --> Q1["[10]"]
        Q1 --> Q_OUT["dequeue() ➡️ Saída (Frente - Remove o 10!) ⚡"]
    end

    style PILHA fill:#ede7f6,stroke:#512da8,stroke-width:2px
    style FILA fill:#e1f5fe,stroke:#03a9f4,stroke-width:2px
    style P3 fill:#00897b,stroke:#004d40,stroke-width:1.5px,color:#ffffff
    style Q1 fill:#00897b,stroke:#004d40,stroke-width:1.5px,color:#ffffff

📖 Fundamentos e Aplicação

Pilhas (Stacks) e Filas (Queues) são estruturas de dados abstratas lineares com disciplinas estritas de inserção e remoção. São pilares da computação aplicados desde o controle de chamadas de funções até sistemas de mensageria em larga escala.

1. Pilhas (LIFO — Last-In, First-Out):

• O último elemento inserido é obrigatoriamente o primeiro a ser removido.
• Operações Principais:
  • push(x): Insere no topo ($O(1)$).
  • pop(): Remove e retorna do topo ($O(1)$).
  • peek() / top(): Consulta o elemento do topo sem remover ($O(1)$).
• Aplicações: Desfazer/Refazer (Ctrl+Z), avaliação de expressões pós-fixas (notação polonesa reversa), validação de parênteses/tags HTML e navegação de histórico de páginas web.

2. Filas (FIFO — First-In, First-Out):

• O primeiro elemento inserido é o primeiro a ser atendido.
• Operações Principais:
  • enqueue(x): Insere no fim da fila ($O(1)$).
  • dequeue(): Remove do início da fila ($O(1)$).
• Aplicações: Filas de impressão, buffers de pacotes de rede, algoritmos de busca em largura (BFS) e filas de tarefas (RabbitMQ/Kafka).

3. Deques (Double-Ended Queues):

• Filas de ponta dupla que permitem inserção e remoção tanto no início quanto no fim em tempo constante $O(1)$.

💡 Pilha/Fila com vetor ou com lista encadeada? O Capítulo 14 mostrou como construir uma lista encadeada com malloc/free, e ela também poderia implementar uma pilha ou fila (inserindo/removendo sempre no head). Mas quando o tamanho máximo é conhecido de antemão, um vetor de tamanho fixo é mais simples e mais rápido (sem malloc a cada operação) — é a abordagem que este capítulo usa em C.

---

🛠️ Implementando uma Pilha em C (com Vetor)

Uma pilha com vetor precisa de dois ingredientes: o vetor que guarda os dados, e uma variável topo que indica a posição do último elemento inserido (topo = -1 significa pilha vazia).

#include <stdio.h>

#define CAPACIDADE 5

typedef struct {
    int dados[CAPACIDADE];
    int topo; // -1 = pilha vazia
} Pilha;

void inicializar(Pilha *p) {
    p->topo = -1;
}

int estaVazia(Pilha *p) {
    return p->topo == -1;
}

int estaCheia(Pilha *p) {
    return p->topo == CAPACIDADE - 1;
}

int push(Pilha *p, int valor) {
    if (estaCheia(p)) {
        return 0; // Falha: pilha cheia
    }
    p->topo++;
    p->dados[p->topo] = valor;
    return 1;
}

int pop(Pilha *p, int *valorRemovido) {
    if (estaVazia(p)) {
        return 0; // Falha: pilha vazia
    }
    *valorRemovido = p->dados[p->topo];
    p->topo--;
    return 1;
}

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

    push(&p, 10);
    push(&p, 20);
    push(&p, 30);

    printf("Pilha apos 3 push: topo esta na posicao %d\n", p.topo);

    int valor;
    pop(&p, &valor);
    printf("pop() removeu: %d\n", valor);

    pop(&p, &valor);
    printf("pop() removeu: %d\n", valor);

    printf("estaVazia? %s\n", estaVazia(&p) ? "sim" : "nao");

    return 0;
}

Saída:

Pilha apos 3 push: topo esta na posicao 2
pop() removeu: 30
pop() removeu: 20
estaVazia? nao

💡 p->topo em vez de (*p).topo: como as funções recebem Pilha *p (um ponteiro para struct, técnica vista no Capítulo 13 para evitar copiar a struct inteira a cada chamada), o operador seta -> acessa um campo diretamente a partir do ponteiro — p->topo é apenas um atalho para (*p).topo.

---

🛠️ Implementando uma Fila Circular em C (com Vetor)

Uma fila simples com vetor tem um problema: depois de várias operações, o “início” avança e o espaço no começo do vetor fica desperdiçado. A solução clássica é a fila circular, que usa o operador % (módulo) para “dar a volta” no vetor e reaproveitar os espaços liberados.

#include <stdio.h>

#define CAPACIDADE 3

typedef struct {
    int dados[CAPACIDADE];
    int inicio;
    int fim;
    int total;
} FilaCircular;

void inicializar(FilaCircular *f) {
    f->inicio = 0;
    f->fim = 0;
    f->total = 0;
}

int enfileirar(FilaCircular *f, int valor) {
    if (f->total == CAPACIDADE) {
        return 0; // Fila cheia
    }
    f->dados[f->fim] = valor;
    f->fim = (f->fim + 1) % CAPACIDADE;
    f->total++;
    return 1;
}

int desenfileirar(FilaCircular *f, int *valorRemovido) {
    if (f->total == 0) {
        return 0; // Fila vazia
    }
    *valorRemovido = f->dados[f->inicio];
    f->inicio = (f->inicio + 1) % CAPACIDADE;
    f->total--;
    return 1;
}

int main() {
    FilaCircular f;
    inicializar(&f);

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

    int valor;
    desenfileirar(&f, &valor);
    printf("dequeue() removeu: %d\n", valor);

    enfileirar(&f, 40); // Reaproveita o espaco liberado pelo dequeue

    while (desenfileirar(&f, &valor)) {
        printf("dequeue() removeu: %d\n", valor);
    }

    return 0;
}

Saída:

dequeue() removeu: 10
dequeue() removeu: 20
dequeue() removeu: 30
dequeue() removeu: 40

💡 Por que % CAPACIDADE? Sem o módulo, fim cresceria para sempre (3, 4, 5…) e estouraria o vetor mesmo com espaço livre no início. Com % CAPACIDADE, o índice “dá a volta”: (2 + 1) % 3 = 0, voltando à posição 0 — por isso o 40 do exemplo acima consegue ocupar a posição que o 10 liberou.

---

🎯 Aplicação Clássica: Validação de Parênteses com Pilha

Um dos usos mais didáticos de pilha é verificar se símbolos de abertura/fechamento ((), [], {}) estão balanceados — a lógica é: todo símbolo de abertura entra na pilha (push); todo símbolo de fechamento precisa casar com o topo da pilha (pop). No final, a pilha deve estar vazia. Você implementará essa lógica completa em C nos Exercícios deste capítulo.

---

🛠️ Como Executar no Code::Blocks

Você pode compilar e executar todos os exemplos de código em C acima no Code::Blocks (a IDE recomendada para este curso — veja o guia de instalação em Configuração do Ambiente).

1. Novo Projeto: File > New > Project... > Console Application > C.
2. Nomeie o Projeto: Dê um nome (ex: PilhasEFilas) e escolha uma pasta.
3. Cole o Código: Abra o arquivo main.c gerado automaticamente e substitua o conteúdo por um dos exemplos acima.
4. Compile e Execute: Pressione F9 (ou Build > Build and Run). Uma janela de console (terminal) abrirá mostrando a saída do programa.

---

🎯 Próximos Passos

• 🧩 Praticar: Exercícios do Capítulo 15