3
Obrigado

Algumas palavras de agradecimento nunca são demais.

Como fazer pilhas na linguagem C

O objetivo desse artigo é que o leitor entenda o uso das pilhas. Para explicar o algoritmo, utilizaremos uma lista simplesmente encadeada. Assim, a compreensão sobre as listas encadeadas também é necessária.




Requisitos

Os requisitos são os tipos de dados, as estruturas, o uso do typedef, os ponteiros, as funções de usuário, as listas simplesmente encadeadas e as listas duplamente encadeadas.

O que é uma pilha

A pilha é uma estrutura de dados que armazena os dados na ordem LIFO (Last In First Out - Último a Entrar, Primeiro a Sair). A recuperação dos dados é feita na ordem inversa da sua inserção.

Para o nosso exemplo, escolhemos uma lista simplesmente encadeada, apresentada na vertical. Já que a adição é sempre feita no início da lista, o primeiro elemento da lista será o último digitado e ficará no topo da pilha.

Não será utlizado um ponteiro fim, como no caso das listas simplesmente encadeadas, já que o objetivo aqui é gerar uma pilha. O que nos interessa é que o último elemento inserido será o primeiro recuperado:


Elaboração do modelo de um elemento da pilha

Para definir um elemento da pilha, será usado o tipo struct. O elemento da pilha conterá um campo dado e um ponteiro segunte. Ele deve ser da mesma classe do elemento, caso contrário ele não poderá apontar para o elemento. O ponteiro 'seguinte' permitirá o acesso ao próximo elemento:

typedef struct ElementoLista {     
char *dado;
struct ElementoLista *seguinte;
}Elemento;


Para permitir as operações na pilha, vamos salvar alguns elementos: o primeiro elemento e o número de elementos

O primeiro elemento, que se encontra no topo da pilha, nos ajudará a realizar a operação de recuperação dos dados situados no topo da pilha. Para tanto, outra estrutura diferente será utilizada, mas isso não é obrigatório, as variáveis podem ser utilizadas. Veja a composição:

typedef struct ListaDetectada{     
Elemento *início;
int tamanho;
} Pilha;


O ponteiro início tem o endereço do primeiro elemento da lista enquanto a variável tamanho contém o número de elementos.

Não usaremos um ponteiro fim, pois ele não é necessário, já que vamos trabalhar unicamente no início da lista.

Seja qual for a posição na lista, o ponteiro início sempre apontará para o primeiro elemento, que estará no topo da pilha. O campo tamanho abrigará o número de elementos da pilha, independentemente da operação efetuada na pilha.

Operações nas pilhas

Inicialização

Modelo da função:
void inicialização (Pilha *monte);


Esta operação deve ser feita antes de qualquer outra da pilha. Ela inicializa o ponteiro início com o ponteiro NULL e o tamanho com o valor 0.

Função:

void inicialização (Pilha *monte){     
monte->início = NULL;
monte->tamanho = 0;
}

Inserção de um elemento na pilha

A seguir, veremos o algoritmo de inserção e o registro dos elementos: declaração de elementos a ser inseridos, alocação da memória para o elemento seguinte, preencher o conteúdo do campo de dados, atualizar o ponteiro início para o primeiro elemento (topo da pilha) e atualizar o tamanho da pilha.

Modelo da função:

int empilhar (Pilha *monte, char *dado);
.

A primeira imagem mostra o início da inserção, portanto, a lista tem o tamanho 1 depois da inserção. A característica da pilha não está bem realçada com um único elemento, já que é o único a ser recuperado:



Por outro lado, na segunda imagem podemos observar o comportamento da pilha, embora não devemos esquecer que a integração é sempre feita no topo da pilha (no início da lista):



Função:

/* empilhar (adicionar) um elemento da pilha */     
int empilhar (Pilha * monte, char *dado){
Elemento *novo_elemento;
if ((novo_elemento = (Elemento *) malloc (sizeof (Elemento))) == NULL)
return -1;
if ((novo_elemento->dado = (char *) malloc (50 * sizeof (char)))
== NULL)
return -1;
strcpy (novo_elemento->dado, dado);
novo_elemento->próximo = monte->início;
monte-> início = novo_elemento;
monte->tamanho++;
}

Eliminar um elemento da pilha

Para excluir o elemento da pilha, basta excluir o elemento para o qual aponta o ponteiro início. Essa operação não permite recuperar o dado no topo da pilha, mas apenas removê-lo.

Modelo da função:

int desempilhar (Pilha *monte);


A função retorna -1 em caso de falha, caso contrário, retorna 0.

Etapas:

O ponteiro remov_elemento conterá o endereço do primeiro elemento. O ponteiro início apontará para o segundo elemento (após a remoção do primeiro elemento, o segundo passará para o topo da pilha). O tamanho da pilha se reduz em um elemento:



Função:

int desempilhar (Pilha * monte){     
Elemento *remov_elemento;
if (monte->tamanho == 0)
return -1;
remov_elemento = monte->início;
tas-> início = tas->início->próximo;
free (remov_elemento->dado);
free (remov_elemento);
monte ->tamanho--;
return 0;
}

Visualização da pilha

Para exibir a pilha inteira, é preciso se posicionar no início da pilha (você poderá fazer isso com o ponteiro início). Em seguida, usando o ponteiro 'seguinte' de cada elemento, a pilha será percorrida do primeiro até o último elemento. A condição de parada é dada pelo tamanho da pilha.


Função:

/* visualização da pilha */     
void exibe (Pilha * monte){
Elemento *atual;
int i;
atual = monte->início;

for(i=0;i<tas->tamanho;++i){
printf("\t\t%s\n", corrente->dado);
atual = atual->seguinte;
}
}

Recuperação do dado no topo da pilha

Para recuperar o dado no topo da pilha sem removê-lo, usamos uma macro. A macro faz a leitura dos dados no topo da pilha usando o ponteiro início:

#define pilha_dado(monte)  monte->início->dado

Exemplo completo

pilha.h

/*********************\     

  • pilha.h * \*********************/ typedef struct ElementoLista{ char *dado; struct ElementoLista *seguinte; } Elemento; typedef struct ListaDetectada{ Elemento *início; int tamanho; } Pile; /* inicialização */ void inicialização (Pilha *monte); /* EMPILER*/ int empilhar (Pilha *monte, char *dado); /* DESEMPILHAR*/ int desempilhar (Pilha *monte); /* Exibição do elemento no topo da pilha (LastInFirstOut) */ #define pilha_dado(monte) monte->início->dado /* Exibe a pilha */ void exibe (Pilha *monte);

pilha_função.h

/***********************\     

  • pile_function.h * \***********************/ void inicialização (Pilha *monte){ tas->início = NULL; tas->tamanho = 0; } /* empilhar (adicionar) um elemento na pilha */ int empilhar (Pilha * monte, char *dado){ Elemento *novo_elemento; if ((novo_elemento = (Elemento *) malloc (sizeof (Elemento))) == NULL) return -1; if ((novo_elemento-> dado = (char *) malloc (50 * sizeof (char))) == NULL) return -1; strcpy (novo_elemento->dado, dado); novo_elemento->seguinte = monte->início; monte-> início = novo_elemento; monte->tamanho++; } /* desempilhar (excluir um elemento da pilhe */ int desempilhar (Pilha * monte){ Elemento *remov_elemento; if (tas->tamanho == 0) return -1; remov_elemento = monte->início; monte-> início = monte->início->seguinte; free (remov_elemento->dado); free (remov_elemento); monte->tamanho--; return 0; } /* exibição da pilha */ void exibe (Pilha * monte){ Elemento *em curso; int i; em curso = monte->início; for(i=0;i<monte->tamanho;++i){ printf("\t\t%s\n", em curso->dado); em curso = em curso->seguinte; } }

pilha.c

/*********************\     

  • pile.c * \*********************/ #include<stdio.h> #include<stdlib.h> #include<string.h> #include "pile.h" #include "pile_function.h" int main () { Pilha *monte; char *nome; if ((monte = (Pilha *) malloc (sizeof (Pile))) == NULL) return -1; if ((nome = (char *) malloc (50 * sizeof (char))) == NULL) return -1; inicialização (monte); printf ("Entre uma palavra:"); scanf ("%s", nome); empilhar (monte, nome); printf ("A pilha (%de elementos): \n",monte->tamanho); printf("\n********** Topo da PILHA **********\n"); exibe(monte); printf("__________ RodapéÉ da PILHA __________\n\n"); printf ("Entre uma palavra:"); scanf ("%s", nome); empilhar (monte, nome); printf ("A pilha (%de elementos): \n",monte->tamanho); printf("\n********** Topo da PILHA **********\n"); exibe(monte); printf("__________ Rodapé da PILHA__________\n\n"); printf ("Entre uma palavra:"); scanf ("%s", nome); empiler (monte, nome); printf ("A pilha (%de elementos): \n",monte->tamanho); printf("\n********** Topo da PILHA **********\n"); exibe(monte); printf("__________ Rodapé da PILHA __________\n\n"); printf ("\nO último entrado (LastInFirstOut) [ %s ] será excluído", pilha_dado(monte)); printf ("\nO último entrado será excluído\n"); desempilhar (monte); /* remoção do último elemento entrado */ printf ("A pilha (%d elementos): \n",monte->tamanho); printf("\n********** Topo da PILHA **********\n"); exibe(monte); printf("__________ Rodapé da PILHA __________\n\n"); return 0; }


Foto: © Everypixel.
Veja também
Este documento, intitulado 'Como fazer pilhas na linguagem C', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.

Assine nossa newsletter!

Receba toda semana o melhor conteúdo

Assine nossa newsletter!