Baixe o app para aproveitar ainda mais
Prévia do material em texto
ESTRUTURAS DE DADOS Aula 06 Professor: Vinicius Moll. Florianópolis, 19 de Fevereiro, 2018. ESTRUTURA DE DADOS Aula 6 – Pilha ESTRUTURA DE DADOS PILHA – Aula6 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 1 • Histórico de páginas visitadas num navegador. 2 • Sequencia de desfazer em vários softwares, o famoso atalho Ctrl Z. 3 • Implementação de recursividade (a torre de Hanói que vimos na disciplina de Algoritmos). 4 • A cadeia de chamadas de funções num programa. 5 • Avaliação de expressões aritméticas. 6 • Conversão de Decimal para Binário, etc. 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]== ‘)’? 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 ) 5 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 ) 5 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
Compartilhar