Resumo_Pilha

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Resumo Pilha:
***********************************************************************************
OBS: Essa matéria só cai na P3!
***********************************************************************************
- Definição:
Pilha é um pedaço reservado da memória usado pra armazenar as variáveis locais das funções de um programa, mas >>Somente<< quando a função está sendo executada e assim que a função encerra, a memória é devolvida.
Na verdade, não existe Pilha em C, ela vem de uma linguagem chamada "Assembly", mas justamente por não existir que é usado um TAD pra tentar representar o funcionamento de uma Pilha em C! Então podemos considerar Pilha como um tipo especial de TAD!
E além disso, Pilha é muito usado para inverter dados. (Strings, Vetor de ponteiros para struct, etc)
OBS: Ainda não viu TAD? Viu TAD na aula, mas não entendeu direito? Viu TAD na aula, mas não sabe nem do que se trata? 
Sem problemas! Recomendo ler urgentemente o meu bloco "Resumo_TAD"! :D 
Antes de tudo, sempre que o assunto for pilha, tente sempre imaginar dessa forma: 
Imagem: http://marcelino.com.sapo.pt/CMan/pics/pic_11_1.jpg
OBS: Talvez você lembre dos slides de Prog 1, sempre mostravam essa mesma foto de pilha pra facilitar o entendimento de outras matérias! Lembrando que quando qualquer função está em execução, suas variáveis locais vão sendo armazenadas na Pilha e só são retiradas quando a função encerra!
E só a partir dessa imagem, já vemos duas operações principais de qualquer pilha:
Pilha Push (Insere um novo elemento no topo da pilha) 
Pilha Pop (Retira e retorna o elemento que está no topo da pilha)
OBS: Então já podemos concluir que em >> TODA << pilha, inserimos e retiramos >>SEMPRE<< do topo!
---------------------------------------//-----------------------------------------
- Tipos de Pilha:
Existem duas formas de implementar uma Pilha: Como um vetor ou como uma lista.
OBS: Nunca se esqueça que Pilha segue as mesmas regras de um TAD comum! Ou seja, também possui um módulo de interface, implementação e um para o usuário!
Mas dessa vez não precisamos nos preocupar em criar cada módulo. O enunciado da prova >>SEMPRE<< diz assim: "Utilize o seguinte TAD Pilha"
typedef struct pilha Pilha;
Pilha * pilha_cria();
void pilha_push(Pilha *p, char c);
char pilha_pop(Pilha *p);
int pilha_vazia(Pilha *p);
void pilha_libera(Pilha *p);
 
OBS: Um conjunto de funções e um typedef...Sim! Esse é o nosso módulo de Interface! :)
É exatamente a mesma interface para Pilha implementada como vetor ou lista!
A grande diferença entre uma pilha implementada como vetor ou lista é na forma como suas funções são implementadas, assim como a definição da struct!
OBS: A informação armazenada na Pilha pode variar também! Nesse exemplo, vamos usar uma Pilha que armazena caracteres.
-----------------------------------//---------------------------------------------
- Pilha Implementada como Vetor: 
#define MAX 50
struct pilha{
 char v[MAX];
 int n;
};
OBS: MAX é a quantidade limite de "casinhas" da pilha e 'n' representa a quantidade de "casinhas" ocupadas, assim como sempre fizemos em vetor! :)
Pilha * pilha_cria(){
 Pilha *nova = (Pilha *) malloc (sizeof(Pilha));
 
 if(!nova) return NULL;
 
 nova->n = 0;
 return nova;
}
OBS: Se a variável 'n' representa a quantidade de "casinhas" ocupadas no vetor, por isso inicializamos com zero durante a criação da pilha! 
----------------------------------------------------------------------------------
void pilha_push(Pilha *p, char c){
 if(p->n == MAX){
 puts("Pilha Estourou!");
 pilha_libera (p);
 exit(1);
 }
 p->v[p->n] = c;
 p->n++;
}
OBS: Antes de tudo precisamos verificar se a pilha está lotada! Se não estiver, temos que atribuir o caracter na posição atual do vetor.
Pra fazer isso, primeiro usamos p->v pra acessar o vetor, mas em qual posição? p->n! Pois o 'n' também representa a posição atual do vetor! E por fim, incrementamos o 'n', pois acabamos de inserir um novo elemento na Pilha. 
----------------------------------------------------------------------------------
 
int pilha_vazia(Pilha *p){
 return p == NULL;
}
OBS: (p == NULL) é uma expressão booleana, como se fosse uma condição if. (Se for verdade retorna 1, senão zero)
Também funciona dessa forma: >> return !p; <<
----------------------------------------------------------------------------------
 
