Aula_06

Prévia do material em texto

ESTRUTURA DE DADOS
Aula 6 – Pilha
Atenção aos Temas Principais dessa Aula
ESTRUTURA DE DADOS
PILHA – Aula6
Conteúdo Programático desta aula
Apresentar o conceito de Pilha; 
Apresentar aplicações da Pilha;
Apresentar o critério LIFO e suas limitações
Implementar as funções empilhar, desempilhar, exibir topo e outras;
ESTRUTURA DE DADOS
PILHA – Aula6
Direto ao Assunto
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
VOCÊ ERROU! NÃO ERA PILHA?
ESTRUTURA DE DADOS
PILHA – Aula6
ERA! E AGORA?
ESTRUTURA DE DADOS
PILHA – Aula6
USA AQUELAS TECLAS.
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
“A pilha é uma das estruturas de dados mais úteis em computação.
… Uma pilha é um tipo especial de lista linear em que todas as operações de inserção e remoção são realizadas numa mesma extremidade, denominada topo”(PEREIRA, S.L. 2004, p 17).
Conceito de Pilha
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
Considerações sobre a PILHA
ESTRUTURA DE DADOS
PILHA – Aula6
 Inserção ou Remoção de um elemento sempre acontece na mesma extremidade.
Considerações sobre a PILHA
ESTRUTURA DE DADOS
PILHA – Aula6
Inserção na Pilha
ESTRUTURA DE DADOS
PILHA – Aula6
Inserção na Pilha
Remoção da Pilha
ESTRUTURA DE DADOS
PILHA – Aula6
 Inserção ou Remoção de um elemento sempre acontece na mesma extremidade.
Não existe movimentação na pilha quando inserimos, ou removemos um elemento dela.
Considerações sobre a PILHA
ESTRUTURA DE DADOS
PILHA – Aula6
 Inserção ou Remoção de um elemento sempre acontece na mesma extremidade.
Podemos usar matrizes homogêneas ou heterogêneas, alocação sequencial, e uma variável para controlar o topo.
Não existe movimentação na pilha quando inserimos, ou removemos um elemento dela.
Considerações sobre a PILHA
ESTRUTURA DE DADOS
PILHA – Aula6
Um dos fatores que limita o crescimento da pilha é a quantidade de memória alocada quando usamos matrizes. 
Considerações sobre a PILHA
ESTRUTURA DE DADOS
PILHA – Aula6
Um dos fatores que limita o crescimento da pilha é a quantidade de memória alocada quando usamos matrizes. 
Quando formos empilhar um elemento, é preciso verificar se a pilha não está cheia. Isso evita overflow.
Considerações sobre a PILHA
ESTRUTURA DE DADOS
PILHA – Aula6
Um dos fatores que limita o crescimento da pilha é a quantidade de memória alocada quando usamos matrizes. 
Quando formos empilhar um elemento, é preciso verificar se a pilha não está cheia. Isso evita overflow.
Quando formos desempilhar um elemento, é preciso verificar se a pilha não está vazia. Isso evita underflow.
Considerações sobre a PILHA
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra?
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra?
1a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra?
2a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra?
3a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra?
4a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra?
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra?
1a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra?
2a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra?
3a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Quem não se lembra?
4a vez
ESTRUTURA DE DADOS
PILHA – Aula6
Avaliação de parênteses – um clássico
ESTRUTURA DE DADOS
PILHA – Aula6
#include <iostream>
#include <cstring>
using namespace std;
int expressaoCorreta( char s[]);
int main()
{
 char p1[]={"((()))"}; 
 char p2[]={"(()))"}; 
 if(expressaoCorreta(p1)==1)
 cout<<"\n"<<p1<<" Esta Correta\n";
 else
 cout<<"\n"<<p1<<" Nao esta Correta\n"; 
 if(expressaoCorreta(p2)==1)
 cout<<"\n"<<p2<<" Esta Correta\n";
 else
 cout<<"\n"<<p2<<" Nao esta Correta\n"; 
 system("pause");
} 
Código
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 (
 (
 (
 )
 )
 ) 
 \0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 (
0 0 (
 (
 )
 )
 )
 \0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 (
0 0 (
 (
 )
 )
 )
 \0 
s[0]== ‘)’?N
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 (
 1 (
 )
 )
 )
 \0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 (
1 1 (
 )
 )
 )
 \0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 (
1 1 (
 )
 )
 )
 \0 
s[1]== ‘)’?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 (
1 1 (
 )
 )
 )
 \0 
s[1]== ‘)’?N
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 (
 2 )
 )
 )
 \0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 (
2 2 )
 )
 )
 \0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 (
2 2 )
 )
 )
 \0 
s[2]== ‘)’?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 (
2 2 )
 )
 )
 \0 
s[2]== ‘)’?N
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
 3 )
 )
 \0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
 )
 \0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
 )
 \0 
s[3]== ‘)’?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
 )
 \0 
s[3]== ‘)’?S
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
 )
 \0 
t!=0 && pilha[t-1]==‘(‘?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
 )
 \0 
t!=0 && pilha[t-1]==‘(‘?S
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
 2 )
 \0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
 \0 
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
 \0 
s[4]== ‘)’?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )3 3 )
4 2 )
 \0 
s[4]== ‘)’?S
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
 \0 
t!=0 && pilha[t-1]==‘(‘?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
 \0 
t!=0 && pilha[t-1]==‘(‘?S
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
 1 \0
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
5 1 \0
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
5 1 \0
s[5]== ‘)’?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
5 1 \0
s[5]== ‘)’?S
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
5 1 \0
t!=0 && pilha[t-1]==‘(‘?
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
5 1 \0
t!=0 && pilha[t-1]==‘(‘?S
Função
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
Função
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
1 \0
 0 
0
1
2
3
4
5
6
ESTRUTURA DE DADOS
PILHA – Aula6
i t s pilha
 0 ( (
0 0 ( (
1 1 ( (
2 2 )
3 3 )
4 2 )
1 \0
6 0
0
1
2
3
4
5
6
retorna 1
Função
ESTRUTURA DE DADOS
PILHA – Aula6
Conversão decimal para binário – outro clássico
ESTRUTURA DE DADOS
PILHA – Aula6
#include <iostream>
#include <cstdlib>
#define TAM 40
using namespace std;
void empilha(int p[], int &t, int v);
void desempilha(int p[], int &t);
int main()
{
 int topo=-1, pilha[TAM],num, resto;
 cout<<"\nNumero em decimal:";
 cin>>num;num=abs(num);
 while(num > 0)
 {
 resto=num %2;
 empilha(pilha, topo, resto);
 num/=2;
 } 
 desempilha(pilha,topo);
 cout<<"\n\n"; system("pause"); }
Código
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t resto num pilha
-1 ? 14
 
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t resto num pilha
-1 ? 14
-1 0 14
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t resto num pilha
-1 ? 14 0
-1 0 14
 0 0 14
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t resto num pilha
-1 ? 14 0
-1 0 14
 0 0 14
 0 0 7
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t resto num pilha
-1 ? 14 0
-1 0 14
 0 0 14
 0 0 7
 0 1 7
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t resto num pilha
-1 ? 14 0
-1 0 14 1
 0 0 14
 0 0 7
 0 1 7
 1 1 7
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t resto num pilha
-1 ? 14 0
-1 0 14 1
 0 0 14
 0 0 7
 0 1 7
 1 1 7
 1 1 3
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t resto num pilha
-1 ? 14 0
-1 0 14 1
 0 0 14
 0 0 7
 0 1 7
 1 1 7
 1 1 3
 1 1 3
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t resto num pilha
-1 ? 14 0
-1 0 14 1
 0 0 14 1
 0 0 7
 0 1 7
 1 1 7
 1 1 3
 1 1 3
 2 1 3
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t resto num pilha
2 1 1 0
 1
 1
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t resto num pilha
2 1 1 0
2 1 1 1
 1
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t resto num pilha
2 1 1 0
2 1 1 1
3 1 1 1
 1
0
1
2
3
4
.
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t resto num pilha
2 1 1 0
2 1 1 1
3 1 1 1
3 1 0 1
0
1
2
3
4
.
FIM - empilha
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t pilha
3 0
 1
 1
 1
0
1
2
3
4
5
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t pilha
3 0
 1
 1
 1
0
1
2
3
4
5
Saída
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t pilha
3 0
2 1
 1
 1
0
1
2
3
4
5
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t pilha
3 0
2 1
2 1
 1
0
1
2
3
4
5
Saída
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t pilha
3 0
2 1
2 1
1 1
0
1
2
3
4
5
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t pilha
3 0
2 1
2 1
1 1
1
0
1
2
3
4
5
Saída
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t pilha
3 0
2 1
2 1
1 1
1
0
0
1
2
3
4
5
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t pilha
3 0
2 1
2 1
1 1
1
0
0
0
1
2
3
4
5
Saída
ESTRUTURA DE DADOS
PILHA – Aula6
Função
t pilha
3 0
2 1
2 1
1 1
1
0
0
-1
0
1
2
3
4
5
Saída
FIM - desempilha
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
1) Inicializa () ou Init()
2) Empilhar() ou Push()
3) Desempilhar() ou Pop()
4) acessoTopo() ou Top()
5) verificaPilhaCheia() ou isFull()
6) verificaPilhaVazia() ou isEmpty()
ESTRUTURA DE DADOS
PILHA – Aula6
0 PROBLEMA
Uma carreta que transporta cinco carros.
Cada carro, será preso a uma tranca que tem duas chaves. Uma que foi enviada ao proprietário e a outra com o motorista.
Cada carro tem um código de saída, identificação(nome do proprietário, tipo de carro e endereço) e nota fiscal.
A solução será apresentada com struct , funções matrizes(alocação contígua).
ESTRUTURA DE DADOS
PILHA – Aula6
A struct
ESTRUTURA DE DADOS
PILHA – Aula6
Inicialização
ESTRUTURA DE DADOS
PILHA – Aula6
Protótipos
Inicialização
ESTRUTURA DE DADOS
PILHA – Aula6
#include <iostream>
#include <cstdlib>
#define TAM 5
using namespace std;
struct atende
{ 
 char identificacao[TAM][60]; 
 long long notaFiscal[TAM];
 int codigoSaida[TAM], topo; 
};
void empilha(atende &pilha);
void desempilha(atende &pilha);
void mostraTopo(atende &pilha);
void lista(atende &pilha);
Código
1
ESTRUTURA DE DADOS
PILHA – Aula6
int main()
{
 int op; atende carros; 
 carros.topo=-1; 
do
 { system("cls");
 cout<<"\nPILHA( LIFO- Last In - First Out )\n\n";
 cout<<"\n1- Inserir carro";
 cout<<"\n2- Remover carro";
 cout<<"\n3- Mostrar o primeiro carro a sair";
 cout<<"\n4- listar - QUESTAO DIDATICA. Remova depois que testar"; 
 cout<<"\n5- Sai"; 
 cout<<"\nOpcao: ";
 cin>>op;
 system("cls");Código
2
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
 switch(op)
 { 
 case 1: cin.get(); empilha(carros); break;
 
 case 2: desempilha(carros); break;
 
 case 3: mostraTopo(carros); break;
 case 4: lista(carros); break; 
 
 case 5: cout<<"\nAplicacao da PILHA\ n"; break;
 
 default: cout<<"\nOPCAO INVALIDA\n"; 
 } 
 cout<<"\n\n";system("pause"); 
 }while(op!=5);
}
Código
3
ESTRUTURA DE DADOS
PILHA – Aula6
void empilha(atende &pilha)
{
 char id[60]; long long nf; int codS;
 if(pilha.topo == TAM-1)
 cout<<"\nATENCAO. Carreta Cheia\n";
 else
 { cout<<"\nProprietatio/ Tipo de carro/ Destino:";
 cin.getline(id, 60);
 cout<<"\nNota Fiscal: "; cin>>nf;
 cout<<"\nCodigo de saida: "; cin>>codS; 
 pilha.topo++; //atualiza o topo
 // pilha recebe valor
 strcpy(pilha.identificacao[pilha.topo], id);
 pilha.notaFiscal[pilha.topo]=nf;
 pilha.codigoSaida[pilha.topo]=codS;
 }
}
Código
4
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
void desempilha(atende &pilha)
{
 if(pilha.topo == -1)
 cout<<"\nATENCAO. Carreta Vazia \n";
 else
 { 
 cout<<"\nCodigo do carro entregue: “; //*
 cout<< pilha.codigoSaida[pilha.topo]; 
 cout<<"\nNota fiscal do carro entregue: “; //*
 cout<< pilha.notaFiscal[pilha.topo];
 cout<<"\nIdentificacao do carro entregue: “; //*
 cout<< pilha.identificacao[pilha.topo]; 
 pilha.topo--; //atualiza o topo 
 }
}
 //* MELHORAR O ENTENDIMENTO. 
