Pilha (Stack)

Uma Pilha (Stack) é um tipo de lista, que funciona como se fosse uma pilha de livros (não, infelizmente não é igual pilhas da Duracell) em que você não consegue retirar livros no meio da pilha, afinal, você não quer que todos os livros caiam no chão e você tenha que recolher todos, não é mesmo?

Na aula, nós utilizamos C para implementar a Pilha, mas, se você é como eu, que já sabe Java e só está lendo isto porque o seu professor(a) quer usar C, então você veio ao lugar certo! Aliás, em Java já existe a implementação deste algoritmo, o Stack.

A pilha é assim, no nosso caso, vamos criar uma que suporta até cinco valores.

topo = -1

A nossa pilha também tem uma variável que controla a posição do topo da pilha, nós iremos chamar ela de topo.

Ao criar a pilha, o topo será -1, afinal, ainda não existe nenhum valor na nossa pilha!

Para inserir algo na pilha, iremos usar o push, que insere no topo da lista, ou seja.

push(&pilha, 5);

Isto irá fazer a nossa pilha ficar assim...

5 topo = 0

topo = 0

Vamos inserir mais outro valor utilizando push...

push(&pilha, 15);

15 topo = 1
5

topo = 1

Wow! Mágica!

Mas... agora eu quero acessar o valor que está no topo da lista! Para isto, iremos usar acessarTopo

int i = acessarTopo(pilha);

E agora, i é igual a 15!

Para retirar um valor da nossa pilha, iremos usar pop

pop(&pilha);

5 topo = 0

Wow, mágica!

E assim que uma pilha funciona! Na nossa implementação, iremos implementar deste jeito:

  • O valor máximo que nossa pilha irá suportar é 10, #define MaxPilha 10
  • Nosso struct será este
typedef struct {
    int topo; // Valor no topo da pilha
    int tabela[MaxPilha]; // Valores que estão na pilha
} Pilha;
  • Operação - Construtores criarPilha() e criarPilhaVazia(Pilha *): Criar pilha vazia.
  • Operação - Acesso acessarTopo(Pilha): Acessar o valor que está no topo da pilha.
  • Operação - Acesso verificarPilhaVazia(Pilha): Verificar Pilha Vazia.
  • Operação - Acesso verificarPilhaCheia(Pilha): Verificar Pilha Cheia.
  • Operação - Manipulação push(Pilha *, int): Inserir um valor no topo da pilha push.
  • Operação - Manipulação pop(Pilha *): Retirar o valor que está no topo da pilha pop.
  • Operação - Manipulação esvaziarPilha(Pilha *): Esvaziar pilha.
  • Caso o usuário tente acessar o topo da lista quando não possui nenhum valor dentro dela, o valor fantasma será retornado (zero).
  • O valor inicial do topo (que iremos chamar de sentinela) será -1.

Antes de começar, vamos declarar os valores usando #define

#define MaxPilha 10
#define Sentinela -1
#define Fantasma 0

As nossas interfaces serão...

// Construtores: Ambos criam uma pilha vazia.
Pilha criarPilha();
void criarPilhaVazia(Pilha *);

// Funções de acesso a pilha
int acessarTopo(Pilha);
bool verificarPilhaVazia(Pilha);
bool verificarPilhaCheia(Pilha);

// Manipulação
// Push: Coloca um número na pilha
// Pop: Retira o valor que está no topo da pilha, mas não devolve o que foi retirado
// Esvaziar Pilha: Esvazia a Pilha
void push(Pilha *, int);
void pop(Pilha *);
void esvaziarPilha(Pilha *);

Agora é a hora da implementação da nossa interface!

Construtores

Existem dois construtores que devemos implementar.

Pilha criarPilha() {
	Pilha pilha;
	pilha.topo = Sentinela;
	return pilha;
}

Isto irá criar uma pilha vazia Pilha pilha; (Nota: Diferente da Java, não é necessário usar Pilha pilha = new Pilha(); ou algo similar, afinal, struct é uma estrutura de dados!).

Após isto, iremos alterar o valor do topo da pilha para o nosso sentinela, caso isto não seja feito, o valor do topo será... um valor completamente aleatório! (Eu duvido que você queria que o topo seja 1983136165313, não é mesmo?)