char pilha_pop(Pilha *p){
 if(pilha_vazia(p)){
 puts("Pilha vazia!");
 exit(1);
 }
 p->n--;
 return p->v[p->n];
}
OBS: Primeiro passo é verificar se a Pilha está vazia! Pois tentar retirar um elemento de uma pilha vazia é um erro fatal! 
Na verdade, não removemos literalmente o elemento do vetor, ele continua lá, só fazemos um "ajuste" na posição atual do vetor através da variável 'n'! (Isso porque o elemento que queremos remover está sempre no final do vetor! Pois só podemos remover do topo da pilha!)
EX: Imagina que o vetor está assim e chamamos a função pilha_pop : 3, 5, 6, 10
A variável 'n' representa o total de posições ocupadas no vetor, então nesse exemplo 'n' é igual a 4 (De 0 até 3). Então pra remover o 10, fazemos p->n--; para decrementar o 'n' que agora vale 3. Aparentemente o 10 continua lá, mas observa com calma, agora o total de posições ocupadas é 3 (De 0 até 2) e 3 é exatamente a posição onde está o valor 10 que precisamos retornar!
OBS: Lembrando que retornar um valor não o remove do vetor! Só na próxima chamada da função pilha_push que o valor 10 será substituído por um novo valor!
----------------------------------------------------------------------------------
void pilha_libera(Pilha *p){
 free(p);
}
OBS: A principal desvantagem da Pilha implementada como vetor é justamente pelo fato de existir um > Tamanho Limite < que é necessário especificar antes de tudo! Então a implementação por lista acaba sendo bem melhor e por isso é mais cobrado em prova do que a por vetor. Mas eu recomendo no mínimo entender o desenvolvimento dessas funções através de vetor pra não ter risco! :)
 
 
---------------------------------------//-----------------------------------------
- Pilha implementada como Lista:
OBS: Praticamente todas essas funções seguem o mesmo esquema das funções que manipulam lista encadeada! (Inserir, liberar, criar, etc) 
A grande diferença é que a lista está dentro da pilha, ou seja, pra acessar qualquer elemento da lista, precisamos primeiro acessar a variável da Pilha! 
Então eu recomendo mais do que nunca que você "Pause" esse resumo e leia urgentemente o meu bloco "Resumo_ListaEncadeada"! :D
typedef struct no{
 char info;
 struct no *prox;
}No;
struct pilha{
 No *lst;
};
OBS: Agora temos duas structs: uma que representa a pilha e outra que representa o Nó da lista. E percebe que >>SÓ<< podemos colocar o typedef na struct da lista! Mas então porque não colocamos ela no Módulo de Interface junto com o outro? 
Porque ela não pertence ao TAD Pilha! Só podemos colocar no Módulo de Interface as funções e typedef comuns a qualquer tipo de Pilha! E vetor e lista são formas de implementação diferentes! (Por isso o #define MAX em vetor também fica nesse módulo de implementação)
----------------------------------------------------------------------------------
Pilha * pilha_cria (){
 Pilha *novo = (Pilha *) malloc(sizeof(Pilha));
 if(!novo) return NULL; 
 novo->lst = NULL; 
 return novo;
}
OBS: O primeiro passo é alocar dinamicamente uma nova pilha. No *lst é o ponteiro que >>SEMPRE<< "aponta" para o começo da lista e como acabamos de criar, a lista está vazia, por isso precisamos inicializar No * lst com NULL! (Exatamente como é feito na criação de qualquer lista) 
---------------------------------------------------------------------------------
void pilha_push (Pilha *p,
char c) {
	No * novo = (No *) malloc (sizeof(No));
	if(!novo){
		puts("Falha na insercao!");
		return ;
	}
	novo->info = c;
	novo->prox = p->lst;
	p->lst = novo;
}
OBS: Essa função é idêntica a "Insere" de lista encadeada. Precisamos alocar dinamicamente um novo Nó e no final fazemos um "ajuste" pra colocar o novo elemento no começo da lista, mesmo esquema! 
A única diferença é que pra acessar o começo da lista usamos: p->lst (Lembrando que quando só era Lista Encadeada, podíamos usar 'lst' direto!)
---------------------------------------------------------------------------------
int pilha_vazia(Pilha *p) {
 return (p->lst == NULL);
}
OBS: O parênteses é opcional!
----------------------------------------------------------------------------------
char pilha_pop(Pilha *p) {
	char c;
	No *e;
	if(pilha_vazia(p)){
		puts("Pilha Vazia!");
		exit(1);
	}
	c = p->lst->info;
	e = p->lst->prox;
	free(p->lst);
	p->lst = e;
	return c;
}
OBS: Sempre devemos verificar se a pilha está vazia antes de tudo! Diferente da Pilha com vetor, aqui nós realmente fazemos uma remoção do elemento! E como precisamos retornar a informação no final, é necessário armazenar a informação e o próximo elemento em variáveis auxiliares antes de remover! 
E pra fechar, dizemos que o novo começo da lista é o elemento que vem depois do que acabou de ser removido!
---------------------------------------------------------------------------------- 
void pilha_libera(Pilha *p) {
 No *e;
 while(p->lst){
 e = p->lst->prox;
 free(p->lst);
 p->lst = e;
 }
 free(p);
}
Bem parecido com a função Libera de lista! Armazena o próximo elemento, elimina o atual e o próximo passa a ser o atual.
OBS: Isso tudo foi explicado com detalhes no "Resumo_ListaEncadeada", é exatamente o mesmo esquema! :D
OBS2: Uma questão da P3 de 2014.1 pedia pra implementar a função Push e Pop, sendo que um dos itens dessa questão pedia pra fazer isso como vetor e o outro como lista! 
-------------------------------------//------------------------------------------
- Inverter dados na Pilha: 
A principal forma de cobrarem Pilha nas provas é com o objetivo de inverter algo.(Listas, vetor de ponteiros para struct, uma outra pilha, etc) 
OBS: Se cair esse tipo de questão, o próprio enunciado já te diz as funções do TAD Pilha e você não precisa implementar nada! Somente chamar as funções pra inverter o que está sendo pedido da forma correta. E a forma de implementação da pilha nesses tipos de questão é >>SEMPRE<< como uma lista!
Exemplo: O enunciado pede pra criar uma função chamada > retiraMaiusculas < que recebe uma pilha de caracteres como parâmetro e retira todas as letras maiúsculas, mas sem alterar a ordenação original dos elemento da pilha!
void retiraMaiusculas(Pilha *p){
	char c;
	Pilha *aux = pilha_cria();
	if(!aux) return;
	while(!pilha_vazia(p)){
		c = pilha_pop(p);
		if(islower(c)){
			pilha_push(aux,c);
		}
	}
	while(!pilha_vazia(aux)){
		c = pilha_pop(aux);
		pilha_push(p, c);
	}
	pilha_libera(aux);
}
Precisamos usar uma pilha auxiliar pra inverter a pilha original!
A lógica é sempre a mesma, enquanto a pilha original >>NÃO<< estiver vazia, retira cada elemento com a função pilha_pop (Lembra que ela sempre retorna o elemento que remove?) 
Primeiro verificamos se o caracter é minúsculo com a função islower >>ANTES<< de inserir na pilha auxiliar, pois só queremos manter as letras minúsculas!
**********************************************************************************
Outras formas de verificar: 
- if( !isupper(c) ) 
OBS: Essa função verifica se o caracter é maiúsculo. Colocamos o > ! < na frente, pois não queremos caracter maiúsculo! 
- if(c >= 'a' && c <= 'z') 
OBS: Essa é a forma tradicional de verificar se um caracter é minúsculo. (Prog 1) 
OBS2: A função islower e isupper pertencem ao protótipo <ctype.h> 
É bom conhecer essas funções, mas não se preocupe em decorar nada, qualquer função extra é dada pelo próprio enunciado! :) 
***********************************************************************************
No fim do primeiro while, vamos ter uma pilha auxiliar preenchida >>Somente<< com os caracteres minúsculos, problema resolvido!? :O
NÃO! Pois quando passamos os caracteres pra pilha auxiliar a ordem foi invertida!
Mas se já conseguimos separar os caracteres minúsculos na pilha auxiliar, se devolvermos tudo para a pilha original, a ordem será invertida novamente! (De volta para a ordenação original) 
pilhaLibera(aux);
OBS: >>NUNCA<< se esqueça de liberar todas as pilhas auxiliares!
A grande maioria das questões de Pilha são exatamente nesse estilo! Tente sempre visualizar o que acontece a cada passagem pra Pilha Auxiliar. 
Será que inverter uma vez já resolve o problema? Na dúvida faça um desenho da pilha com os dados de exemplo pra facilitar ou use o próprio desenho que normalmente vem nos enunciados! :)
------------------------------------//---------------------------------------------