Código
5
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
void mostraTopo(atende &pilha)
{ 
 if(pilha.topo == -1)
 cout<<"\nATENCAO. Carreta Vazia \n";
 else
 {
 cout<<"\nCodigo do carro: “; //*
 cout<<pilha.codigoSaida[pilha.topo];
 cout<<"\nNota fiscal do carro: “; //*
 cout<<pilha.notaFiscal[pilha.topo];
 cout<<"\nIdentificacao do carro: “; //*
 cout<<pilha.identificacao[pilha.topo];
 } 
} //* MELHORAR O ENTENDIMENTO. 
Código
6
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
void lista(atende &pilha)
{
 if(pilha.topo == -1)
 cout<<"\nATENCAO. Carreta Vazia \n";
 else
 { 
 cout<<"\nOrdem de Saida\n";
 for(int x=pilha.topo; x>=0; x--)
 { cout<<"\n\n"<<x+1<<"o carro";
 cout<<"\nCodigo do carro: "<<pilha.codigoSaida[x];
 cout<<"\nNota fiscal do carro: "<<pilha.notaFiscal[x];
 cout<<"\nIdentificacao do carro: “; //*
 cout<<pilha.identificacao[x]; 
 }
 }
} //* MELHORAR O ENTENDIMENTO. 
Código
7
ESTRUTURA DE DADOS
PILHA – Aula6
ESTRUTURA DE DADOS
PILHA – Aula6
Resumindo
ESTRUTURA DE DADOS
PILHA – Aula6