Pilhas

Uma pilha (stack) é uma estrutura linear em que os elementos só podem ser inseridos e removidos por uma das pontas, o topo. O último elemento inserido é o primeiro a sair: por isso, diz-se que a pilha segue a política LIFO (Last In, First Out).

O modelo intuitivo é uma pilha de pratos em uma prateleira: é fácil colocar um prato em cima ou tirar o de cima, mas, para pegar o penúltimo, é preciso antes tirar o último. Na computação, pilhas aparecem em muitos lugares:

• a pilha de execução, que guarda as chamadas de função ainda não terminadas (é ela que torna a recursão possível);
• o desfazer (undo) de um editor de texto, que desfaz primeiro a última alteração;
• o botão voltar do navegador, que volta primeiro para a página visitada por último;
• a análise de expressões, como verificar se os parênteses de uma expressão estão balanceados (veja a aplicação no fim desta página).

Operações

Três operações definem uma pilha:

• empilhar (push): insere um elemento no topo;
• desempilhar (pop): remove o elemento do topo e o devolve;
• topo (top): consulta o elemento do topo, sem removê-lo.

Também é comum verificar se a pilha está vazia e, quando ela tem tamanho máximo, se está cheia.

Interface do TAD Pilha

Como em todo tipo abstrato de dados, começamos pela interface: quais operações quem usa a pilha tem à disposição. Para simplificar, a pilha guarda inteiros.

/* Pilha.h */
#ifndef PILHA_H
#define PILHA_H

#include <stdbool.h>

typedef struct pilha Pilha;

Pilha *criaPilha(int capacidade);   /* capacidade: máximo de elementos */
void liberaPilha(Pilha *p);
void empilha(Pilha *p, int valor);  /* insere no topo */
int desempilha(Pilha *p);           /* remove o topo e devolve o valor */
int topoPilha(const Pilha *p);      /* devolve o topo, sem remover */
bool pilhaVazia(const Pilha *p);

#endif

Vamos implementar essa mesma interface de duas formas: com um vetor e com uma lista encadeada. O código que usa a pilha (o cliente) não muda nada de uma para a outra; é exatamente esse o valor de programar contra um TAD.

Implementação com vetor

Quando se conhece de antemão quantos elementos a pilha pode ter ao mesmo tempo, um vetor resolve: os elementos ocupam as primeiras posições, e um inteiro topo guarda o índice do elemento do topo. A pilha vazia tem topo = -1.

struct pilha {
    int *vetor;
    int capacidade;
    int topo;       /* índice do elemento do topo; -1 se vazia */
};

Empilhar é avançar o topo e gravar na nova posição; desempilhar é ler a posição do topo e recuar. Nenhum elemento sai do lugar.

void empilha(Pilha *p, int valor) {
    if (p->topo == p->capacidade - 1) {
        printf("Erro: pilha cheia\n");
        return;
    }
    p->topo++;
    p->vetor[p->topo] = valor;
}

int desempilha(Pilha *p) {
    if (pilhaVazia(p)) {
        printf("Erro: pilha vazia\n");
        return -1;
    }
    int valor = p->vetor[p->topo];
    p->topo--;
    return valor;
}

O programa completo está abaixo, com os três arquivos do TAD. O main.c empilha quatro valores, desempilha todos e, por fim, tenta desempilhar de uma pilha vazia.

Implementação com lista encadeada

Quando não se sabe quantos elementos a pilha terá, uma lista encadeada cresce e diminui à vontade. Inserir e remover no início de uma lista simplesmente encadeada custam , então basta considerar o início da lista como o topo da pilha.

typedef struct no {
    int dado;
    struct no *proximo;
} No;

struct pilha {
    No *inicio;     /* o topo da pilha é o início da lista */
    int tamanho;
};

empilha é a inserção no início da lista, e desempilha é a remoção do primeiro nó:

void empilha(Pilha *p, int valor) {
    No *novo = malloc(sizeof(No));
    novo->dado = valor;
    novo->proximo = p->inicio;
    p->inicio = novo;
    p->tamanho++;
}