E depois iremos retornar a nossa pilha marota.

void criarPilhaVazia(Pilha* pilha) {
	pilha->topo = Sentinela;
}

Já essa função é para aquelas pessoas teimosas que "eu criei a minha PRÓPRIA PILHA no meu PRÓPRIO CÓDIGO".

void criarPilhaVazia(Pilha* pilha) {
	pilha->topo = Sentinela;
}

A pessoa passa a pilha dela por referência criarPilhaVazia(&pilha) e nós apenas alteramos o valor do topo para o nosso sentinela, só para a pessoa ficar feliz.

Você deve estar vendo "oxe, mas o que é esse -> aí?"... então, quando um valor é passado por referência &, é necessário usar -> e não .! Lembre-se, se tem * na função, mete setinha nele!

Acesso

Vamos implementar primeiro as funções de verificar se a lista está cheia/vazia.

bool verificarPilhaVazia(Pilha pilha) {
	return pilha.topo == Sentinela;
}

bool verificarPilhaCheia(Pilha pilha) {
	int valorMaximo = MaxPilha - 1;
	return pilha.topo == valorMaximo;
}

Simples, apenas comparamos o valor do topo com o valor do sentinela ou com o valor máximo.

Por exemplo, se criarmos uma pilha AGORA, nesse exato MOMENTO, o topo será -1, certo? E se a gente usar verificarPilhaVazia(pilhaCriada)?

Vai executar "hmmmmm, pilha.topo == Sentinela... ou seja, -1 == -1, eita nois, é true!"

E a mesma coisa com o verificarPilhaCheia! Nós verificamos com o valor de MaxPilha - 1 porque...

40028922 topo = 4
1337
20
10
5

É, então, se a pilha está cheia, o topo sempre será o valor máximo - 1, já que o nosso topo começa no -1!

E agora, vamos implementar o acesso ao topo da pilha!

int acessarTopo(Pilha pilha) {
	int valor = Fantasma;
	if (!verificarPilhaVazia(pilha)) {
		valor = pilha.tabela[pilha.topo]
	}
	return valor;	
}

Primeiro iremos marcar o valor padrão como o Fantasma e aí, caso a pilha NÃO esteja vazia, iremos pegar o valor da nossa pilha (afinal, não queremos pegar valores inválidos!)

Vamos supor que usamos acessarTopo(pilha) sendo que pilha é { topo = 4; tabela = [ 1, 2, 3, 4, 10 ]; }.

Primeiro o valor será marcado como 0, que é o nosso valor fantasma.

Depois iremos verificar se a pilha está vazia... bem, o topo não é igual ao sentinela, não é mesmo? Afinal, a pilha não está vazia, então é verdadeiro!

O valor será pego da nossa matriz tabela, na posição 4, ou seja.

tabela[0] 1
tabela[1] 2
tabela[2] 3
tabela[3] 4
tabela[4] 10

Irá retornar 10!

Manipulação

Hora de manipular a nossa pilha!

Começando pelo nosso querido push

void push(Pilha* pilha, int valor) {	
	if (!verificarPilhaCheia(pilha)) {
		topo = pilha->topo;
		topo++;
		
		pilha->tabela[topo] = valor;
		pilha->topo = topo;
	}
}

Apenas iremos dar push caso a lista não esteja cheia! Por isso a chamada para a função verificarPilhaCheia(pilha).

Após isto, iremos pegar o valor do topo, aumentar ele, salvar o nosso valor desejado na array da pilha e alterar o valor do topo!

E agora o pop, que tem um código bem similar ao push.

void pop(Pilha* pilha) {
	if (!verificarPilhaVazia(pilha)) {
		topo = pilha->topo;
		topo--;
		
		pilha->topo = topo;
	}
}

Você deve ter notado que nós não removemos o valor anterior que estava na pilha... é assim porque não estava na implementação original e porque, em C, não vai mudar nada você alterar o valor (exceto se você tivesse usando malloc), não é igual em Java (na maioria das implementações de stack) em que, se você retirasse, ele iria ser retirado da memória (para depois o GC limpar).

E agora a função mais difícil de todas... a função para esvaziar a lista!

void esvaziarPilha(Pilha* pilha) {
	pilha->topo = Sentinela;
}

Código final

#include "Booleano.h"

