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(PilhaEnc *p) {
    return p->topo == NULL;
}

int empilha(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 desempilha(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(PilhaEnc *p, Produto *valor) {
    if (estaVazia(p))
        return 0;

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

int tamanho(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;
            empilha(&p, simbolo);
        } else if (c == ')') {
            if (!desempilha(&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 desempilha.
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, empilha e desempilha (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 (!empilha(&p, vetor[i]))
            return 0; // falha na alocação de algum nodo
    }

    for (i = 0; i < n; i++) {
        desempilha(&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;
            empilha(&p, simbolo);
        } else if (c == ')' || c == ']' || c == '}') {
            if (!desempilha(&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(PilhaVet *p) {
    return p->topo == -1;
}

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

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

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

    *valorRemovido = p->dados[p->topo];
    p->topo--;
    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: