Estruturas de dados em computação é um tema extremamente amplo e, provavelmente durante seus estudos, assim como eu, você já deve ter se perguntado por que tantas estruturas de dados diferentes.
A principal questão é que cada uma possui suas características próprias. Assim, cada uma tem suas aplicações. O mesmo acontece com a estrutura do tipo Pilha, bem semelhante a uma pilha de pratos onde apenas é possível retirar ou colocar um novo prato no topo da pilha.
Toda vez que escrevemos um programa recursivo, estamos indiretamente usando uma pilha controlada pelo Sistema Operacional (SO). Em cada chamada recursiva, o SO tira como que uma “fotografia” do estado de todas as variáveis do seu programa envolvidas na recursão e insere em uma pilha (operação push ou empilhar). Isso, em cada chamada recursiva. Ao terminar a recursão, o SO inicia o processo de desempilhar (operação pop), finalizando cada chamada recursiva. É assim que o computador sabe exatamente o valor da cada variável lá na milésima chamada recursiva rsrs.
Outro exemplo comum são as operações desfazer e refazer presente em muitos softwares. Cada uma dessas operações gerenciam uma pilha. Funciona mais ou menos assim: você abre o software de edição de texto por exemplo, a cada ação que você executa um registro dessa ação é empilhado na pilha da função desfazer; quando você pressiona as teclas ctrl + z ou pressiona o botão desfazer, a última ação empilhada é desempilhada, desfeita e empilhada na pilha da opção refazer. Dessa forma é possível ir alterando entre as opções desfazer e refazer.
Como dito anteriormente, uma estrutura do tipo pilha admite basicamente duas operações, empilhar (push) e desempilhar (pop). Como o próprio nome da estrutura sugere, a operação de empilhar insere o novo elemento sempre no topo e a operação desempilhar retira um elemento também sempre do topo.
Por essa característica uma estrutura do tipo pilha é conhecida pela propriedade LIFO, do inglês Last In, First Out, ou seja, o último elemento a ser empilhado é o primeiro a ser desempilhado.
Na videoaula abaixo apresento em mais detalhes como funciona uma estrutura do tipo pilha.
Estruturas
Para criar nossa Pilha faremos uso de duas estruturas: uma estrutura nó com dois elementos, um valor inteiro e um ponteiro para outro nó; e a estrutura pilha, que possui um elemento do tipo nó chamado topo, e um inteiro para o tamanho, como apresentado abaixo.
typedef struct no{
int valor;
struct no *proximo;
}No;
typedef struct{
No *topo;
int tam;
}Pilha;
Operação empilhar (pop)
Para a operação de empilhar, nosso procedimento receberá um ponteiro para nossa pilha e o elemento a ser inserido. Um novo nó é alocado dinamicamente e inserido no topo da lista, atualizando o ponteiro para o topo em seguida.
// operação push
void empilhar(Pilha *p, int x){
No *no = malloc(sizeof(No));
no->valor = x;
no->proximo = p->topo;
p->topo = no;
}
Operação desempilhar (push)
Nossa função para desempilhar retorna o ponteiro para o topo desempilhado, ou nulo caso a pilha esteja vazia. Antes de retornar o nó desempilhado, o topo é atualizado para o nó seguinte.
/* operação pop
retorna o topo da pilha ou NULL
*/
No* desempilhar(Pilha *p){
No *no = NULL;
if(p->topo){
no = p->topo;
p->topo = no->proximo;
}
return no;
}
Procedimento imprimir
Para imprimir nossa pilha, fazemos um procedimento recursivo bem simples que, recebendo um nó, imprime seu conteúdo e chama o procedimento novamente para o próximo nó. Esse processo se repete até que um nó nulo seja atingido.
Na sequência, inserimos a função principal com algumas opções no menu para que o usuário possa escolher entre as opções empilhar, desempilhar, imprimir e sair.
void imprimir(No *no){
if(no){
printf("%d\n", no->valor);
imprimir(no->proximo);
}
}
int main() {
int op, valor;
No *no;
Pilha p;
p.tam = 0;
p.topo = NULL;
do{
printf("\n0 - Sair\n1 - Empilhar\n2 - Desempilhar\n3 - Imprimir\n");
scanf("%d", &op);
switch(op){
case 0:
printf("Saindo...\n");
break;
case 1:
printf("Valor a ser empilhado: ");
scanf("%d", &valor);
empilhar(&p, valor);
break;
case 2:
no = desempilhar(&p);
if(no){
printf("\tDesemplilhado: %d\n", no->valor);
}
break;
case 3:
printf("\n-------- PILHA --------\n");
imprimir(p.topo);
printf("-------- PILHA --------\n");
break;
default:
printf("Opcao invalida!\n");
}
}while(op != 0);
return 0;
}
Código completo para a estrutura de dados Pilha
#include <stdio.h>
#include <stdlib.h>
typedef struct no{
int valor;
struct no *proximo;
}No;
typedef struct{
No *topo;
int tam;
}Pilha;
// operação push
void empilhar(Pilha *p, int x){
No *no = malloc(sizeof(No));
no->valor = x;
no->proximo = p->topo;
p->topo = no;
}
/* operação pop
retorna o topo da pilha ou NULL
*/
No* desempilhar(Pilha *p){
No *no = NULL;
if(p->topo){
no = p->topo;
p->topo = no->proximo;
}
return no;
}
void imprimir(No *no){
if(no){
printf("%d\n", no->valor);
imprimir(no->proximo);
}
}
int main() {
int op, valor;
No *no;
Pilha p;
p.tam = 0;
p.topo = NULL;
do{
printf("\n0 - Sair\n1 - Empilhar\n2 - Desempilhar\n3 - Imprimir\n");
scanf("%d", &op);
switch(op){
case 0:
printf("Saindo...\n");
break;
case 1:
printf("Valor a ser empilhado: ");
scanf("%d", &valor);
empilhar(&p, valor);
break;
case 2:
no = desempilhar(&p);
if(no){
printf("\tDesemplilhado: %d\n", no->valor);
}
break;
case 3:
printf("\n-------- PILHA --------\n");
imprimir(p.topo);
printf("-------- PILHA --------\n");
break;
default:
printf("Opcao invalida!\n");
}
}while(op != 0);
return 0;
}
Ficou com alguma dúvida? Gostaria de ver aqui um tutorial sobre algum assunto específico? Deixe seu comentário abaixo 🙂
Gostou do conteúdo? Compartilhe com os amigo. Um grande abraço e até o próximo.
