Pilhas

O que são as Estruturas de Dados do tipo Pilha?

A pilha representa um conjunto dinâmico cujos elementos são inseridos e retirados de acordo com o seguinte protocolo: o último elemento que entra no conjunto é o primeiro que sai, por exemplo, a função desfazer do seu editor de textos, que desfaz o último comando de uma pilha de comandos realizados no editor.

Fonte: Shutterstock.

Deseja ouvir este material?

Áudio disponível no material digital.

Praticar para Aprender

Você teve sucesso em sua primeira empreitada como desenvolvedor de uma empresa de jogos digitais e tem atuado criando soluções que ajudam os desenvolvedores a ser mais produtivos em suas tarefas. Dessa vez seu chefe lhe apresentou o seguinte problema: os dados de um jogador (nome, idade, recursos etc.) de determinado jogo que está sendo produzido pela empresa são armazenados em um arquivo de texto denominado “playerData.txt”. Antes de iniciar, o jogo lê esse arquivo e faz as configurações necessárias no sistema. Contudo, bugs estão ocorrendo em virtude de erros existentes nesse arquivo de configuração.

Alguns símbolos de agrupamento, como chaves e colchetes, são usados nesse arquivo para indicar as configurações do jogo. No exemplo a seguir, os colchetes são usados para indicar um conjunto de recursos que o jogador possui e as chaves são usadas para descrever cada tipo de recurso.

Jogador: {
  Nome: “José”
  Idade: 20
  Recursos: [
   { Nome: “Arma com laser”, HP: 20 }
   { Nome: “Poção mágica”, HP: 55 }  
 ]
} 

Uma questão importante a respeito do uso dos símbolos de agrupamento é descobrir se eles foram utilizados de forma correta, isto é, para cada símbolo de abertura deve haver um símbolo corresponder de fechamento. Além disso, esse símbolo de fechamento deve aparecer na ordem correta, “combinando” com seu símbolo de abertura equivalente.

Os exemplos a seguir ilustram o uso (correto e incorreto) de símbolos de agrupamento. O problema é decidir se uma expressão está ou não correta, com relação ao uso dos símbolos de agrupamento:

• (()) – Correto 
• ([]) – Correto 
• (() – Incorreto, falta um parêntese de fechamento 
• ()) – Incorreto, falta um parêntese de abertura
• ([)) – Incorreto, o primeiro parênteses de fechamento não combina com o colchete de abertura.

Seu novo desafio como estagiário é escrever um programa capaz de receber um conjunto de caracteres de símbolos de agrupamento e decidir se esse conjunto de símbolos corresponde a uma expressão correta ou não. Assim, os desenvolvedores poderão verificar a consistência do arquivo de configuração do jogo antes de enviar uma nova versão para os jogadores.

conceito-chave

Pilha

Caro aluno, nesta seção você vai aprender mais uma ED, conhecida como pilha. A pilha representa um conjunto dinâmico cujos elementos são inseridos e retirados de acordo com o seguinte protocolo: o último elemento que entra no conjunto é o primeiro que sai. Esse protocolo é amplamente conhecido como LIFO, do inglês Last in, First out (último a entrar, primeiro a sair).

É possível inserir um elemento na pilha a qualquer momento, mas somente o elemento inserido mais recentemente pode ser removido a qualquer momento. O nome pilha deriva-se da metáfora de uma pilha de pratos em uma cantina ou restaurante (GOODRICH; TAMASSIA, 2013; CORMEN et al., 2012).

A pilha é uma das estruturas de dados mais simples, apesar de estar entre as mais importantes, uma vez que são utilizadas em diversos tipos de situações, desde aplicações de escritório (o comando “desfazer” do editor de texto utiliza o conceito de pilha para armazenar a última alteração feita pelo usuário sobre uma parte do texto) até sistemas operacionais e compiladores (as chamadas a funções de um programa são armazenadas em uma pilha de execução). Há inclusive, operações de pilha implementadas em hardware, com o intuito de melhorar o desempenho das máquinas modernas.

As principais operações que devem estar presentes em uma ED do tipo pilha são:

• criar(): cria e retorna uma pilha vazia.
• empilhar(p, item): também conhecida como push, essa função é responsável por empilhar um “item” no topo da pilha “p”.
• desempilhar(p): também conhecida como pop, essa função é responsável por desempilhar o elemento do topo da pilha “p” e retorná-lo.
• topo(p): retorna o elemento do topo da pilha “p”, sem retirá-lo da mesma pilha.
• tamanho(p): retorna a quantidade de elementos existentes na pilha “p”.
• vazia(p): retorna se a pilha “p” está vazia ou não.
• liberar(p): desaloca a memória ocupada pela pilha “p”.

