Cap7-Pilhas

Prévia do material em texto

Capítulo 7
Pilhas
7.1 Fundamentos
Pilha é uma lista em que todas as operações de inserção, remoção e acesso são feitas num mesmo extremo, denominado topo.
Os itens são removidos da pilha na ordem inversa aquela em que foram inseridos, o último a entrar é o primeiro a sair, por isso, pilhas são também conhecidas como
Listas LIFO (Last-In/First-Out)
A principal propriedade de uma pilha é sua capacidade de inverter a ordem de uma sequência.
Essa propriedade é útil em várias aplicações em computação.
Um Exemplo:
Num navegador web, conforme as páginas vão sendo acessadas, seus endereços vão sendo inseridos numa pilha.
Em qualquer instante durante a navegação, o endereço da última página acessada está no topo da pilha.
Quando o botão voltar é clicado, o navegador remove um endereço da pilha e recarrega a página do endereço que ficou no topo da pilha.
Ou seja, à medida que o botão voltar é clicado, as páginas acessadas são reapresentadas na ordem inversa aquela em que foram visitadas.
Outro exemplo:
Controle de fluxo de execução de um programa de computador.
Durante a execução de um programa, sempre que uma função é chamada, antes de passar o controle a ela, um endereço de retorno correspondente é inserido numa pilha.
Quando a função termina sua execução, o endereço no topo da pilha é removido e a execução do programa continua a partir dele.
Assim a última função que passa o controle é a primeira a recebê-lo de volta.
Veja exemplo abaixo: Empilha -> chama Desempilha/retorna 
A função main() chama a() e o SO A função a() chama b() e o SO A função b() imprime “b”, encera sua excução 
 empilha o endereço de a na pilha empilha o enderço de b na pilha e o SO desempilha o endereço de b da pilha
Desenhe e escreva no seu caderno, como a pilha vai ficar 
E o que será impresso na tela. 
7.2 Operações em Pilhas
A figura da próxima transparência mostra os efeitos dessas operações numa pilha P. 
Efeitos e resultados das operações em pilhas.
A pilha é representada por uma lista com topo na extrema direita.
7.3 Implementação de pilhas
Em C uma pilha pode ser definida como:
//typedef int Itemp; //tipo dos itens da pilha
typedef char Itemp; //tipo dos itens da pilha
//typedef float Itemp; //tipo dos itens da pilha
typedef struct pilha {
 int max;			//capacidade da pilha
 int topo;			//posição do topo
 Itemp *item;			//itens da pilha
} *Pilha;
Pilha é um ponteiro que aponta uma estrutura(struct pilha) com três campos:
max que indica a capacidade máxima da pilha P -> max
topo que indica a posição do topo da pilha		 P-> topo
item é um ponteiro que aponta um vetor dinâmico que guarda os itens da pilha P-> item
Ponteiro para uma estrutura de pilha, que armazena os itens a,b,c
Função de criação da pilha P 
 Pilha pilha(m): cria e devolve uma pilha vazia P, com capacidade máxima m;
Pilha pilha(int m) {
 Pilha P = malloc(sizeof(struct pilha));
 P->max = m;
 P->topo = -1;
 P->item = malloc(m*sizeof(Itemp));
 return P;
}
Quando chamada quais os passos executados pela função pilha() ????
Porque o topo é iniciado com -1.
 
O comando Pilha P = pilha(5); cria a pilha mostrada abaixo
Vamos ver adiante, como inserir elementos na pilha. Posso colocar 5 elementos na pilha da figura acima, e ela ficará cheia, como mostrado abaixo
Quando a pilha estiver cheia, em topo teremos max-1.
Quando a pilha estiver vazia em topo teremos -1
Função que verifica se a pilha está vazia
int vaziap (Pilha P): devolve 1(verdade) se P está vazia, senão devolve 0(falso)
int vaziap (Pilha P){
	if(P->topo == -1) return 1;
	else return 0;
}
Exemplo de operação			Pilha		Resultado
P = pilha(3);				 [ ] -	
Exemplo de operação			Pilha P			Resultado
int a;
a=vaziap(P);				 [ ]			 1	
Quanto vale a ??? 
 
Função que verifica se a pilha está cheia
int cheiap (Pilha P): devolve 1(verdade) se P está cheia, senão devolve 0(falso)
int cheiap (Pilha P){
	if(P->topo == P->max-1) return 1;
	else return 0;
}
Exemplo de operação			Pilha P			Resultado
int a;
a=cheiap(P);				 [ ]			 0	
Quanto vale a ??? 
Função para inserir um elemento na pilha
void empilha (Itemp x, Pilha P): insere o item x no topo da pilha P
void empilha(Itemp x, Pilha P) {
 if( cheiap(P) ) { puts("pilha cheia!"); abort(); }
 P->topo++;
 P->item[P->topo] = x;
}
Exemplo de operação			 Pilha P		Resultado
empilha(1,P);				 [1]			 - 
empilha(2,P);				 [1 2]		 - 
empilha(3,P);				 [1 2 3]		 - 	
int a,b;
a=vaziap(P); b=cheiap(P); Quanto valem a e b ????																																 	
 
