Listas Especializadas: Pilha

A pilha é uma lista! Porém ela tem uma disciplina de acesso: A inserção de um novo item, ou a remoção de um item já existente, se dá em uma única extremidade (topo), exatamente como uma pilha de pratos de cozinha.

… Ou seja: o último prato que empilhamos é o primeiro a ser lavado, ou utilizado.

Enfim, o último elemento que entrou na pilha é sempre o primeiro a sair e o primeiro que entrou é sempre o último a sair da pilha, acompanhe o funcionamento na figura:

Após esta imagem já percebemos que a exclusão de um elemento é tratada de forma diferenciada.

As pilhas são conhecidas em inglês como Stack ou LIFO (Last In First Out = Último que Entra é o Primeiro que Sai).

Reforçando: Uma pilha estática é uma lista estática em que todas as inserções, remoções e geralemente os acessos são realizados em apenas um extremo da lista: o topo.

Suas aplicações são diversas: já pensou como o sistema operacional organiza a ordem das janelas abertas? Ou como um algoritmo recursivo funciona?

Veja um exemplo de sua implementação na linguagem C:

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

const int MAX = 10;

struct Aluno
{
    int ra;
    char nome[50];
};

struct Pilha
{
    Aluno alunos[MAX];
    int topo;
};

void IniciarPilha(Pilha &pilha)
{
        pilha.topo = 0;
}

bool PilhaEstaVazia(Pilha &pilha)
{
    return pilha.topo == 0;
}

bool PilhaEstaCheia(Pilha &pilha)
{
    return pilha.topo == MAX;
}

bool Empilhar(Pilha &pilha, Aluno &item)
{
    if (!PilhaEstaCheia(pilha))
    {
        pilha.alunos[pilha.topo] = item;
        pilha.topo++;
        return true;
    }
    else
    {
        return false;
    }
}

void Desempilhar(Pilha &pilha, Aluno &alunoDesempilhado)
{
    pilha.topo--;
    alunoDesempilhado = pilha.alunos[pilha.topo];
}

void Listar(Pilha pilha)
{
    printf("\nListando...\n");

    while (!PilhaEstaVazia(pilha))
    {
        Aluno alunoDesempilhado;
        Desempilhar(pilha, alunoDesempilhado);
        printf("\n%i - %s", alunoDesempilhado.ra, alunoDesempilhado.nome);
    }

    getch();
}

void main()
{
    char opcao;
    Pilha pilha;

    // -> Inicializando a pilha.
    IniciarPilha(pilha);

    do
    {
        system("cls");
        printf("Escolha a opcao desejada:");
        printf("\n 1- Empilhar um Aluno");
        printf("\n 2- Desempilhar um Aluno");
        printf("\n 3- Listar todos os elementos da pilha");
        printf("\n 0- Sair do programa\n");
        printf("\n Opcao: ");

        opcao = getchar();

        switch(opcao)
        {
            case '1':
                Aluno aluno;

                printf(" \nDigite um nome para o Aluno: ");
                scanf("%s", &aluno.nome);

                printf(" \nDigite um RA para o Aluno: ");
                scanf("%i", &aluno.ra);

                Empilhar(pilha, aluno);
                break;
            case '2':
                Aluno alunoDesempilhado;
                Desempilhar(pilha, alunoDesempilhado);
                printf(" \nAluno %i - %s desempilhado", alunoDesempilhado.ra, alunoDesempilhado.nome);
                getch();
                break;
            case '3':
                Listar(pilha);
                break;
            case '0':
                return;
        }
    }while(opcao != 0);
}

Com estes algoritmos montamos uma pilha com uma estrutura baseada na figura abaixo:

Acompanhe as saídas de exemplo:

Hora de refletir e se divertir:

1) Implemente o exemplo dado anteriormente com ponteiros.

2) Implemente uma função que retorne o número de posições livres da pilha, para as duas implementações (referência e ponteiros).

3) Implemente uma função que localize um dado específico (cujo nome for igual a...) para as duas implementações da pilha (referência e ponteiros). A função deve retornar na tela a posição do dado no vetor bem como as informações armazenadas sobre ele.

Boa diversão :)