O Quadro 4.2 apresenta uma série de operações e seus efeitos sobre uma pilha inicialmente vazia. Considere que o elemento mais à direita do conjunto de dados da pilha representa o topo da pilha.

Assim como no caso da ED lista, podemos implementar uma pilha de pelo menos duas formas: utilizando vetores ou utilizando estruturas ligadas (ou encadeadas). Nesta seção, será apresentada a implementação por meio de estruturas ligadas.

Pilha ligada

Observe a ilustração de uma pilha ligada, na Figura 4.7.

Uma pilha ligada consiste em uma sequência de elementos, denominados nós (representados por retângulos com uma seta em uma de suas extremidades na Figura 4.7). Cada nó tem uma informação (valor que aparece dentro do retângulo) e um ponteiro para o próximo nó da pilha (seta na extremidade direita do retângulo). O último nó da pilha (que está na sua base) aponta para NULL, representando que não existe um próximo nó na pilha. A pilha propriamente dita é representada apenas por um ponteiro para o nó do que está no topo da pilha, chamado de Topo na Figura 4.7.

Caro aluno, chegou a hora de você implementar a sua primeira pilha ligada. Você pode iniciar criando algumas structs. Vamos criar uma struct para representar cada nó da nossa pilha ligada e outra para representar a pilha propriamente dita. Mas, antes disso, vamos importar todas as bibliotecas que usaremos nos códigos desta seção.

#include <stdio.h>  // para operações de entrada e saída
#include <stdlib.h>  // para alocação dinâmica de memória
#include <stdbool.h> // para uso do tipo de dados “bool”
#include <assert.h>  // para uso da instrução “assert”

Feito isso, agora podemos observar o conteúdo das structs criadas para a pilha.

struct No {
  int info;
  struct No* proximo;
};

struct Pilha {
  struct No* topo;
  int tamanho;
};

A struct “No” é idêntica à que foi criada para a lista simplesmente ligada. A struct “Pilha” também é bastante similar, diferenciando apenas o nome da estrutura, bem como o nome do ponteiro para a struct “No”, que aqui se chama “topo”, indicando que ele aponta para o topo da pilha.

Assim como fizemos com a ED lista, partiremos para a implementação das funções da pilha, uma a uma, comentando uma delas ao longo do texto. No Código 4.20 encontra-se o código da função “criar”.

struct Pilha* criar() {
    struct Pilha* nova_pilha = (struct Pilha*) malloc(sizeof(struct Pilha));
    if (nova_pilha != NULL) {
        nova_pilha->topo = NULL;
        nova_pilha->tamanho = 0;
    }
    return nova_pilha;
} 

Essa função é responsável por instanciar dinamicamente uma variável do tipo struct “Pilha” na memória (linha 2) e configurar os valores de seus campos. Antes, porém, de configurar os valores dos campos da struct “Pilha”, é preciso testar se a memória foi corretamente alocada para a pilha (linha 3). O campo “topo”, que é um ponteiro, deve apontar para NULL, uma vez que estamos criando uma pilha vazia (linha 4). Analogamente, o campo “tamanho” deve ser inicializado com o valor igual a 0 (zero) – linha 5. Feito isso, deve-se retornar o endereço da memória alocado para a variável do tipo “Pilha” (linha 7). Com isso, nós já somos capazes de criar uma pilha vazia na memória do computador.

Passemos, então para a implementação das duas funções mais importantes da pilha, a saber “empilhar” e “desempilhar”. O código dessas funções pode ser visualizado no Código 4.21.

void empilhar(struct Pilha* p, int item) {
    assert(p != NULL);    
    struct No* novo_no = (struct No*) malloc(sizeof(struct No));
    if (novo_no != NULL) {
        novo_no->info = item;
        novo_no->proximo = p->topo;
        p->topo = novo_no;
        p->tamanho++;
    }
}
int desempilhar(struct Pilha* p) {
    assert(p != NULL);    
    assert(p->topo != NULL);
    struct No* aux = p->topo;
    int elemento = aux->info;
    p->topo = aux->proximo;
    p->tamanho--; 
    free(aux);
    return elemento;    
}

Tanto a função “empilhar” quanto a “desempilhar” inicialmente verificam se o ponteiro para a pilha passada como parâmetro não é nulo (NULL) – linhas 2 e 12, respectivamente. 

