Nesta aula estudamos o TAD Pilha, a primeira de três estruturas de dados especializadas que veremos nesta unidade (pilhas, filas e deques). Diferente das listas gerais vistas até agora, uma pilha restringe onde é possível inserir e remover elementos — e é exatamente essa restrição que a torna útil e eficiente para uma série de problemas.

1. O TAD Pilha

Uma pilha (stack) é uma lista em que todas as inserções e remoções ocorrem em uma única extremidade, chamada de topo. Isso faz com que o último elemento inserido seja sempre o primeiro a ser removido — comportamento conhecido pela sigla LIFO (Last-In, First-Out).

        +-------+
 topo -> |   C   |  (último a entrar, primeiro a sair)
        +-------+
        |   B   |
        +-------+
        |   A   |  (primeiro a entrar, último a sair)
        +-------+

A analogia mais comum é a de uma pilha de pratos: só é possível colocar um novo prato no topo, e só é possível retirar o prato que está no topo — nunca um prato do meio ou do fundo da pilha.

Operações

2. Implementação por lista encadeada

Implementamos a pilha sobre uma lista encadeada (Aula 4), sem limite de capacidade. A ideia central: o topo da pilha é sempre o início da lista — e empilhar/desempilhar tornam-se, respectivamente, inserir e remover no início:

typedef struct {
    int cod;
    char nome[50];
    float preco;
} Produto;

typedef struct str_Nodo Nodo;

struct str_Nodo {
    Nodo *prox;
    Produto dado;
};

typedef struct {
    Nodo *topo;
} PilhaEnc;

void inicializa(PilhaEnc *p) {
    p->topo = NULL;
}

int estaVazia(const PilhaEnc *p) {
    return p->topo == NULL;
}

int push(PilhaEnc *p, Produto valor) {
    Nodo *novo = (Nodo*) malloc(sizeof(Nodo));
    if (novo == NULL)
        return 0;

    novo->dado = valor;
    novo->prox = p->topo; // aponta para o antigo topo
    p->topo = novo;        // o novo nodo passa a ser o topo
    return 1;
}

int pop(PilhaEnc *p, Produto *valorRemovido) {
    Nodo *removido;

    if (estaVazia(p)) // underflow
        return 0;

    removido = p->topo;
    *valorRemovido = removido->dado;
    p->topo = removido->prox;
    free(removido);
    return 1;
}

int topo(const PilhaEnc *p, Produto *valor) {
    if (estaVazia(p))
        return 0;

    *valor = p->topo->dado;
    return 1;
}

int tamanho(const PilhaEnc *p) {
    Nodo *aux = p->topo;
    int contador = 0;

    while (aux != NULL) {
        contador++;
        aux = aux->prox;
    }

    return contador;
}

Todas as operações desta implementação são O(1), e a pilha cresce dinamicamente sem nenhum limite predefinido — o único limite passa a ser a memória disponível no sistema. É por isso que adotamos a lista encadeada como implementação principal do TAD Pilha nesta disciplina.

3. Aplicações

Pilha de execução de funções

Já usamos uma pilha sem perceber: a própria pilha de chamadas de função (Material Extra — Conceitos de Linguagens de Programação) é uma pilha no sentido deste TAD. Cada chamada de função "empilha" um quadro de ativação, e o retorno da função "desempilha" esse quadro — sempre na mesma ordem LIFO: a última função chamada é a primeira a retornar.

Verificação de parênteses balanceados

Um uso clássico de pilhas é verificar se os parênteses (ou colchetes, chaves) de uma expressão estão corretamente balanceados. A ideia: percorrer a expressão da esquerda para a direita, empilhando cada abertura, e desempilhando a cada fechamento correspondente. Para isso, usamos o campo cod de um Produto apenas para guardar o caractere empilhado — os demais campos ficam sem uso nesta aplicação específica, já que a pilha desta aula é definida sobre Produto:

int parentesesBalanceados(char *expressao) {
    PilhaEnc p;
    int i;
    char c;
    Produto simbolo, removido;

    inicializa(&p);

    for (i = 0; expressao[i] != '\0'; i++) {
        c = expressao[i];

        if (c == '(') {
            simbolo.cod = c;
            push(&p, simbolo);
        } else if (c == ')') {
            if (!pop(&p, &removido)) // fechou sem ter aberto: desbalanceado
                return 0;
        }
    }

    // se sobrou algo na pilha, há aberturas sem fechamento correspondente
    return estaVazia(&p);
}

