Enviar um café pro programador

Pode me ajudar a transformar cafeína em código?

Pilhas (Stack) em C - O Que É e Como Implementar (Tutorial de C Estrutura de Dados)

Neste Tutorial de C, vamos falar sobre uma das estrutura de dados mais importantes da computação, que são as pilhas (stack, em inglês).

Vamos entender o que são pilhas, para que servem, como implementar e programar uma, do zero.

Pilha em C - O Que É e Para Que Serve

Uma pilha é um tipo de estrutura de dado, que é uma maneira de se organizar e usar dados, informações.

A regra das pilhas é famoso LIFO - Last In, First Out, ou seja, o último a entrar é o primeiro a sair da estrutura.

O nome pilha não é por acaso. Vamos imaginar uma pilha de pratos.
Sempre que alguém termina de comer, coloca o prato na pilha, sempre acima.
Ou seja, o último prato a entrar na estrutura, esta sempre no topo.

E na hora de desfazer essa estrutura, essa pilha, que elementos vamos tirar?
Sempre o prato de cima, que foi o último elemento a entrar na pilha.
Note que o primeiro prato inserido vai ser o último a sair, pois ele está na base da pilha.

A ideia por trás das pilhas (stack), é de suma importância na estrutura de dados, sendo sua lógica usada em uma infinidade de aplicações. Seu sistema operacional, em níveis de linguagem C e Assembly, está a todo momento usando informações em pilhas para tratar processos e chamadas à funções.

Vamos aprender como fazer uma, na mão, do zero?

Como Programar Uma Pilha em C

Aqui, vamos explicando, passo a passo, como criar uma pilha em C, do zero, na mão.
Inicialmente vamos comentar tudo que é necessário, toda a lógica, e o código será exibido na próxima parte deste tutorial.

Struct e Cabeçalhos de Funções

O primeiro passo é a struct, vamos de Node (cada elemento de uma pilha é chamado de nó).
Ela vai ter apenas dois elementos, um número inteiro e um ponteiro para outra struct do tipo Node.

Esse ponteiro do próprio tipo é obrigatório, não existe estrutura dinâmica de dados sem esse detalhe especial. Na lógica do funcionamento da pilha, vamos entender para que ele serve.

Já o outro elemento (int num) é só para armazenarmos números nessa pilha, pois vamos pedir e mostrar esses números. Mas note que isso é uma struct, podemos colocar quantos elementos e do tamanho que quisermos, que a pilha vai funcionar do mesmo jeito.

Também colocamos todos os cabeçalhos das funções que iremos usar para programar a pilha em C, por questões de organização (o código das funções ficará abaixo).

Função main()

Na função main criamos a nossa pilha, que é uma struct Node, vamos chamar ela de "PILHA", e é a base. Quando o primeiro elemento for adicionado, ele vai ser adicionado no ponteiro "prox" da PILHA.
Este nó, na verdade, não faz parte da pilha, ele serve apenas para indicar onde ela começa (começa no ponteiro na qual ela aponta).

O resto da main é simplesmente um laço do while, que fica exibindo um menu com as opções para trabalharmos com a pilha, que termina se digitarmos 0.

Função menu() e opcao()

Essas são as funções responsáveis pela ação, a interação o usuário e a pilha.

A função menu() simplesmente exibe as opções possíveis e pede um inteiro ao usuário.
Este inteiro será usado e passado para a função opcao(), que junto com a pilha (ponteiro *PILHA) vai servir para chamar a função específica, de acordo com o que o usuário escolheu.

Na função opcao(), basicamente existe um switch que vai tratar a opção escolhida pela usuário, e chamar a função correta. Sem segredo.

Função inicia()

Esta função é responsável por inicializar a pilha.
Inicializar é simplesmente preparar a pilha para ser utilizada, simplesmente apontando seu ponteiro *prox para NULL.

Essa função é chamada automaticamente no início de nosso programa em C, e quando zeramos a pilha.

Função vazia()

Esta função simplesmente checa se a pilha está vazia ou não.
Basta olhar para onde aponta a base (*PILHA), se apontar para NULL é porque ela está vazia, senão, é porque existem nós nesta estrutura de dados dinâmica.

Função aloca()

Visando deixar nosso algoritmo bem feito, estruturado e organizado, é interessante separar cada ideia em uma função diferente, com um propósito bem evidente e único.

A função aloca() é um exemplo dessa organização.
Como o nome sugere, ele serve para alocar nós.
Sempre que formos adicionar um elemento na pilha, temos que alocar memória para ele.