Feito isso, a função “empilhar” cria um novo nó dinamicamente, o que é feito na linha 3, por meio da função “malloc”. Caso o novo nó tenha sido criado com sucesso, isto é, se o valor do ponteiro “novo_no” é diferente de NULL (linha 4), parte-se para o processo de empilhamento do nó. Como vimos, em uma pilha os nós são inseridos apenas em seu topo. Por isso, deve-se apontar o ponteiro “proximo” do novo nó para o topo da pilha (linha 6) e, depois, apontar o ponteiro “topo” da pilha para o novo nó (linha 7). Esse procedimento fará com que o antigo topo da pilha passe a ser o segundo elemento dela e o novo nó passe a ocupar o topo da pilha. Por fim, incrementa-se o tamanho da pilha, na linha 8.

A função “desempilhar” faz o inverso da função “empilhar”. Ou seja, ela remove o elemento que está no topo da pilha, fazendo com que o segundo elemento passe a ocupar o topo da mesma pilha. Para isso, inicialmente é verificado se a pilha não está vazia (linha 13).

Uma vez feito isso, cria-se um nó auxiliar que aponta para o topo de pilha (linha 14). Isso é necessário, pois como o ponteiro “topo” da pilha será atualizado, precisamos guardar a posição de memória do elemento que estava anteriormente no topo. Logo após, o valor do elemento que está no topo da pilha é armazenado na variável “elemento” (linha 15) e o ponteiro “topo” da lista é atualizado (linha 16). A partir de então, o topo da pilha passa a ser ocupado pelo segundo elemento, caso haja um. Caso contrário, o topo da pilha passa a ser igual a NULL, indicando que a pilha está vazia. Contudo, ainda restam algumas instruções a serem executadas, como decrementar o tamanho da pilha (linha 17), liberar a memória alocada para o nó que ocupava o topo da pilha anteriormente (linha 18) e retornar o valor armazenado na variável “elemento” (linha 19).

 Com isso, já podemos começar a usar nossa pilha, cujo código completo se encontra a seguir, na ferramenta Paiza.io.

Para usar a ES pilha, crie uma função “main” em seu programa, com o código do Código 4.22.

int main() {
    struct Pilha* minha_pilha = criar();
    empilhar(minha_pilha, 1);
    empilhar(minha_pilha, 2);
    empilhar(minha_pilha, 3);

    printf("%d ", desempilhar(minha_pilha));
    printf("%d ", desempilhar(minha_pilha));
    printf("%d ", desempilhar(minha_pilha));

    return 0;
}

Inicialmente, cria-se uma pilha vazia (linha 2). Logo após, os elementos 1, 2 e 3 são empilhados, nessa ordem, por meio da função “empilhar” (linhas 3 a 5). Por fim, todos os elementos da pilha são desempilhados e impressos na tela (linhas 7 a 9).

 Teste o programa no Paiza.io, cuja saída esperada é a impressão dos números 3, 2 e 1, nessa ordem.

Exemplificando

A seguir temos um exemplo de algoritmos com ED pilha que seja capaz de imprimir uma sequência de 5 (cinco) números informados pelo usuário na ordem inversa da entrada, ou seja, de trás para frente. Por exemplo, dada a sequência [1, 2, 4, 0, 3], seu programa deve imprimir [3, 0, 4, 2, 1].

Uma possível solução para esse problema encontra-se a seguir. Inicialmente, criamos um laço for para ler os dados de entrada, adicionando-os em uma pilha. Depois, desempilhamos os elementos da pilha, imprimindo-os na tela. A própria característica da ED pilha fará com que os elementos sejam impressos na ordem inversa.

int main() {
    struct Pilha* minha_pilha = criar();
    int num;
     
    for(int i = 0; i < 5; i++) {
        scanf("%d", &num);
        empilhar(minha_pilha, num);
    }   
 
    for(int i = 0; i < 5; i++) {
        printf("%d ", desempilhar(minha_pilha));
    }   
    return 0;
}

O código completo pode ser visto a seguir, utilizando a ferramenta Paiza.io.

Agora podemos concluir a implementação da pilha com as funções que ainda restam, a saber “tamanho”, “topo”, “vazia” e “liberar”. Vamos começar pelo código das funções “tamanho” e “topo” (Código 4.24).

int topo(struct Pilha* p) {
    assert(p != NULL);
    assert(p->topo != NULL);
    struct No* topo = p->topo;
    return topo->info;
}
int tamanho(struct Pilha* p) {
    assert(p != NULL);
    return p->tamanho;
}

Ambas as funções verificam se o ponteiro “p”, passado como parâmetro, não é nulo (linhas 2 e 8). A função “topo”, entretanto, também verifica se o ponteiro “topo” da pilha não é nulo (linha 3). Isso é importante, pois o valor do nó apontado por “topo” será lido e retornado pela função. Nas linhas 4 e 5 da função “topo”, é criada uma variável auxiliar que aponta para o nó que está no topo da pilha (linha 4) e, depois, o valor armazenado nesse nó é retornado pela função (linha 5). Para a função “tamanho”, após verificar se o ponteiro “p” não é nulo, o valor do campo “tamanho” da struct “Pilha” é retornado (linha 9).

