Estrutura de dados 2 - Pilha

Poker chips, por: Jamie Adams (CC-by-SA 2.0).

Dando continuidade ao assunto de estruturas de dados, hoje falaremos sobre pilhas, incluindo aplicações diretas e implementação (estática e dinâmica) na linguagem C.


Índice - Estruturas de dados

1 - Lista encadeada
2 - Pilha
3 - Fila
4 - Árvore binária

Definição de uma pilha e operações

O nome já deve dar uma boa ideia de como funciona a pilha — exatamente como uma pilha física, por exemplo de fichas. Esta estrutura também é conhecida como LIFO, Last In First Out, ou seja, o último que entra é o primeiro que sai. Todas as operações lidam diretamente com o topo da pilha: tanto para remover quanto adicionar elementos.

Em termos mais abstratos, uma pilha é uma estrutura composta por um conjunto de dados (vetor ou lista encadeada) e uma variável para indicar onde está o topo. Considere a seguinte pilha, cujo vetor v está preenchido até a posição 2:

Para adicionar um elemento, vamos atualizar o topo da pilha e inseri-lo nesta nova posição:

Se quisermos remover um elemento, é só questão de atualizar o topo. Note que o elemento teoricamente continua lá, mas na prática cria o efeito de estar fora da pilha. Quando inserirmos um novo elemento, o último será apagado:

Nossa implementação básica utilizará as seguintes operações:

- Inicializar pilha;
- Verificar se pilha está vazia;
- Verificar se pilha está cheia;
- Inserir elemento na pilha;
- Remover elemento da pilha.

Implementação em C com vetores

A implementação estática, usando vetores, é bem intuitiva e simples, com a desvantagem de ser necessário fixar um tamanho inicial. Definição e inicialização da pilha:


#define SIZE 20
typedef int tipoElem;


typedef struct {
        tipoElem dados[SIZE];
        int topo;
} Pilha;


Pilha novaPilha() {
      Pilha p;
      p.topo = -1;
      return p;
}

Fazemos com que o topo seja -1, porque na hora de acrescentar um elemento incrementamos o topo por 1. Desse modo, o primeiro elemento fica na posição 0 do vetor. Observe:


void push(Pilha *p, tipoElem elem) {
     if(!pilhaCheia(p))
                     p->dados[++p->topo] = elem;
     else printf("Stack overflow");
}

Ah, sim, geralmente chamamos essa operação de "push", equivalente a "empilhar". No caso do "desempilhar", usamos "pop":


tipoElem pop(Pilha *p) {
         if(!pilhaVazia(p))
                        return(p->dados[p->topo--]);
         else return OBJ_ERRO;
}

De onde diabos vieram esses pilhaCheia e pilhaVazia? Bem, aí deixo por sua conta. Como verificar se uma lista está cheia ou vazia, considerando que o número máximo de elementos no vetor é dado por SIZE? Pense um pouco nisso.

Implementação em C com lista encadeada

Claro, a implementação acima é satisfatória, mas e se precisarmos lidar com uma pilha de tamanho variável? Uma que continue alocando memória enquanto precisarmos — e, claro, houver memória no PC? Aí entra a estrutura de lista encadeada. Assim como o vetor é a estrutura de dados que compõe a pilha estática, a lista encadeada compõe a pilha dinâmica. Podemos imaginar que as estruturas mais complexas são formadas pelas básicas, portanto.

Há vários caminhos possíveis dependendo de suas decisões de projeto, mas a ideia básica aqui é que a pilha seja apenas um caso especial (na verdade é bem comum, mas você entende) de lista encadeada. Os elementos da pilha não se encontram em um bloco contínuo, mas inseridos em células de forma que uma célula aponte para a célula seguinte. Confira novamente a ilustração de uma lista encadeada:

Não faz sentido para você? Imagine que se tenha um único prato na louça. Podemos dizer que nossa pilha de louça tem apenas um elemento, mas podemos ligar o prato a outros para aumentar o tamanho da pilha. Se ligarmos dois pratos individuais, cada um constituindo uma louça de tamanho unitário, teremos uma louça (pilha) maior através dessa ligação. Agora veja um pouco de código:


typedef int tipoElem;