Função para remover um item da pilha
Itemp desempilha(Pilha P): remove e devolve o item existente no topo da pilha
Itemp desempilha(Pilha P) {
 if( vaziap(P) ) { puts("pilha vazia!"); abort(); }
 Itemp x = P->item[P->topo];
 P->topo--;
 return x; 
}
Exemplo de operação 			Pilha			resultado
empilha(3,P) [1,2,3] -
desempilha(P) 			[1 2]			 3	
desempilha(P) 			[1 ]			 2	
Função para acessar o item no topo da pilha sem removê-lo
Itemp topo(Pilha P): acessa e devolve o item existente no topo da pilha 
Itemp topo(Pilha P) {
 if( vaziap(P) ) { puts("pilha vazia!"); abort(); }
 return P->item[P->topo];
}
Função para destruição da pilha
 destroip(&P): destrói a pilha
void destroip(Pilha *Q) {
 free((*Q)->item);
 free(*Q);
 *Q = NULL;
}
Essa é a única função de pilha cujo parâmetro P é passado por referência, isto é Q é um ponteiro de ponteiro.
O que acontece então ????
Quando a chamada destroip(&P) é feita:
 O endereço do ponteiro P é copiado para o ponteiro Q, usado como parâmetro da função.
Então a notação *Q permite acessar o ponteiro P e, consequentemente, (*Q)-> item permite acessar o campo item da estrutura apontada por P. 
Assim, quando a chamada free((*Q)-> item é feita, o vetor item apontado por P é destruído.
A chamada free(*Q) faz com que a estrutura de pilha apontada por P também é destruída.
Finalmente *Q=NULL, faz o ponteiro P ter o valor NULL
7. 4 O arquivo pilha.h
Daqui por diante assumimos que as definições de tipos e funções para pilhas estão no arquivo
pilha.h
Para usar o tipo Pilha basta incluir a diretiva #include "pilha.h”
Assim, durante sua compilação, todas as definições no arquivo pilha.h serão usadas automaticamente.
Exercícios
Criar um programa que converte um número decimal n em binário
O algoritmo é: 
Efetuar sucessivas divisões de n por 2 até que o quociente seja 0
O número binário são os restos das divisões efetuadas na ordem inversa em que foram obtidas.
Exemplo 13 decimal = 1101 binário
Solução: criar uma pilha de números inteiros. Empilhar os restos das divisões sucessivas até que o quociente seja 0. Depois desempilhar e imprimir cada item até que a pilha fique vazia.
//binario.c - conversao em binario
#include <stdio.h>
#include "pilha.h"
main()
{
	int n;
	Pilha P= pilha(32);
	printf("Entre com o numero Decimal\n");
	scanf("%d",&n);
		//printf("%d\n",n);
	do{
		empilha(n%2,P);
		//printf("%d\n",n%2);
		n=n/2;
		//printf("%d\n",n);
	}while(n!=0);
	printf("\nValor em Binario=");
	while(!vaziap(P))printf("%d",desempilha(P));
	destroip(&P);
}//cap7.2.c
2. Inversão de cadeia de caracteres, ou seja exibir a string inversa aquela digitada pelo usuário. Por exemplo, se o usuário digitar roma, o programa deverá exibir amor. 
 Em C uma cadeia de caracteres termina sempre com o caractere \0. Então basta criar uma pilha cujos elementos são caracteres, depois empilhar os elementos começando do primeiro até chegar em \0 e finalmente desempilhar, imprimindo cada caractere, até a pilha ficar vazia. 
//inverte.c - inversão de string
#include <stdio.h>
#include "pilha.h" //pilha de caractere 
main()
{
	int i;
	char c[8];
	Pilha P= pilha(80);
	printf("Entre com a string\n");
	gets(c);
	for(i=0; c[i]!='\0';i++)empilha(c[i],P);printf("\nString Invertida\n");
	while(!vaziap(P))printf("%c",desempilha(P));
	destroip(&P);
}//cap7.3.c
3. Qual a saída exibida pelo programa a seguir ? Por que ?
#include <stdio.h>
#include "pilha.h"
main()
{
	Pilha P= pilha(3);
		empilha(1,P);
		empilha(2,P);
	printf("%d\n",desempilha(P));
	printf("%d\n",desempilha(P));
	printf("%d\n",desempilha(P));
	destroip(&P);
}
//cap.7.4.c
//Modifique o programa para produzir as sequencias 3241 e 1423
4. Qual a saída exibida pelo programa a seguir ? Por que ?
#include <stdio.h>
#include "pilha.h" //pilha de float
main()
{
	Pilha P= pilha(100);
		empilha(8,P);
			while(topo(P)>0){
 // while(topo(P)>1){
			empilha(topo(P)/2,P);
	}
		while(!vaziap(P))printf("%f\n",desempilha(P));
 // while(!vaziap(P))printf("%d\n",desempilha(P)); //pilha de inteiro
 	destroip(&P);
}
//cap7.5.c
6.//inverter a ordem das letras nas palavras de uma frase, se for digitada "apenas um amor" aparecerá “sanepa mu roma"
#include <stdio.h>
#include "pilha.h" //pilha de caractere 
main(){
	int i=0,j=0,m,n=0;
	char c[50];
	Pilha P= pilha(80);
	printf("Entre com a string\n");
	gets(c);
	do {
		empilha(c[i],P);
		if(c[i]=='\0') break;
		if(c[i]==' ') {
		m=0;
		n=n+j; 	
		while((n+m)!=i+1){	
		printf("%c",desempilha(P));
		j++;
		m++;
 	}}
	 i=i+1; 
	}while(1);
 while(!vaziap(P))printf("%c",desempilha(P));
destroip(&P);}//cap7.6.c
6. Crie um programa que usa duas pilhas A e B para ordenar uma sequencia de n números reais dados pelo usuário.