Como fazer pilhas na linguagem C

Dezembro 2017

O recurso para construir pilhas (stack) diz repeito a um tipo abstrato de estrutura de dados e os requisitos são os diferentes tipos de dados, as estruturas, o uso do typedef, os ponteiros e as funções do usuário. Leia os artigos Listas simplesmente encadeadas e Listas duplamente encadeadas, que são necessários para a compressão dessa dica.


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). Escolha uma lista simplesmente encadeada, apresentada na vertical. A adição é sempre feita no início da lista, o primeiro elemento da lista será o último digitado; assim, a sua posição fica no topo da pilha. Não usei um indicador fino, como no caso das listas simplesmente encadeadas, já que o objetivo não é abordar uma lista encadeada, mas a pilha. O que nos interessa é que o último elemento inserido seja o primeiro recuperado:




Como construir um protótipo de um elemento da pilha

Para estabelecer um elemento da pilha será usado o tipo struct. O elemento da pilha conterá um campo dado e um ponteiro 'segunte'. Este deve ser semelhante ao elemento, caso contrário ele não poderá apontar para o elemento. O indicador 'seguinte' permitirá o acesso para o 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 (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 inicial tem o endereço do primeiro elemento da lista. Nós não vamos usar um indicador fino desta vez (veja as listas simplesmente encadeadas), pois não precisamos, já que só trabalharemos com o início da lista. Seja qual for a posição na lista, o ponteiro de início sempre apontará para o primeiro elemento, que estará no topo da pilha. O espaço (tamanho) abrigará o número de elementos da pilha, independentemente da operação efetuada na pilha.

Como são as operações nas pilhas

Inicialização

Protótipo da função:
void inicialização (Pilha *monte);
. Esta operação deve ser feita antes de qualquer outra operação da pilha. Ela inicializa o ponteiro do início com o indicador NULL início e o tamanho com o valor 0.

A função:

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

Inserção de um elemento na pilha

Veja o algoritmo de inserção e de backup dos componentes: declaração de elementos a serem inseridos; locação da memória para o novo elemento; preencher o conteúdo do campo de dados; atualizar o ponteiro do início para o primeiro elemento (o topo da pilha); atualizar o tamanho da pilha; protótipo da função:
int empilhar (Pilha *monte, char *ado);
. 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):


A 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 (remover ou desempilhar) o elemento da pilha, basta excluir o elemento para o qual aponta o ponteiro de início. Esta operação não permite recuperar o dado no topo da pilha, mas apenas removê-lo. Protótipo da função:


int desempilhar (Pilha *monte);

A função retorna -1 em caso de falha, caso contrário, ela retorna 0: o ponteiro remov_elem conterá o endereço do primeiro elemento; o ponteiro de 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 será decrementado de um elemento:


A 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;
}

Exibir a pilha

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


A função:

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

for(i=0;i<tas->tamanho;++i){
printf("\t\t%s\n", corrente->dado);
em curso = em curso->próximo;
}
}

Recuperação do dado no topo da pilha

Para recuperar o dado no topo da pilha sem removê-lo, eu usei um macro. O macro faz a leitura dos dados no topo da pilha usando o ponteiro inicial:


#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);

pile_function.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; } }

pile.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; }

Você pode ler este artigo para aprofundar o assunto: As listas circulares e As filas em linguagem.

Foto: © Ktchung - 123RF.com

Veja também

Artigo original publicado por Carlos-vialfa. Tradução feita por pintuda. Última modificação: 1 de dezembro de 2017 às 12:47 por Pedro.CCM.
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.
Linguagem C: estruturas condicionais
As filas em linguagem C