Essa função aloca a memória necessária pro nó (struct Node), pede o número que o usuário quer armazenar) e retornar o endereço da memória alocada.

Função libera()

Tão importante quanto alocar memória para cada nó da pilha de nossa estrutura de dados, é liberar esse espaço de memória. A função libera faz isso, vai liberando o espaço alocado de cada nó de nossa pilha.

Usamos dois ponteiros para a struct do nó, o ponteiro que aponta para o elemento atual e o ponteiro que aponta para o próximo elemento.
Pegamos o ponteiro que aponta para o nó atual e usamos para desalocar aquele espaço de memória, em seguida o ponteiro que apontava para o atual aponta para o próximo, e isso segue até o fim da pilha, desalocando cada um dos nós da estrutura de dados.

Função exibe()

Essa é a função responsável por exibir todos os elementos da pilha.
Como em cada nó dessa estrutura de dados possui um inteiro que o usuário inseriu, essa função, no fim das contas, vai exibir os números da pilha.

Essa função declara um ponteiro que vai começar apontando para o primeiro elemento da pilha, exibe o número armazenado ali, pega o endereço do próximo nó, exibe o que está armazenado nele também, e assim se segue, até o fim da pilha (quando *prox aponta para NULL).

Função push()

Agora vamos a parte que mais interessa em se tratando de estrutura de dados, e especificamente, sobre pilhas em C: as funções push e pop.

Push em inglês é empurrar, vamos empurrar, colocar um elemento, um nó na pilha.
O primeiro passo é alocar espaço para esteve novo nó da pilha, o que é feito com ajuda da função aloca().
Como é uma pilha, seu último elemento (que é esteve novo), deve apontar para NULL, pois isso caracteriza o fim da pilha.

Adicionado o elemento, vamos procurar o último elemento da pilha.
Temos o ponteiro *PILHA que aponta para a base.
Se a pilha estiver vazia, ótimo! Fazemos o ponteiro *prox apontar para esteve novo nó, e tudo ok.

Se a pilha não for vazia, vamos achar o último elemento através de um ponteiro *tmp que vai apontar para o primeiro elemento da pilha (PILHA->prox aponta para o primeiro nó).

E como sabemos que o nó atual é o último?
Basta checar seu ponteiro *prox, se ele apontar para NULL, ele é último.
Se não apontar, é porque aponta para um novo nó, então fazemos nosso ponteiro *tmp apontar para este novo nó, sempre, até chegar no último.

Quando "tmp->prox" apontar para NULL, é porque *tmp está apontando para o último nó.
Agora, vamos fazer o próximo nó apontar para nosso novo nó: tmp->prox = novo
E pronto! Função push feita! Adicionamos um novo nó na pilha.

Função pop()

Agora vamos para a função pop, o outro pilar da estrutura de dados dinâmica que é a pilha.
Esta função vai tirar o último nó da pilha, e retirá-lo de lá.

Primeiro fazemos uma checagem se a pilha está vazia (PILHA->prox aponta pra NULL).
Se estiver, não há nada a ser feito, pois não há nó para ser retirado da pilha.

Do contrário, vamos utilizar dois ponteiros para struct Node, o "ultimo" e o "penultimo".
Basicamente, o que vamos fazer é que o "ultimo" aponte para o último elemento da pilha e o "penultimo" aponte para o último nó da pilha.

O motivo disso é simples: vamos retornar o último nó da pilha e vamos retirá-lo da lista (então ele vai se perder, por isso precisaremos sempre do penúltimo, pois este vai se tornar o novo último nó da lista).

O que vamos fazer é buscar o último nó (que é aquele que tem o ponteiro *prox apontando pra NULL).
E sempre que avançarmos na pilha com o ponteiro "ultimo", fazemos com que o "penultimo" também avance (ora, o penúltimo nó é aquele que tem o ponteiro *prox apontando para o ponteiro *ultimo).

Essa lógica é feita testando ultima->prox, quando não for NULL, o ponteiro "penultimo" passa a ser o "ultimo" e o "ultimo" vai ser o "ultimo->prox", que é o próximo nó da pilha.
Note que agora que demos um passo a frente na pilha, com os dois ponteiros.
E isso só para quando estivermos apontando para o último e penúltimo nó da pilha.

Quando estivermos nesse ponto, fazemos "penultimo->prox" apontar para NULL, pois vai caracterizar que o penúltimo nó será, agora, o último nó (pois aponta pra NULL), ou seja: retiramos o último nó da pilha!

