Pilha Dinâmica

Como já demonstrado antes aqui, a linguagem C/C++ tem o potencial de alocar a memória do computador sobre demanda.

Que tal aproveitarmos este potencial para criar uma pilha dinâmica?

Para resolver isto vamos focar em alguns detalhes:

• A pilha é uma lista com restrição de entrada e saída, ou seja, é acessada pelo topo.
• Para inserir um elemento é necessário empilhar este elemento no topo da pilha.
• Para retirar um elemento, nos desempilhamos do topo da pilha.
• (… nem venham me falar que isto é redundante…)
• Então precisamos de manter um ponteiro para o topo da lista.
• Devemos criar uma estrutura (struct) que contenha o elemento, e um ponteiro para o próximo elemento (o que esta abaixo).

Vejamos graficamente como funciona este conceito, acompanhe a imagem e o vídeo abaixo:

Exemplos by: http://mda.codeplex.com/

Agora, com esta parte funcional esclarecida, vejamos um breve exemplo de código de uma pilha dinâmica em C, construída em cima da lista dinâmica:

#include <stdio.h>
#include <stdlib.h>

struct Item
{
    int numero;
    struct Item *proximo;
};

void Inicializar(Item **topo)
{
   *topo = NULL;
}

bool EstaVazia(Item **topo)
{
   if(*topo == NULL)  
      return true;  
   else  
      return false;  
}

void Empilhar(Item **topo, int elemento)
{
    Item *novo;
    novo = (Item *)malloc(sizeof(Item));  
    novo->numero = elemento;
    novo->proximo = *topo; // -> próximo recebe o elemento que estava no topo.
    *topo = novo;
}

int Desempilhar(Item **topo)
{
   int result;
   Item *auxiliar;
   if(EstaVazia(topo))
   {
        printf("\n stack underflow! \n");
        exit(1);
   }
   else // -> Elemento retirado do topo
   {
        result = (*topo)->numero;
        auxiliar = *topo;
        *topo = (*topo)->proximo;
        free(auxiliar);
        return result;
   }  
}

void MostrarPilha(Item *topo)
{
    int i = 0;
    Item *item;
    printf("\n\n Listando...\n\n");
    printf("---------------------------------\n");

    if (EstaVazia(&topo))
    {
        printf ("A Pilha esta vazia!\n");
    }
    else
    {      
        item = topo;

        while(item != NULL)
        {
            i++;
            printf("[%i] -> %i\n", i, item->numero);
            item = item->proximo;
        }
    }

    printf("---------------------------------\n");
}

void Menu()
{
    printf( "Digite a sua escolha: \n"
        "    1 empilhar elemento \n"
        "    2 desempilhar \n"
        "    3 para finalizar \n"
        "? ");
}

void main()
{   
    Item *topo = NULL;
    int opcao;
    int numero;

    Menu();
    scanf("%i", &opcao);

    while (opcao != 3)
    {

        switch (opcao)
        {
            case 1:
                printf( "Digite um numero: ");
                scanf("\n%i", &numero);

                Empilhar(&topo, numero);
                MostrarPilha(topo);

                break;
            case 2:
                Desempilhar(&topo);
                MostrarPilha(topo);

                break;

            default:
                printf( "Escolha invalida.\n\n");
                Menu();
                break;
        }

        scanf("%i", &opcao);   
    }

    system("pause");
}

Por ser uma lista com restrição, este exemplo chega a ser bem simples perto da lista dinâmica.

Só vale ressaltar:

• Para inserir, é necessário empilhar, ou seja: Alocar um novo item na memória, fazer com que o item do topo se torne o próximo do novo item, finalmente, o ponteiro do topo deve apontar para o novo elemento.
• Para remover, énecessário retirar o item do topo, assim: Criamos um ponteiro auxiliar que recebe o endereço de memória do conteúdo do topo, o topo deverá receber o próximo (dele mesmo), finalmente, liberamos a memória do conteúdo da variável auxiliar.

Hora da diversão:

• Implemente a pilha com uma estrutura de aluno, que tenha RA (inteiro), Nome (char de 50).

Obrigado, espero que tenha sido esclarecedor. :)