Por exemplo, "(a(b)c)" é balanceado (a pilha termina vazia), enquanto "(a(b)c" não é (sobra um ( na pilha) e "a)b(" também não é (o primeiro ) tenta desempilhar uma pilha já vazia).

Outras aplicações

• Desfazer/refazer (undo/redo): cada ação do usuário é empilhada; "desfazer" desempilha a última ação.
• Navegação "voltar" de um navegador: cada página visitada é empilhada; "voltar" desempilha a página atual e exibe a anterior.
• Avaliação de expressões em notação pós-fixa (ex: calculadoras), e conversão de expressões infixas para pós-fixas — assuntos que costumam ser aprofundados em Análise e Projeto de Algoritmos I.

Resumo

Exercícios

1. Explique, com suas próprias palavras, o que significa a sigla LIFO e como ela se relaciona com a operação pop.
2. Por que a pilha implementada sobre lista encadeada usa o início da lista como topo, e não o final?
3. Explique por que a pilha de chamadas de função (Material Extra — Conceitos de Linguagens de Programação) é um exemplo de estrutura LIFO. O que corresponde a "empilhar" e o que corresponde a "desempilhar" nesse contexto?
4. Na função parentesesBalanceados, o que aconteceria se trocássemos a pilha por uma fila (que veremos na próxima aula, com comportamento FIFO)? O algoritmo continuaria funcionando corretamente?
5. Implemente uma função int inverterVetor(Produto vetor[], int n) que utilize uma PilhaEnc para inverter a ordem dos elementos de um vetor de Produto (empilhando todos os elementos e depois desempilhando de volta no próprio vetor).
6. Estenda o exercício de parênteses balanceados: implemente int expressaoBalanceada(char *expressao), que verifique o balanceamento de três tipos de símbolos — (), [] e {} — garantindo também que eles fecham na ordem correta (por exemplo, "(a[b)c]" deve ser considerado desbalanceado, mesmo tendo a mesma quantidade de aberturas e fechamentos).
7. Implemente a pilha por vetor. Defina a struct PilhaVet, com um vetor de capacidade fixa (CAPACIDADE) e um índice topo, e implemente as funções inicializa, estaVazia, push e pop (tratando tanto overflow quanto underflow). Explique, com base na sua implementação, por que todas as operações continuam sendo O(1), assim como na versão por lista encadeada.

Sugestões de Respostas dos Exercícios

int inverterVetor(Produto vetor[], int n) {
    PilhaEnc p;
    int i;
    Produto valor;

    inicializa(&p);

    for (i = 0; i < n; i++) {
        if (!push(&p, vetor[i]))
            return 0; // falha na alocação de algum nodo
    }

    for (i = 0; i < n; i++) {
        pop(&p, &valor);
        vetor[i] = valor;
    }

    return 1;
}

int expressaoBalanceada(char *expressao) {
    PilhaEnc p;
    int i;
    char c;
    Produto simbolo, removido;

    inicializa(&p);

    for (i = 0; expressao[i] != '\0'; i++) {
        c = expressao[i];

        if (c == '(' || c == '[' || c == '{') {
            simbolo.cod = c;
            push(&p, simbolo);
        } else if (c == ')' || c == ']' || c == '}') {
            if (!pop(&p, &removido))
                return 0; // fechou sem ter aberto nada

            // o símbolo desempilhado precisa ser exatamente a abertura correspondente
            if ((c == ')' && removido.cod != '(') ||
                (c == ']' && removido.cod != '[') ||
                (c == '}' && removido.cod != '{')) {
                return 0; // fechou o símbolo errado
            }
        }
    }

    return estaVazia(&p);
}

#define CAPACIDADE 50

typedef struct {
    Produto dados[CAPACIDADE];
    int topo; // índice do elemento no topo; -1 significa pilha vazia
} PilhaVet;

void inicializa(PilhaVet *p) {
    p->topo = -1;
}

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

int push(PilhaVet *p, Produto valor) {
    if (p->topo == CAPACIDADE - 1) // overflow
        return 0;

    p->topo++;
    p->dados[p->topo] = valor;
    return 1;
}