Chegamos, então às últimas duas funções da ED pilha, “vazia” e “liberar”, as quais são apresentadas no Código 4.25.

bool vazia(struct Pilha* p) {
    assert(p != NULL);
    return (p->topo == NULL);
}

void liberar(struct Pilha* p) {
    assert(p != NULL);
    while(vazia(p) == false) {
       desempilhar(p); 
    }
    free(p);
}

Novamente, ambas as funções verificam se o ponteiro “p”, passado como parâmetro, não é nulo (linhas 2 e 7). Para checar se a pilha está vazia, a função “vazia” simplesmente compara o ponteiro “topo” da pilha a NULL (linha 3). O resultado dessa comparação lógica será retornado como resultado da linha, ou seja, se “topo” for igual a NULL, então a função “vazia” retornará “true”, indicando que a pilha se encontra vazia. Caso contrário, a função retornará “false”.

Quanto à função “liberar”, ela faz uso da função “vazia”, recém-apresentada. A lógica é simples: enquanto a pilha não estiver vazia (linha 8), isto é, enquanto o retorno da função “vazia” for igual a “false”, então a função “desempilhar” deve ser invocada (linha 9). Isso é importante para que todos os elementos da ED sejam desalocados corretamente. Ao final, o espaço de memória reservado para a pilha também deve ser desalocado (linha 11).

 Assim a nossa pilha está completa e funcional. Você pode acessar o código dela a seguir, utilizando a ferramenta Paiza.io.

int main() {
    struct Pilha* minha_pilha = criar();

    printf("Está vazia (1 - SIM; 0 - NÃO)? %d\n", vazia(minha_pilha));

    printf("Empilhando 1... \n");
    empilhar(minha_pilha, 1);
    printf("Empilhando 2... \n");
    empilhar(minha_pilha, 2);
    printf("Empilhando 3... \n");
    empilhar(minha_pilha, 3);

    printf("Está vazia (1 - SIM; 0 - NÃO)? %d\n", vazia(minha_pilha));

    printf("Topo = %d\n", topo(minha_pilha));
    printf("Tamanho = %d\n", tamanho(minha_pilha));

    printf("Desempilhando elementos: ");
    printf("%d ", desempilhar(minha_pilha));
    printf("%d ", desempilhar(minha_pilha));
    printf("%d ", desempilhar(minha_pilha));

    liberar(minha_pilha);	

    return 0;
}

Faça valer a pena

void empilhar(struct Pilha* p, int item) {
   assert(p != NULL);    
   struct No* novo_no = (struct No*) malloc(sizeof(struct No));
   if (novo_no != NULL) {
       novo_no->info = item;
       ______________________
       ______________________
       p->tamanho++;
   }
}

Referências

AULA 38 – Pilha: Definição. [S. l.], 10 dez. 2013. 1 vídeo (3 min. 43 s.). Publicado pelo canal Linguagem C Programação Descomplicada. Disponível em: https://bit.ly/2Yqd0Uq. Acesso em: 18 jan. 2021.

CORMEN, T. H. et al. Algoritmos: teoria e prática. São Paulo: Elsevier, 2012.

GOODRICH, M. T.; TAMASSIA, R. Estruturas de dados & algoritmos em java. 5. ed. Porto Alegre: Bookman Editora, 2013.

MILLER, B.; RANUM, D. Símbolos Balanceados. In: MILLER, B.; RANUM, D. Resolução de problemas com algoritmos e estruturas de dados usando Python. Símbolos Balanceados.Tradução de Andrew Toshiaki Nakayama Kurauchi, Carlos Eduardo Leão Elmadjian, Carlos Hitoshi Morimoto e José Coelho de Pina. IME-USP: [s. d.]. Disponível em: https://bit.ly/3t2oawy. Acesso em: 18 jan. 2021.

STACK using linked list animation. [S. l.], [s. d.]. 1 vídeo (1 min. 44 s.). Publicado pelo canal Acme Groups. Disponível em: https://bit.ly/3oyUe80. Acesso em: 18 jan. 2021.

THE HUXLEY. Anagramas a partir de pilhas. The Huxley, 18 ago. 2014. Disponível em: https://bit.ly/2M5a8tD. Acesso em: 18 jan. 2021.

THE HUXLEY. Página inicial. The Huxley, [s. d.]. Disponível em: https://www.thehuxley.com. Acesso em: 12 jan. 2021.

THE HUXLEY. Pilhas com Listas. The Huxley, 6 maio 2015. Disponível em: https://bit.ly/3tdzJBl. Acesso em: 18 jan. 2021.