E o que fazemos com o último nó?
Vamos retornar ele! Se estamos tirando ele da pilha, é porque queremos o que tem nele, seja lá pra que for. Então retornamos ele pra função que o chamou (a função opcao()), ela exibe o valor desse último elemento da pilha e então o descarta (liberando a memória dele).

Código Completo De Uma Pilha em C

#include <stdio.h>
#include <stdlib.h>

struct Node{
 int num;
 struct Node *prox;
};
typedef struct Node node;

int tam;

int menu(void);
void inicia(node *PILHA);
void opcao(node *PILHA, int op);
void exibe(node *PILHA);
void libera(node *PILHA);
void push(node *PILHA);
node *pop(node *PILHA);


int main(void)
{
 node *PILHA = (node *) malloc(sizeof(node));
 if(!PILHA){
  printf("Sem memoria disponivel!\n");
  exit(1);
 }else{
 inicia(PILHA);
 int opt;

 do{
  opt=menu();
  opcao(PILHA,opt);
 }while(opt);

 free(PILHA);
 return 0;
 }
}

void inicia(node *PILHA)
{
 PILHA->prox = NULL;
 tam=0;
}

int menu(void)
{
 int opt;

 printf("Escolha a opcao\n");
 printf("0. Sair\n");
 printf("1. Zerar PILHA\n");
 printf("2. Exibir PILHA\n");
 printf("3. PUSH\n");
 printf("4. POP\n");
 printf("Opcao: "); scanf("%d", &opt);

 return opt;
}

void opcao(node *PILHA, int op)
{
 node *tmp;
 switch(op){
  case 0:
   libera(PILHA);
   break;

  case 1:
   libera(PILHA);
   inicia(PILHA);
   break;

  case 2:
   exibe(PILHA);
   break;

  case 3:
   push(PILHA);
   break;

  case 4:
   tmp= pop(PILHA);
   if(tmp != NULL)
   printf("Retirado: %3d\n\n", tmp->num);
   break;

  default:
   printf("Comando invalido\n\n");
 }
}

int vazia(node *PILHA)
{
 if(PILHA->prox == NULL)
  return 1;
 else
  return 0;
}

node *aloca()
{
 node *novo=(node *) malloc(sizeof(node));
 if(!novo){
  printf("Sem memoria disponivel!\n");
  exit(1);
 }else{
  printf("Novo elemento: "); scanf("%d", &novo->num);
  return novo;
 }
}


void exibe(node *PILHA)
{
 if(vazia(PILHA)){
  printf("PILHA vazia!\n\n");
  return ;
 }

 node *tmp;
 tmp = PILHA->prox;
 printf("PILHA:");
 while( tmp != NULL){
  printf("%5d", tmp->num);
  tmp = tmp->prox;
 }
 printf("\n        ");
 int count;
 for(count=0 ; count < tam ; count++)
  printf("  ^  ");
 printf("\nOrdem:");
 for(count=0 ; count < tam ; count++)
  printf("%5d", count+1);


 printf("\n\n");
}

void libera(node *PILHA)
{
 if(!vazia(PILHA)){
  node *proxNode,
     *atual;

  atual = PILHA->prox;
  while(atual != NULL){
   proxNode = atual->prox;
   free(atual);
   atual = proxNode;
  }
 }
}

void push(node *PILHA)
{
 node *novo=aloca();
 novo->prox = NULL;

 if(vazia(PILHA))
  PILHA->prox=novo;
 else{
  node *tmp = PILHA->prox;

  while(tmp->prox != NULL)
   tmp = tmp->prox;

  tmp->prox = novo;
 }
 tam++;
}


node *pop(node *PILHA)
{
 if(PILHA->prox == NULL){
  printf("PILHA ja vazia\n\n");
  return NULL;
 }else{
  node *ultimo = PILHA->prox,
              *penultimo = PILHA;

  while(ultimo->prox != NULL){
   penultimo = ultimo;
   ultimo = ultimo->prox;
  }

  penultimo->prox = NULL;
  tam--;
  return ultimo;
 }
}


Considerações sobre a Estrutura de Dados Dinâmica Pilha

A ideia por trás da estrutura de dados do tipo pilha é simples: o último elemento a entrar, é sempre o primeiro a sair.

Existem zilhões de maneiras de se programar uma pilha.
Fizemos apenas uma, que criamos e achamos que é didaticamente interessante de se aprender

