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.
- Pilha em c
- Pilhas em c - Melhores respostas
- Pilha programação - Melhores respostas
- Lista duplamente encadeada em c - Dicas -C
- Variaveis c++ - Dicas -C++
- Condicionais em c - Dicas -C
- Falcon c++ - Downloads - Programação
- Fila em c - Dicas -C
Assine nossa newsletter!