int desempilha(Pilha *p) {
    if (pilhaVazia(p)) {
        printf("Erro: pilha vazia\n");
        return -1;
    }
    No *removido = p->inicio;
    int valor = removido->dado;      /* lê antes de liberar */
    p->inicio = removido->proximo;
    free(removido);
    p->tamanho--;
    return valor;
}

Para liberar a pilha, basta desempilhar até esvaziá-la e então liberar a struct. A capacidade passada a criaPilha é ignorada: ela só existe para que as duas versões tenham exatamente a mesma interface.

O main.c e o Pilha.h abaixo são os mesmos da versão com vetor; só o Pilha.c mudou. A saída também é a mesma.

Vetor ou lista encadeada?

Na prática, a versão com vetor costuma ser mais rápida (os elementos ficam contíguos na memória e não há alocação a cada operação), e a versão com lista é a escolha natural quando não há um limite razoável para o tamanho.

empilha(p, 1);
empilha(p, 2);
printf("%d ", desempilha(p));
empilha(p, 3);
empilha(p, 4);
printf("%d ", desempilha(p));
printf("%d ", desempilha(p));

Aplicação: delimitadores balanceados

Compiladores precisam verificar se os delimitadores de um programa (parênteses, colchetes e chaves) estão "casados": cada um que abre tem que ser fechado, pelo delimitador do mesmo tipo e na ordem certa. Por exemplo,

a = a + (c + d) * (e - f);
g[10] = h[i[9]] + (j + k)*1;
while (m < (n[8] + o) ) { p = (7 + 2) * 3; }

estão corretos, enquanto

a = a + (c + d) * (e - f));
g[10] = h[i[9]] + (j + k*1;
while (m < (n[8) + o] ) { p = (7 + 2) * 3; }

não estão: na primeira linha sobra um ), na segunda falta um ), e na terceira o ] fecha antes do ( que foi aberto depois do [.

O delimitador que precisa ser fechado primeiro é sempre o último que foi aberto e ainda não foi fechado. "Último a entrar, primeiro a sair": é uma pilha. O algoritmo percorre a expressão e:

• ao encontrar um delimitador de abertura, empilha-o;
• ao encontrar um de fechamento, compara-o com o topo da pilha: se a pilha estiver vazia ou o topo for de outro tipo, a expressão está mal formada; senão, desempilha e continua;
• ignora os demais caracteres.

No fim, a expressão está bem formada se a pilha estiver vazia (senão, sobrou alguém sem fechamento). Implementar esse algoritmo é o primeiro exercício abaixo.

Exercícios

Encontre e corrija o erro

Programa 1

Deveria empilhar 1, 2 e 3 e recusar o quarto elemento, porque a capacidade é 3.

if (p->topo == p->capacidade - 1) {

Programa 2

No *removido = p->inicio;
int valor = removido->dado;
p->inicio = removido->proximo;
free(removido);
p->tamanho--;
return valor;

Programa 3

void liberaPilha(Pilha *p) {
    No *atual = p->inicio;
    while (atual != NULL) {
        No *proximo = atual->proximo;
        free(atual);
        atual = proximo;
    }
    free(p);
}

Implemente

Delimitadores balanceados. Implemente bemFormada, que recebe uma string e diz se os delimitadores ( ), [ ] e { } dela estão bem formados, usando o algoritmo da seção anterior e a pilha (com lista encadeada) que já está pronta em Pilha.c. Os testes incluem linhas com centenas de milhares de delimitadores e verificam se não há vazamento de memória: libere a pilha também quando a função retornar antes de chegar ao fim da string.

Pilha com mínimo. Implemente uma pilha que, além das operações usuais, informa o menor valor guardado nela, com todas as operações em . Percorrer a pilha a cada consulta do mínimo não serve: os testes fazem centenas de milhares de operações. Use a pilha de Pilha.c para guardar os valores (e o que mais for preciso).

Referências

• W. Celes, R. Cerqueira e J. L. Rangel. Introdução a Estruturas de Dados: com técnicas de programação em C. 2ª ed. Grupo GEN, 2016.
• A. Backes. Estrutura de Dados Descomplicada em Linguagem C. Elsevier, 2016.
• Parênteses balanceados. Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python.