#define MaxPilha 10
#define Sentinela -1
#define Fantasma 0

typedef struct {
	int topo;
	int tabela[MaxPilha];
} Pilha;

// Construtores: Ambos criam uma pilha vazia.
Pilha criarPilha();
void criarPilhaVazia(Pilha *);

// Funções de acesso a pilha
int acessarTopo(Pilha);
bool verificarPilhaVazia(Pilha);
bool verificarPilhaCheia(Pilha);

// Manipulação
// Push: Coloca um número na pilha
// Pop: Retira o valor que está no topo da pilha, mas não devolve o que foi retirado
// Esvaziar Pilha: Esvazia a Pilha
void push(Pilha *, int);
void pop(Pilha *);
void esvaziarPilha(Pilha *);

// Implementação
Pilha criarPilha() {
	Pilha pilha;
	pilha.topo = Sentinela;
	return pilha;
}

void criarPilhaVazia(Pilha* pilha) {
	pilha->topo = Sentinela;
}

int acessarTopo(Pilha pilha) {
	int valor = Fantasma;
	if (!verificarPilhaVazia(pilha)) {
		valor = pilha.tabela[pilha.topo]
	}
	return valor;	
}

bool verificarPilhaVazia(Pilha pilha) {
	return pilha.topo == Sentinela;
}

bool verificarPilhaCheia(Pilha pilha) {
	int valorMaximo = MaxPilha - 1;
	return pilha.topo == valorMaximo;
}

void push(Pilha* pilha, int valor) {	
	if (!verificarPilhaCheia(pilha)) {
		topo = pilha->topo;
		topo++;
		
		pilha->tabela[topo] = valor;
		pilha->topo = topo;
	}
}

void pop(Pilha* pilha) {
	if (!verificarPilhaVazia(pilha)) {
		topo = pilha->topo;
		topo--;
		
		pilha->topo = topo;
	}
}

void esvaziarPilha(Pilha* pilha) {
	pilha->topo = Sentinela;
}

E aqui uma versão para "professores chatos presos em 1990", acredite em mim, tem gente que acha que é um absurdo reusar código!

#include "Booleano.h"

#define MaxPilha 10
#define Sentinela -1
#define Fantasma 0

typedef struct {
	int topo;
	int tabela[MaxPilha];
} Pilha;

// Construtores: Ambos criam uma pilha vazia.
Pilha criarPilha();
void criarPilhaVazia(Pilha *);

// Funções de acesso a pilha
int acessarTopo(Pilha);
bool verificarPilhaVazia(Pilha);
bool verificarPilhaCheia(Pilha);

// Manipulação
// Push: Coloca um número na pilha
// Pop: Retira o valor que está no topo da pilha, mas não devolve o que foi retirado
// Esvaziar Pilha: Esvazia a Pilha
void push(Pilha *, int);
void pop(Pilha *);
void esvaziarPilha(Pilha *);

// Implementação
Pilha criarPilha() {
	Pilha pilha;
	pilha.topo = Sentinela;
	return pilha;
}

void criarPilhaVazia(Pilha* pilha) {
	pilha->topo = Sentinela;
}

int acessarTopo(Pilha pilha) {
	int valor;
	if (pilha.topo == Sentinela) {
		valor = Fantasma;
	} else {
		valor = pilha.tabela[pilha.topo];
	}
	return valor;	
}

bool verificarPilhaVazia(Pilha pilha) {
	bool ok;
	ok = pilha.topo == Sentinela;
	return ok;
}

bool verificarPilhaCheia(Pilha pilha) {
	bool ok;
	int valorMaximo = MaxPilha - 1;
	ok = pilha.topo == valorMaximo;
	
	return ok;
}

void push(Pilha* pilha, int valor) {
	int topo;
	int valorMaximo = MaxPilha - 1;
	
	if (pilha->topo != valorMaximo) {
		topo = pilha->topo;
		topo++;
		
		pilha->tabela[topo] = valor;
		pilha->topo = topo;
	}
}

void pop(Pilha* pilha) {
	int topo;
	
	if (pilha->topo != Sentinela) {
		topo = pilha->topo;
		topo--;
		
		pilha->topo = topo;
	}
}

void esvaziarPilha(Pilha* pilha) {
	pilha->topo = Sentinela;
}