Por exemplo, fizemos uma que possui apenas um elemento fixo, o ponteiro *PILHA, que aponta para a base da pilha. Tente fazer um com o ponteiro *top, que aponta para o topo (final da pilha).

Se tiver estudado nosso Tutorial Sobre Listas Encadeadas em C vai entender bem melhor tudo que foi explicado neste tutorial, e vai notar que uma pilha é uma lista onde os só podemos inserir elementos no fim da lista e só podemos retirar elementos do fim também.

Ou seja, uma pilha é uma lista também, mas uma lista mais simples, onde só usamos o final dela.
Mais importante que ter todos esses códigos e implementações em C em mente, é ter essas ideias, essa lógica da coisa, de como funciona.

14 comentários:

Prof. VALENTE disse...

Excelente material !! PARABÉNS mesmo ...
Usarei em minhas aulas, sem dúvida alguma!!
OBS.: logo no começo do material houve uma incorreção:
"A regra das pilhas é famoso LIFO - Last In, First Out, ou seja, o primeira a entrar é o primeiro a sair da estrutura."

Mais uma vez PARABÉNS pela iniciativa pela qualidade do material !!

Apostila C Progressivo disse...

Opa, verdade Professor, confundimos uma palavrinha.

A equipe agradece os elogios e estamos muito felizes de ter um professor usando nosso material.

Não deixe de enviar erratas, críticas e sugestões, para criarmos um material cada vez mais completo!

Anônimo disse...

Amigos,
acredito que o professor foi quem se equivocou.
Existem vários tipos de estruturas e as que nos interessa agora são as PILHAS e FILAS.
FILAS: normalmente conhecidas em inglês como FIFO ( First In First Out ), ou em português, menos usados, PEPS ( Primeiro a Entrar é o Primeiro a Sair ).
PILHAS: também em inglês conhecidas como LIFO ( Last In First Out ), ou em português UEPS ( Ultimo a Entrar é o Primeiro a Sair ).
Donde se conclui que vcs estão corretos e o professor foi quem se equivocou.

Parabéns pelo material !!!

Prof. VALENTE disse...

Não, eu NÃO estava errado, caro ANONIMO !! O texto estava errado mesmo, como eu transcrevi na minha mensagem, e foi devidamente corrigido ... e muito rapidamente, mostrando o quanto este site é bem estruturado e administrado !!

Anônimo disse...

olá , essa pilha já desempilha ordenado?, por que você não tenta usar, um ponteiro apontando pra cabeça ?, acho que iria melhorar o código

Anônimo disse...

Ola amigo em q situacao EU usaria uma pilha em um programs? Ela funciona igual a "pilha" da memoria? N consigo tirar ver diferenca nas duas e isso n me dxa entender o assunto

Nelson Neves Filho disse...

Na opção do switch
case 4:
tmp= pop(PILHA);
if(tmp != NULL)
printf("Retirado: %3d\n\n", tmp->num);

Não deveria ter um "free(tmp);" para liberar a memória alocada?

Unknown disse...

Só uma consideração: as funções que trabalham com estruturas básicas devem buscar ter o melhor desempenho possível. Nas funções que trabalham com pilha, a complexidade de praticamente todas as funções básicas deve ser O(1), o que não ocorre no push e pop. Poderia utilizar uma abordagem de inserção no início que deixaria ambas as funções com essa característica.

Unknown disse...

Muito obrigado pela ajuda

Eli disse...

Boa noite. Gostaria de saber como fica a main pois estou tentando com letras mas noa tá dando certo.
int main (void)
{
Nome *l;
char v;
cria();
push (l, 'e');
push (l, 'l');
push (l, 'i');
push (l, 'a');
push (l, 'n');
push (l, 'e');
imprime(l);
v = pop(l);
imprime(l);
v = pop(l);
imprime(l);
libera(l);
return 0;
}

Anônimo disse...

Parabéns pela humildade... Site muito bom mesmo. Estou aprendendo muito.

Unknown disse...

Marcyrius Joanes, você ajustou a estrutura principal usada (Node)?
Ali tem um membro chamado num, do tipo inteiro. Tem que substituir por char.

Mat disse...

Olha o site de vocês é excelente, didático pra caramba. Estou muito contente de verdade!! Obrigado.

Isabel Siqueira disse...

Poderia exemplificar uma situação que eu optaria pela pilha? Acho que a grande dificuldade pra quem está aprendendo é entender em que eu aplicaria ou para que eu aplicaria certas estruturas.