Como fazer pilhas na linguagem C

Novembro 2016


Pilha (stack) = um tipo abstrato de dado e estrutura de dados

Requisitos

Os tipos de dados
As estruturas
O uso do typedef
Os ponteiros
As funções do usuário
As listas simplesmente encadeadas
As listas duplamente encadeadas

Para explicar o algoritmo, eu usarei uma lista simplesmente ligada (ou encadeada). Assim sendo, a compreensão das listas encadeadas é necessária.

O que é uma pilha

A pilha é uma estrutura de dados que armazena os dados na ordem LIFO (Last In First Out) - em português Último a Entrar Primeiro a Sair). Escolhi uma lista ligada simplesmente, 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.

Eu não usei um indicador fino, como eu fiz no caso das listas simplesmente ligadas, já que o objetivo não é abordar uma lista ligada, 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 "seguinte". Este deve ser do semelhante que o elemento, se não 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
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, 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.

Observação:

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 aponta 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.

Operações nas pilhas

Inicialização

Protótipo da função:
void inicialização (Pilha *monte);


Esta operação deve ser feito 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
Alocaçã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.
O que 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++;
}

Tirar 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.

Passos :

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 os dados do 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; }

Veja também

As listas simplesmente encadeadas
As listas duplamente encadeadas
As listas circulares
As filas

Veja também :
Este documento, intitulado « Como fazer pilhas na linguagem C »a partir de CCM (br.ccm.net) está disponibilizado sob a licença Creative Commons. Você pode copiar, modificar cópias desta página, nas condições estipuladas pela licença, como esta nota aparece claramente.