Conceito, operações e implementações de pilhas

Estruturas de dados permitem organizar informações de acordo com as operações que serão realizadas sobre elas. Segundo Ziviani (2006), a escolha da representação dos dados está diretamente relacionada aos algoritmos que atuarão sobre esses dados, pois diferentes estruturas favorecem diferentes formas de acesso, inserção e remoção.

Nesse contexto surge o conceito de Tipo Abstrato de Dados (TAD). Um TAD descreve um conjunto de dados e as operações permitidas sobre eles, sem determinar necessariamente como essas operações serão implementadas internamente. Ziviani (2006) define o TAD como um modelo acompanhado das operações que podem ser realizadas sobre esse modelo. Sua implementação concreta pode utilizar diferentes estruturas de dados.

Dentre as principais possibilidades de TAD temos as pilhas (do inglês, stack). Seu comportamento é determinado pela política Last In, First Out (LIFO), ou seja, o último elemento inserido é o primeiro elemento removido (Cormen et al., 2012). As pilhas são exemplos clássicos de um TAD.

Imagine uma cafeteria em que bandejas limpas são colocadas umas sobre as outras:

TOPO
┌───────────┐
│ Bandeja 3 │← última colocada
├───────────┤
│ Bandeja 2 │
├───────────┤
│ Bandeja 1 │← primeira colocada
└───────────┘

A próxima bandeja disponível será a Bandeja 3, justamente a última que foi colocada. Essa é a lógica de uma pilha.

O que é uma pilha?

Uma pilha é uma estrutura linear na qual inserções e remoções acontecem em uma única extremidade, denominada topo. Como consequência, os elementos são removidos na ordem inversa daquela em que foram inseridos.

Considere as seguintes operações em uma cafeteria:

Empilhar Bandeja 1

Topo
 ↓
[Bandeja 1]


Empilhar Bandeja 2

Topo
 ↓
[Bandeja 2]
[Bandeja 1]


Empilhar Bandeja 3

Topo
 ↓
[Bandeja 3]
[Bandeja 2]
[Bandeja 1]

Ao desempilhar:

Retirada → Bandeja 3

Topo
 ↓
[Bandeja 2]
[Bandeja 1]

Retirada → Bandeja 2

Topo
 ↓
[Bandeja 1]

Retirada → Bandeja 1

Topo
 ↓

Portanto:

Entrada:  1 → 2 → 3

Saída:    3 → 2 → 1

Essa característica distingue a pilha de outras estruturas, como a fila, que utiliza a política First In, First Out (FIFO), segundo Cormen et al (2012).

Pilha como Tipo Abstrato de Dados

Ao estudar pilhas, é importante separar duas ideias: pilhas são um TAD, enquanto vetores e estruturas encadeadas são possíveis formas de implementá-lo. Assim, conceitualmente, uma pilha precisa oferecer determinadas operações. Entretanto, não é necessário que o usuário da estrutura conheça os detalhes internos utilizados para realizá-las.

Por exemplo:

empilhar(item)
desempilhar()
consultarTopo()
estaVazia()

Essas operações poderiam funcionar sobre um vetor, uma lista encadeada ou outra representação apropriada. Essa separação entre interface e representação é justamente uma das ideias fundamentais dos tipos abstratos de dados (Ziviani, 2006).

Operações primitivas de uma pilha

As principais operações são empilhar (push), desempilhar (pop), consultar o topo (peek ou top) e verificar se a pilha está vazia. Algumas implementações também oferecem operações para consultar seu tamanho ou verificar se uma pilha está cheia.

Empilhar (push)

A operação push adiciona um novo elemento ao topo. Considere:

[Bandeja 2] ← topo
[Bandeja 1]

Ao executar:

push(Bandeja 3)

o resultado será:

[Bandeja 3] ← topo
[Bandeja 2]
[Bandeja 1]

Desempilhar (pop)

A operação pop remove o elemento localizado no topo. Supondo:

[Bandeja 3] ← removida
[Bandeja 2]
[Bandeja 1]

Depois da operação pop ficamos com:

[Bandeja 2] ← novo topo
[Bandeja 1]

A retirada não pode acontecer arbitrariamente no meio ou na base da pilha. O acesso segue obrigatoriamente a política LIFO.

Consultar o topo (peek ou top)

Nem sempre é necessário remover o elemento. Em determinadas situações, deseja-se apenas saber qual elemento está no topo.

[Bandeja 3] ← consultar
[Bandeja 2]
[Bandeja 1]

Nesse caso, a pilha continua inalterada e o topo continua apontando para a [Bandeja 3].

Verificar se a pilha está vazia

Antes de retirar ou consultar um elemento, deve-se verificar se existe algum elemento armazenado. Cormen et al. (2012) destacam que a tentativa de realizar pop sobre uma pilha vazia caracteriza uma condição de underflow, isto é, uma tentativa de remover um elemento inexistente.

Pilha estática

Uma pilha estática utiliza uma estrutura de tamanho previamente determinado, normalmente um vetor. Martins (2009) apresenta a implementação estática de pilhas utilizando vetores, observando que a quantidade máxima de elementos fica limitada ao tamanho reservado para o vetor.

Podemos representar uma pilha com capacidade para três bandejas da seguinte maneira:

índice

2   [         ]
1   [         ]
0   [         ]

topo = 0

Nesse modelo, utilizaremos topo como a quantidade de elementos armazenados.

Depois de inserir uma bandeja:

2   [         ]
1   [         ]
0   [Bandeja 1]

topo = 1

Depois de três inserções:

2   [Bandeja 3]
1   [Bandeja 2]
0   [Bandeja 1]

topo = 3

Observe que a pilha agora está cheia.

Essa abordagem é simples e eficiente, mas apresenta uma limitação evidente: sua capacidade precisa ser determinada antecipadamente.

Pilha dinâmica

Uma pilha dinâmica utiliza memória alocada durante a execução do programa. Uma maneira tradicional de implementá-la é por meio de nós encadeados utilizando ponteiros.

Martins (2009) apresenta essa estratégia utilizando um ponteiro para o topo. Cada elemento armazena seu dado e uma referência para o próximo elemento da pilha. Podemos visualizar esse exemplo da seguinte maneira:

topo
 ↓
┌────────────┬──────┐
│ Bandeja 3  │   ●──┼───┐
└────────────┴──────┘   │
                        ↓
               ┌────────────┬──────┐
               │ Bandeja 2  │   ●──┼───┐
               └────────────┴──────┘   │
                                       ↓
                              ┌────────────┬──────┐
                              │ Bandeja 1  │ null │
                              └────────────┴──────┘

Ao empilhar um novo elemento, cria-se um novo nó. Esse nó passa a apontar para o antigo topo e, posteriormente, torna-se o novo topo. Ao desempilhar, o nó apontado pelo topo é removido e seu sucessor torna-se o novo topo.

A principal diferença é que não existe uma capacidade previamente estabelecida. Contudo, cabe lembrar que na prática a pilha continua limitada pela memória disponível no sistema (Martins, 2009).

Implementação completa em C++17 ou superior

O programa a seguir reúne as duas implementações em um único código. O cenário utiliza uma cafeteria como contexto: a pilha estática representa bandejas disponíveis, enquanto a pilha dinâmica representa um histórico de operações, situação na qual a política LIFO também é apropriada.

#include <iostream>
#include <string>

using namespace std;

const int CAPACIDADE = 3;

struct ItemCafeteria {
    string nome;
};

// ========================================
// PILHA ESTÁTICA
// ========================================

struct PilhaEstatica {
    ItemCafeteria itens[CAPACIDADE];
    int topo = 0;
};

bool pilhaVazia(const PilhaEstatica& pilha) {
    return pilha.topo == 0;
}

bool pilhaCheia(const PilhaEstatica& pilha) {
    return pilha.topo == CAPACIDADE;
}