int pop(PilhaVet *p, Produto *valorRemovido) {
    if (estaVazia(p)) // underflow
        return 0;

    *valorRemovido = p->dados[p->topo];
    p->topo--;
    return 1;
}

Questões teóricas

1. Se adicionássemos um campo int tamanho à struct PilhaEnc, qual seria o impacto nas funções já implementadas? Em que situações esse campo valeria a pena, e o que seria necessário manter consistente?
2. A implementação por lista encadeada coloca o topo no início da lista; a implementação por vetor (PilhaVet) usa o índice mais alto como topo. Por que ambas as escolhas são O(1) para push e pop, mesmo sendo opostas em direção?
3. Por que a operação topo (peek) não é implementada simplesmente como um pop seguido de um push do valor removido? O que se perderia em termos de robustez e semântica?
4. Trace manualmente o estado da pilha durante a execução de parentesesBalanceados("(a(b)c)"). Mostre o conteúdo da pilha após o processamento de cada caractere, e indique o valor retornado ao final.
5. A pilha de chamadas de função do C é LIFO. O que aconteceria concretamente se ela fosse FIFO? Considere a cadeia de chamadas main → f1 → f2: qual função retornaria primeiro, e qual seria o problema prático disso?
6. Suponha que você precise de uma estrutura que acesse eficientemente tanto o elemento inserido mais recentemente quanto o mais antigo. Seria suficiente usar apenas uma PilhaEnc? Justifique, e indique qual outra estrutura seria mais adequada.

Questões de implementação

Nas questões abaixo, todas as soluções devem usar a PilhaEnc como cliente: utilize apenas as funções do TAD (inicializa, push, pop, topo, estaVazia) — sem acessar nem modificar os campos internos da struct diretamente.

1. Implemente void decimalParaBinario(int n) que, usando uma PilhaEnc, imprima a representação binária de n: divida repetidamente por 2, empilhando cada resto; ao final, desempilhe e imprima os restos na ordem correta (do bit mais significativo para o menos significativo). Use o campo cod de Produto para guardar cada bit (0 ou 1).
2. Implemente int ehPalindromo(char *str, int n) que use uma PilhaEnc para verificar se str (de comprimento n) é um palíndromo: empilhe os primeiros n/2 caracteres; compare, desempilhando, com os n/2 últimos caracteres. Use o campo cod para guardar cada caractere (int).
3. Implemente int avaliarPosFixa(char *expr) que avalie uma expressão em notação pós-fixa contendo dígitos ('0'–'9') e operadores ('+', '-', '*'). Ao percorrer a string: se for dígito, empilhe o valor numérico; se for operador, desempilhe dois operandos, calcule e empilhe o resultado. Retorne o valor no topo ao final. Exemplo: "23+4*" → (2+3)*4 = 20.
4. Implemente void imprimirPilhaIntacta(PilhaEnc *p) que imprima os elementos do topo ao fundo sem modificar a pilha ao final. Use uma segunda PilhaEnc auxiliar: transfira tudo para ela (imprimindo no caminho), depois transfira de volta — a pilha original deve terminar com os mesmos elementos e na mesma ordem.
5. Implemente um sistema simples de undo com duas funções: void executarAcao(PilhaEnc *historico, Produto acao), que empilha a ação realizada; e int desfazer(PilhaEnc *historico, Produto *ultima), que desempilha a última ação em *ultima e retorna 1, ou retorna 0 se não houver nada para desfazer. Escreva também um pequeno main de exemplo executando 3 ações e depois 2 desfazer.
6. Implemente int sequenciaPopValida(int n, int saida[], int m) que determine se a sequência saida[0..m-1] é uma sequência de pops válida supondo que produtos de cod = 1, 2, ..., n são empilhados em ordem crescente (um de cada vez, podendo intercalar pops). Use uma PilhaEnc para simular: para cada valor em saida, empilhe novos elementos enquanto o topo não for o esperado; se precisar desempilhar de uma pilha vazia ou o topo não bater, a sequência é inválida.

Sugestões de Respostas — Questões teóricas e de implementação

Expressão: ( a ( b ) c )
           ↑ ↑ ↑ ↑ ↑ ↑ ↑