typedef struct pilha {
        tipoElem dado;
        struct pilha *prox;
} Pilha;


Pilha * novaPilha() {
      Pilha *head;
      head = malloc(sizeof(Pilha));
      head->dado = (tipoElem) NULL;
      head->prox = NULL;
      return head;
}

Ora, mas... é um copy-paste descarado de uma lista encadeada! Exato, assim como uma lista, uma pilha consiste de várias células encadeadas. Quando a pilha está vazia, temos apenas uma célula head, que serve para apontar ao próximo elemento. Outro fato importante é que o resto do programa, o método main por exemplo, vai manipular apenas a cabeça da pilha. Com ela podemos inserir elementos:


void push(Pilha *head, tipoElem elem) {
     Pilha *novaPilha;
     novaPilha = malloc(sizeof(Pilha));
     novaPilha->dado = elem;
     novaPilha->prox = head->prox;
     head->prox = novaPilha;
}

E removê-los:


tipoElem pop(Pilha *head) {
         tipoElem elem;
         Pilha *pilhaRemovida = head->prox;
         
         if(pilhaVazia(head))
                       return OBJ_ERRO;
         
         head->prox = pilhaRemovida->prox;
         elem = pilhaRemovida->dado;
         free(pilhaRemovida);
         return elem;
}

Nenhuma novidade aqui também. Estamos inserindo elementos logo após a head, então eles estarão automaticamente à frente de todos os dados já existentes na pilha. Também removemos um elemento logo após a head, à frente dos demais. Pronto, está feita nossa pilha.

Aplicações e exercícios

Podemos encontrar pilhas até mesmo no nível de arquitetura de hardware. Na memória do computador há uma área especial chamada de pilha, e lá a memória é alocada e acessada de forma dinâmica através de um ponteiro de hardware — geralmente na forma de um registrador. Leia mais sobre o assunto no artigo da Wikipédia.

Outros usos notáveis são a pilha de execução de um programa e em algumas situações de inteligência artificial. A pilha de execução é especialmente notável em funções recursivas, nas quais o problema maior só pode ser resolvido combinando-se as respostas para os problemas menores. O computador vai criando espaços na memória para alocar as variáveis e parâmetros, um em cima do outro, conforme as funções são chamadas. A última chamada é a primeira a ser resolvida.

Quanto à inteligência artificial, podemos imaginar que nosso algoritmo tem várias escolhas a cada passo e apenas a combinação adequada de escolhas leva à resposta. Um labirinto, por exemplo. Uma abordagem comum é ir testando um por um: se uma escolha não levar a nada, teste a outra, senão a outra... Não é possível avançar mais? Então volte à última escolha e selecione outro caminho. Esse "volte à última escolha" pode ser um processo de desempilhar.

Claro, isso sem contar as inúmeras situações nas quais esta estrutura de dados é útil. Vejamos algumas:

• Socorram-me, subi no ônibus em Marrocos: Dada uma string, verifique se ela é palíndromo. Uma sequência de caracteres é dita palíndromo se a sequência composta pelos caracteres em ordem inversa é igual à sequência original. Por exemplo, "Bob", "Stanley Yelnats" e "abba".

• atrevnI a medro: Dada uma frase, inverta a ordem dos caracteres de cada palavra. Por exemplo, "Inverta a ordem" ficaria "atrevnI a medro".

• A torre: Você conhece a Torre de Hanói? Em caso negativo, fiz um post abordando alguns jogos de raciocínio lógico, incluindo a Torre de Hanói. Se já conhece, parabéns, agora faça um algoritmo que a resolva. A função deve receber o número de discos e 3 inteiros para representar as torres.

• Parênteses e colchetes everywhere: Dada uma sequência composta por vários parênteses e colchetes, como "[ ( [ ] ( ) ) ]", verifique se a expressão é válida. Como assim? Bem, como você deve saber, é preciso fechar parênteses e colchetes na ordem inversa em que são escritos: o primeiro que se abre é o último a ser fechado. Por exemplo, "[ ( ] )" é inválido, pois o colchete deveria ser fechado por último.

Fontes

Estrutura de dados: pilhas
Pilha em C (implementação dinâmica)
Stack - Wikipedia
stack - Dictionary of Algorithms and Data Structures