bool push(
    PilhaEstatica& pilha,
    const ItemCafeteria& item
) {
    if (pilhaCheia(pilha)) {
        return false;
    }

    pilha.itens[pilha.topo] = item;
    pilha.topo++;

    return true;
}

bool pop(
    PilhaEstatica& pilha,
    ItemCafeteria& itemRemovido
) {
    if (pilhaVazia(pilha)) {
        return false;
    }

    pilha.topo--;

    itemRemovido = pilha.itens[pilha.topo];

    return true;
}

bool consultarTopo(
    const PilhaEstatica& pilha,
    ItemCafeteria& itemTopo
) {
    if (pilhaVazia(pilha)) {
        return false;
    }

    itemTopo = pilha.itens[pilha.topo - 1];

    return true;
}

// ========================================
// PILHA DINÂMICA
// ========================================

struct No {
    ItemCafeteria item;
    No* proximo;
};

bool pilhaVazia(No* topo) {
    return topo == nullptr;
}

void push(
    No*& topo,
    const ItemCafeteria& item
) {
    No* novo = new No{item, topo};

    topo = novo;
}

bool pop(
    No*& topo,
    ItemCafeteria& itemRemovido
) {
    if (pilhaVazia(topo)) {
        return false;
    }

    No* removido = topo;

    itemRemovido = removido->item;

    topo = topo->proximo;

    delete removido;

    return true;
}

bool consultarTopo(
    No* topo,
    ItemCafeteria& itemTopo
) {
    if (pilhaVazia(topo)) {
        return false;
    }

    itemTopo = topo->item;

    return true;
}

void liberarPilha(No*& topo) {
    ItemCafeteria item;

    while (pop(topo, item)) {
    }
}

// ========================================
// PROGRAMA PRINCIPAL
// ========================================

int main() {

    cout << "=== PILHA ESTATICA ===" << endl;

    PilhaEstatica bandejas;

    push(bandejas, {"Bandeja 1"});
    push(bandejas, {"Bandeja 2"});
    push(bandejas, {"Bandeja 3"});

    ItemCafeteria item;

    if (!push(bandejas, {"Bandeja 4"})) {
        cout << "Erro: pilha cheia." << endl;
    }

    if (consultarTopo(bandejas, item)) {
        cout << "Topo: "
             << item.nome
             << endl;
    }

    if (pop(bandejas, item)) {
        cout << "Retirada: "
             << item.nome
             << endl;
    }

    cout << endl;

    cout << "=== PILHA DINAMICA ===" << endl;

    No* historico = nullptr;

    push(
        historico,
        {"Adicionar espresso"}
    );

    push(
        historico,
        {"Adicionar cappuccino"}
    );

    push(
        historico,
        {"Cancelar cappuccino"}
    );

    if (consultarTopo(historico, item)) {
        cout << "Ultima acao: "
             << item.nome
             << endl;
    }

    if (pop(historico, item)) {
        cout << "Acao desfeita: "
             << item.nome
             << endl;
    }

    liberarPilha(historico);

    if (!pop(historico, item)) {
        cout << "Erro: pilha vazia."
             << endl;
    }

    return 0;
}

Entendendo a implementação estática

O elemento central da implementação estática é:

struct PilhaEstatica {
    ItemCafeteria itens[CAPACIDADE];
    int topo = 0;
};

Nela, criamos o vetor que contém os elementos, enquanto topo representa a quantidade atualmente armazenada. Inicialmente, topo = 0, o que significa que não há elementos. Ao empilhar:

pilha.itens[pilha.topo] = item;
pilha.topo++;

primeiro o elemento é colocado na posição atual e, depois, topo é incrementado. Por exemplo:

topo = 2

posição 1 → Bandeja 2
posição 0 → Bandeja 1

A próxima inserção ocorrerá em:

pilha.itens[2]

Depois:

topo = 3

Por que o desempilhamento decrementa primeiro?

Observe o seguinte trecho do código:

pilha.topo--;
itemRemovido = pilha.itens[pilha.topo];

e repare que na hora de desempilhar (pop), decrementamos o topo antes. Isso ocorre porque o topo da pilha sempre está na posição posterior ao último elemento empilhado. Para conseguirmos acessar o último elemento, precisamos da posição, ou índice, imediatamente antes do topo.

Veja só, considere o seguinte:

índice 0 → Bandeja 1
índice 1 → Bandeja 2
índice 2 → Bandeja 3

topo = 3

O último elemento está no índice:

topo - 1

ou seja:

3 - 1 = 2

Por isso o algoritmo primeiro faz:

pilha.topo--;

resultando em:

topo = 2

e então acessa:

pilha.itens[2]

que corresponde à Bandeja 3.

Entendendo a pilha dinâmica

Na implementação dinâmica não usamos mais o vetor e colocamos uma struct no lugar:

struct No {
    ItemCafeteria item;
    No* proximo;
};

Cada nó possui duas informações: o próprio item e o próximo nó.

item
próximo nó

O ponteiro:

No* topo = nullptr;

indica onde está o elemento superior da pilha.

Quando topo == nullptr, não existe nenhum nó e, portanto, a pilha está vazia.

Empilhamento dinâmico

A operação:

No* novo = new No{item, topo};
topo = novo;

pode ser dividida conceitualmente em duas etapas.

Primeiro:

No* novo = new No{item, topo};

cria um novo nó apontando para o antigo topo.

Se tínhamos:

topo
 ↓
[Bandeja 2]
 ↓
[Bandeja 1]

o novo nó passa inicialmente a apontar para Bandeja 2:

[Bandeja 3]
 ↓
[Bandeja 2]
 ↓
[Bandeja 1]

Depois fazemos:

topo = novo;

e o novo elemento torna-se o topo.

topo
 ↓
[Bandeja 3]
 ↓
[Bandeja 2]
 ↓
[Bandeja 1]

Conforme explicita Martins (2009), essa lógica corresponde à implementação dinâmica tradicional de pilhas por estruturas autorreferenciadas.

Desempilhamento dinâmico

Para retirar um elemento, primeiramente guardamos o endereço do nó que será eliminado:

No* removido = topo;

Depois fazemos o topo avançar:

topo = topo->proximo;

e, finalmente, deletamos o nós da pilha dinâmica:

delete removido;

O último comando libera a memória que havia sido alocada pela diretiva new. Ela é especialmente importante em C++ para que o programa não fique ocupando memória quando deixar de ser necessária.

Implementação estática ou dinâmica?

É importante lembrar que ambas as implementações representam o mesmo TAD, apenas possuem características diferentes, tais como:

Então, com as duas possibilidades, temos que verificar quando usar uma ou outra. A pilha estática é mais adequada quando a quantidade máxima de elementos é conhecida previamente ou possui um limite pequeno e bem definido, pois sua implementação com vetor é mais simples e evita o custo de alocação dinâmica de memória.

Já a pilha dinâmica é indicada quando a quantidade de elementos pode variar durante a execução e não é possível prever seu tamanho máximo, pois novos nós são alocados conforme a necessidade. Em contrapartida, essa flexibilidade exige o uso de ponteiros e um cuidado maior com alocação e liberação de memória (Martins, 2009; Ziviani, 2006).

Complexidade das operações

Uma vantagem importante das pilhas é que suas operações fundamentais não precisam percorrer os demais elementos. De acordo com Cormen et al. (2012), as operações fundamentais de uma pilha podem ser executadas em tempo constante O(1). Assim, temos que:

Isso ocorre porque todas essas operações manipulam exclusivamente o topo da estrutura. Portanto, não é necessário percorrer n elementos para encontrar onde inserir ou remover.

Casos especiais e erros comuns

Remover de uma pilha vazia

Considere:

topo
 ↓
vazio

Executar pop nessa situação é uma operação inválida. Esse problema é tradicionalmente denominado underflow, ou estouro negativo (Cormen et al., 2012).

Por isso utilizamos:

if (pilhaVazia(pilha)) {
    return false;
}

para verificar a situação da pilha inicialmente.

Inserir em uma pilha estática cheia

Suponha:

const int CAPACIDADE = 3;

e:

[Bandeja 3]
[Bandeja 2]
[Bandeja 1]

Ou seja, não existe uma quarta posição disponível. A tentativa de realizar outro push caracteriza overflow, isto é, estouro da capacidade da pilha (Cormen et al., 2012).

Por isso verificamos o estado dela com:

if (pilhaCheia(pilha)) {
    return false;
}

Confundir topo com índice

Outro erro comum ocorre quando topo representa a quantidade de elementos, mas o programador tenta utilizá-lo diretamente como índice do último elemento.

Se:

topo = 3

os índices válidos ocupados são:

0
1
2

Consequentemente, o topo real está em:

pilha.itens[pilha.topo - 1]

e não em:

pilha.itens[pilha.topo]

Esquecer de atualizar o topo

Outra falha frequente consiste em inserir ou remover elementos sem atualizar a variável ou ponteiro responsável pelo topo.

Na implementação estática:

pilha.topo++;

e:

pilha.topo--;

mantêm a posição lógica da pilha.

Na implementação dinâmica:

topo = novo;

e:

topo = topo->proximo;

realizam a mesma função conceitual.

Esquecer de liberar memória

Em uma implementação dinâmica em C++, executar:

new No

sem realizar posteriormente:

delete

quando o nó deixa de ser utilizado provoca vazamento de memória (memory leak).

Por isso nossa operação pop executa:

delete removido;

e o programa também possui:

liberarPilha(historico);

para garantir que os elementos restantes sejam desalocados.

Onde as pilhas são utilizadas?

Embora uma pilha de bandejas seja uma boa analogia física, as aplicações computacionais são muito mais abrangentes.

Pilhas são especialmente adequadas quando existe a necessidade de retornar primeiro a informação manipulada mais recentemente. Entre os exemplos clássicos estão chamadas de funções, processamento de expressões, algoritmos recursivos, navegação com retorno e mecanismos de desfazer operações. Ziviani (2006) destaca seu uso em estruturas aninhadas, chamadas de subprogramas, expressões aritméticas e na implementação da recursividade.

Um sistema de cafeteria poderia, por exemplo, utilizar uma pilha para registrar alterações realizadas sobre um pedido:

Adicionar espresso
Adicionar cappuccino
Alterar cappuccino para grande
Cancelar cappuccino

Se o usuário escolher desfazer, a primeira ação revertida deverá ser:

Cancelar cappuccino

Uma segunda operação de desfazer atingiria:

Alterar cappuccino para grande

e assim sucessivamente.

Conclusão

Uma pilha é um Tipo Abstrato de Dados (TAD) linear organizado segundo a política LIFO, na qual inserções, consultas e retiradas acontecem pelo topo. O conceito de pilha deve ser distinguido de sua implementação, pois o mesmo comportamento abstrato pode ser construído utilizando vetores ou estruturas dinâmicas encadeadas.

A implementação estática possui estrutura simples e armazenamento contíguo, mas exige uma capacidade previamente definida. A implementação dinâmica elimina essa capacidade fixa por meio de alocação dinâmica e ponteiros, ao custo de maior complexidade de implementação.

Compreender pilhas também prepara o desenvolvedor para compreender melhor os conteúdos posteriores de Estruturas de Dados, tal como listas encadeadas, árvores, percursos em grafos e gerenciamento explícito de memória.

Obrigado pela leitura e bons estudos!

Referências

CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: Elsevier, 2012.

MARTINS, Paulo Roberto (org.). Algoritmos e estrutura de dados: análise e desenvolvimento de sistemas. São Paulo: Pearson Prentice Hall, 2009.

ZIVIANI, Nivio et al. Projeto de algoritmos: com implementações em Java e C++. Material didático. 2006.