Pilhas encadeadas

Pilhas Encadeadas Dinâmica
Em uma implementação de pilhas através de apontadores, cada item da pilha é encadeado com o seguinte através de uma variável do tipo Apontador. Este tipo de implementação permite utilizar posições não contíguas de memória, assim como acontece com as listas encadeadas.
É conveniente usar pilhas com apontadores, porque neste caso o tamanho máximo da pilha não precisa ser definido a priori. A maior desvantagem deste tipo de implementação é a utilização de memória extra para armazenar os apontadores.
Quando o número máximo de elementos que serão armazenados na pilha não é conhecido, devemos implementar a pilha com uma estrutura de dados dinâmica, no caso, com uma lista encadeada. Os elementos são armazenados na lista, e a pi¬lha pode ser representada simplesmente por um ponteiro para o primeiro nó da lista(elemento topo). Veja a seguir a implementação da Estrutura da Pilha usando apontador

typedef struct { int chave; /* pode inserir outros elemetos */ } tipoitem;

typedef struct lista { tipoitem item; struct lista * prox; } tipolista;

A estrutura da pilha é então simplesmente:

typedef struct pilha { tipolista * topo; } pilha;
A função cria aloca a estrutura da pilha e inicializa a lista como sendo vazia. pilha * pilha_cria (void)
{
pilha * p = (pilha *) malloc(sizeof(pilha)); p->topo = NULL; return p; }

A pilha estará vazia se a lista estiver vazia: int pilha_vazia (pilha* p)
{
return (p->topo==NULL);
}

O primeiro elemento da lista representa o topo da pilha. Cada novo elemen¬to é inserido no início da lista e, conseqüentemente, sempre que solicitado, reti¬ramos o elemento também do início da lista. A implementação dessas funções é ilustrada a seguir:

Inserindo um item na pilha

/*Funcao para inserir novo item na pilha*/ void pilha_push (pilha* p, tipoitem item) { tipolista * n =