[INF1007] ResumoPilha

Prévia do material em texto

Programação II 
Monitor: André Vicente Pessanha 
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://lh5.ggpht.com/weguest/SA689aip5DI/AAAAAAAAAEQ/aBnXhEPr8II/pilha_thumb%5B
3%5D.jpg?imgmax=800 
 
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! 
 
OBS2:​ Se caso a imagem não abrir, é só digitar no google imagens “pilha linguagem C 
push pop” 
 
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! :) 
 
 
------------------------------------------------------- // ------------------------------------------------------------