'(' → push('(')       pilha: ['(']
'a' → nada            pilha: ['(']
'(' → push('(')       pilha: ['(', '(']     ← topo: segundo '('
'b' → nada            pilha: ['(', '(']
')' → pop             pilha: ['(']
'c' → nada            pilha: ['(']
')' → pop             pilha: []

pilha vazia → retorna 1 (balanceado)

void decimalParaBinario(int n) {
    PilhaEnc p;
    Produto bit, removido;
    inicializa(&p);

    if (n == 0) { printf("0\n"); return; }

    while (n > 0) {
        bit.cod = n % 2;
        push(&p, bit);
        n /= 2;
    }

    while (!estaVazia(&p)) {
        pop(&p, &removido);
        printf("%d", removido.cod);
    }
    printf("\n");
}

int ehPalindromo(char *str, int n) {
    PilhaEnc p;
    Produto c, removido;
    int i;
    inicializa(&p);

    for (i = 0; i < n / 2; i++) {
        c.cod = str[i];
        push(&p, c);
    }

    // se n é ímpar, pula o caractere do meio
    for (i = (n + 1) / 2; i < n; i++) {
        pop(&p, &removido);
        if (removido.cod != str[i])
            return 0;
    }

    return 1;
}

int avaliarPosFixa(char *expr) {
    PilhaEnc p;
    Produto op1, op2, res;
    int i;
    inicializa(&p);

    for (i = 0; expr[i] != '\0'; i++) {
        if (expr[i] >= '0' && expr[i] <= '9') {
            res.cod = expr[i] - '0';
            push(&p, res);
        } else {
            pop(&p, &op2); // segundo operando (topo)
            pop(&p, &op1); // primeiro operando
            if      (expr[i] == '+') res.cod = op1.cod + op2.cod;
            else if (expr[i] == '-') res.cod = op1.cod - op2.cod;
            else if (expr[i] == '*') res.cod = op1.cod * op2.cod;
            push(&p, res);
        }
    }

    pop(&p, &res);
    return res.cod;
}

void imprimirPilhaIntacta(PilhaEnc *p) {
    PilhaEnc aux;
    Produto val;
    inicializa(&aux);

    // transfere para auxiliar e imprime
    while (!estaVazia(p)) {
        pop(p, &val);
        printf("cod=%d\n", val.cod);
        push(&aux, val);
    }

    // devolve para a original (restaura a ordem)
    while (!estaVazia(&aux)) {
        pop(&aux, &val);
        push(p, val);
    }
}

void executarAcao(PilhaEnc *historico, Produto acao) {
    push(historico, acao);
}

int desfazer(PilhaEnc *historico, Produto *ultima) {
    return pop(historico, ultima);
}

// Exemplo de uso:
int main() {
    PilhaEnc historico;
    Produto a1 = {1, "Inserir A", 0};
    Produto a2 = {2, "Inserir B", 0};
    Produto a3 = {3, "Deletar C", 0};
    Produto ultima;
    inicializa(&historico);

    executarAcao(&historico, a1);
    executarAcao(&historico, a2);
    executarAcao(&historico, a3);

    desfazer(&historico, &ultima); // desfaz a3
    printf("Desfeito: %s\n", ultima.nome);
    desfazer(&historico, &ultima); // desfaz a2
    printf("Desfeito: %s\n", ultima.nome);
    return 0;
}

int sequenciaPopValida(int n, int saida[], int m) {
    PilhaEnc p;
    Produto val, topo_val;
    int proximo_push = 1; // próximo cod a empilhar
    int i;
    inicializa(&p);

    for (i = 0; i < m; i++) {
        // empilha até o topo ser o esperado ou acabar os pushes
        while ((estaVazia(&p) || (topo(&p, &topo_val) && topo_val.cod != saida[i]))
               && proximo_push <= n) {
            val.cod = proximo_push++;
            push(&p, val);
            topo(&p, &topo_val);
        }

        if (estaVazia(&p) || topo_val.cod != saida[i])
            return 0; // não é possível gerar saida[i]

        pop(&p, &val);
    }

    return 1;
}

Código para Download

O TAD PilhaEnc completo, exatamente como visto nesta aula, dividido em interface (pilhaEnc.h) e implementação (pilhaEnc.c), junto com um main.c de exemplo: