Cap-tulo-2-Pilhas-com-Aloca-o-Sequencial-e-Est-tica_2014_Estruturas-de-Dados-Com-Jogos.pdf

17

Capítulo 2Pilhas com Alocação

Sequencial e Estática

Seus objetivos neste capítulo• EntenderoqueéeparaqueserveumaestruturadotipoPilha.

• EntenderosignificadodeAlocaçãoSequencialeAlocaçãoEstáticadeMemória,

nocontextodoarmazenamentotemporáriodeconjuntosdeelementos.

• DesenvolverhabilidadeparaimplementarumaestruturadotipoPilha,comoumTipo

AbstratodeDados(TAD),comAlocaçãoSequencialeEstáticadeMemória.

• DesenvolverhabilidadeparamanipularPilhasatravésdosOperadoresdefinidos

paraoTADPilha.

• Iniciarodesenvolvimentodoseuprimeirojogo.

2.1 O que é uma Pilha?Nocontextodestelivro,otermoPilhadizrespeitoaumapilhadepratos,pilhadelivrosoupilhadecartas.Ouseja,osentidoédeempilharumacoisasobreaoutra.

18

Capítulo 2 Pilhas com Alocação Sequencial e Estática

Emumapilhadepratos,sevocêtentartirarumpratodomeiodapilha,apilhapoderádesmoronar.Tambémserábemcomplicadovocêinserirumpratonomeiodapilha.Omaisnaturaléretirarpratosdotopodapilhaeinserirpratossemprenotopodapilha.

Emessência,éassimquefuncionaumaPilha:novoselementosentramsemprenotopo;sequisermosretirarumelemento,retiramossempreoelementodotopo.

UmaPilhaéumconjuntoordenadodeelementos.Aordemdeentradadeterminaaposiçãodoselementosnoconjunto.SetemostrêselementosemumaPilha(A,BeC)eseelesentraramnaPilhanasequênciaA,depoisBeentãoC,sabemosqueoelementoCestaránotopodaPilha(Figura2.3a).

NasituaçãodaFigura2.3a,oúnicoelementoquepodemosretiraréexatamenteoelementoqueestánotopodaPilha.Ouseja,oelementoC.RetirandooelementoC,asituaçãodaPilhaficasendoadaFigura2.3b.Se,emseguida,quisermosinseriroelementoD,esseelementoDpassaráaserotopodaPilha—Figura2.3c.E,finalmente,sequisermosinseriroelementoE,essenovoelementopassaráaseroelementodotopo—Figura2.3d.SeaordemdeinserçãodoselementosnaPilhativessesidooutra,aPilharesultantetambémseriaoutra.

OmesmoraciocíniovaleparaumaPilhadeCartas,porexemplo.ConsiderecomosituaçãoinicialumaPilhacomtrêscartas:8decopas,Jdepause,notopodaPilha,Adeespadas,comomostraaFigura2.4a.AocontráriodoquefizemosnapilhadecubosdaFigura2.3,agoraotopoestárepresentadonapartedebaixodaPilhadeCartas.Essa

Figura 2.1 Ilustração do conceito de Pilha — sentido de empilhar.

Figura 2.2 Definição de Pilha.

Estruturas de Dados com Jogos

19

representaçãomostraovaloreonaipedetodasascartasdaPilha,comoseestivéssemosempilhandoumacartasobreaoutracomumbaralhodepapel.ÉarepresentaçãousualdasPilhasdeCartasemjogosdotipoFreeCell.

SequisermosinserirnoconjuntoacartaQdecopas,essanovacartaprecisaráserinseridanotopodaPilha,resultandonasituaçãodaFigura2.4b.Se,emseguida,quisermosretirarumacartadaPilha,aúnicacartaquepodemosretiraréacartadotopodaPilha—opróprioQdecopas,queacaboudeserinserido.APilhaentãovoltaráàsituaçãodaFigura2.4a,tendoapenastrêselementos,comoAdeespadasnovamentenotopo.

Figura 2.4 Inserindo e retirando cartas em uma Pilha.

Figura 2.3 Retirando e inserindo elementos em uma Pilha.

20


2.2 Operações de uma PilhaVamoschamaraoperaçãoqueinsereelementosemumaPilhadeEmpilha,eaoperaçãoqueretiraelementosdeumaPilha,deDesempilha.AessasduasOperações,vamosacres-centaroutrastrês:operaçãoparacriarumaPilha,operaçãoparatestarseaPilhaestávaziaeoperaçãoparatestarseaPilhaestácheia.NaFigura2.5temosaespecificaçãodasoperaçõesEmpilha,Desempilha,Cria,VaziaeCheia,bemcomoumadescriçãodeseusparâmetrosefuncionamento.

Exercício 2.1 Transfere elementos de uma Pilha para outraDesenvolvaumalgoritmoparatransferirtodososelementosdeumaPilhaP1paraumaPilhaP2.ConsiderequeasPilhasP1eP2jáexistem,ouseja,nãoprecisamsercriadas.Paraelaboraressealgoritmo,useosoperadoresdefinidosnaFigura2.5.ConsiderequeasPilhasP1eP2possuemelementosdotipointeiro.VocêteráqueelaboraressealgoritmosemsabercomooTipoAbstratodeDadosPilhaéefetivamenteimplementado.Vocêencontraráumasoluçãoparaesteexercícionasequênciadotexto.Mas,antesdeprosseguiraleitura,tenteproporumasolução.ÉassimquedesenvolvemoshabilidadeparamanipularPilhas(eoutrasestruturas)pelosseusOperadores.

AlógicadasoluçãodoExercício2.1éaseguinte:enquantoaPilhaP1nãoestivervazia,retiramoselementosdeP1atravésdaoperaçãoDesempilha.Cadavalordesempi-lhadodeP1deveserempilhadonaPilhaP2atravésdaoperaçãoEmpilha.RepetimosessasequênciadecomandosatéqueaPilhaP1setornevazia.VejaoalgoritmodaFigura2.6.

Figura 2.5 Operações de uma Pilha.


21

NotequeaindanãotemosamenorideiadecomoessasoperaçõesdoTADPilha(Empilha,Desempilha,Vazia,Cheia,Cria)sãoefetivamenteimplementadas.ConsideramosasPilhascomocaixas-pretasemanipulamososvaloresarmazenadosapenasatravésdosOperado-res(ou“botõesdatelevisão”).Éassimquemanipulamosestruturasdearmazenamento,comoPilhas,demodoabstrato.ÉassimqueutilizamososTiposAbstratosdeDados.

ProponhaumasoluçãoparaosExercícios2.2,2.3e2.4semprecomamesmaestratégia:manipulandoosvaloresarmazenadosexclusivamenteatravésdosOperadoresdoTADPilhadescritosnaFigura2.5.

Exercício 2.2 Mais elementos?DesenvolvaumalgoritmoparatestarseumaPilhaP1temmaiselementosdoqueumaPilhaP2.ConsiderequeasPilhasP1eP2jáexistemesãopassadascomoparâmetro.ConsideretambémqueasPilhasP1eP2possuemelementosdotipoInteiro.VocêpodecriarPilhasauxiliares,senecessário.VocêdevepreservarosdadosdeP1eP2.Ouseja,aofinaldaexecuçãodessaoperação,P1eP2precisamconterexatamenteosmesmoselementosquecontinhamnoiníciodaoperação,enamesmasequência.Paraproporasolução,utilizeosOperadoresdaFigura2.5.

Exercício 2.3 Algum elemento igual a X?DesenvolvaumalgoritmoparaverificarseumaPilhaPpossuialgumelementoigualaumvalorX.PeXsãopassadoscomoparâmetros.ConsiderequeaPilhaPpossuielementosdotipoInteiro.Paraproporasolução,utilizeosOperadoresdaFigura2.5.VocêpodecriarPilhasauxiliares,senecessário.

Exercício 2.4 As Pilhas são iguais?DesenvolvaumalgoritmoparatestarseduasPilhasP1eP2sãoiguais.DuasPilhassãoiguaissepossuemosmesmoselementos,exatamentenamesmaordem.Paraproporsuasolução,vocêpodeutilizarPilhasauxiliares,senecessário.ConsiderequeasPilhasP1eP2jáexistemesãopassadascomoparâmetro.Considerequeas

Figura 2.6 Algoritmo para transferir elementos de uma Pilha para outra.

22


PilhasP1eP2possuemelementosdotipoInteiro.Paraproporasolução,utilizeosOperadoresdaFigura2.5.

Nofinaldestecapítulovocêencontrarárespostasousugestõesparaalgunsdosexercícios.Mas,paradesenvolverashabilidadespretendidas,proponhasuasprópriassoluçõesantesdeconsultarasrespostassugeridas.

2.3 Alocação de memória para conjuntos de elementosAlocarmemória,emessência,significareservarumaporçãodamemóriadocomputadorparaumusoespecífico.Alocarmemóriaparaumconjuntodeelementos,comoumaPilha,envolvereservarespaçodememóriaparaarmazenarcadaumdoselementosdoconjunto.

Alocação SequencialNaAlocaçãoSequencialdeMemóriaparaumconjuntodeelementos(Knuth,1972,p.240;Pereira,1996,p.12),todososelementosdoconjuntoserãoarmazenadosjuntos,emposiçõesadjacentesdememória.Ouseja,oselementosficam“emsequência”,umaoladodooutronamemóriadocomputador.

AFigura2.8mostraumaPilhacomquatroelementos:oelementoAnotopodaPilhae,emseguida,oselementosD,CeB.NaAlocaçãoSequencialdeMemória,aordemdessesquatroelementosérefletidanasposiçõesdememóriaemqueoselementossãoarmazenados.

Alocação EstáticaNaAlocaçãoEstáticadeMemóriaparaumconjuntodeelementos,estabelecemosotamanhomáximodoconjuntopreviamente,aoelaboraroprograma,ereservamosmemóriaparatodososseuselementos.Esseespaçodememóriapermaneceráreser-vadodurantetodaaexecuçãodoprograma,mesmoquenãoestejasendototalmenteutilizado,istoé,mesmoqueemdeterminadomomentoaquantidadedeelementosnoconjuntosejamenorqueoqueseutamanhomáximo.Comootamanhodoespaçodememóriaédefinidopreviamente,elenãopoderácresceroudiminuiraolongodaexecuçãodoprograma.

Figura 2.7 Definição de Alocação Sequencial de Memória para um conjunto de elementos.


23

2.5 Implementando uma Pilha com Alocação Sequencial e EstáticaParaimplementarumaPilhacombinandoosconceitosdeAlocaçãoSequencialeAlocaçãoEstáticadeMemória,aoelaboraroprogramaprecisamosdefinirotamanhodoespaçodememóriaaserreservadoepossibilitarqueoselementosdaPilhapossamserarmazenadosemposiçõesadjacentesdememória.Podemosfazerissoatravésdeumaestruturadotipovetor.

NaFigura2.10temosoesquemadeumaPilhaimplementadaatravésdeumvetordeno-minadoElementos,quearmazenaoselementosdaPilha,edeumavariáveldenominadaTopo,queindicaotopodaPilha.

PodemosdefinirotipoPilhacomoumRegistro(umaStructnalinguagemC)contendodoiscampos:ElementoseTopo.TopodotipoInteiroeElementosdotipovetorde1atéTamanho(constantequeindicaotamanhodaPilha)ou,ainda,dezeroatéTamanho−1,conformeopadrãodalinguagemC.OselementosdaPilhapodemserdotipoChar,dotipoInteiro,dotipoCarta-do-Baralhooudeoutrotipoqualquer,conformenecessário.

ParaimplementarumTipoAbstratodeDados(TAD)precisamosdeumaestruturadearmazenamentoedeOperadoresquepossamseraplicadossobreosDadosarmazenados.VamosimplementaroTADPilhacomaestruturadearmazenamentodefinidanaFigura2.10ecomosOperadoresdefinidosnaFigura2.5:Empilha,Desempilha,Cria,VaziaeCheia.

Figura 2.9 Definição de Alocação Estática de Memória para um conjunto de elementos.

Figura 2.8 Alocação Sequencial — armazenamento em posições de memória adjacentes.

24


Exercício 2.5 Operação EmpilhaConformeespecificadonaFigura2.5,aoperaçãoEmpilharecebecomoparâmetrosaPilhaeovalordoelementoquequeremosempilhar.OelementosónãoseráinseridoseaPilhajáestivercheia.Vocêencontraráumapossívelsoluçãoparaesteexercícionasequênciadotexto.Mastenteproporumasoluçãoantesdeprosseguiraleitura.

AFigura2.11ilustraofuncionamentodaoperaçãoEmpilha.ApartirdasituaçãodaFigu-ra2.11a,umelementodevalor’E’éinserido,resultandonasituaçãodaFigura2.11b.

Figura 2.10 Esquema da implementação de uma Pilha com Alocação Sequencial e Estática de Memória.

Figura 2.11 Operação Empilha.


25

NotequeovalordavariávelTopofoiincrementado,eoelemento’E’foiinseridonovetorElementosnaposiçãoindicadapelovaloratualizadodavariávelTopo.

AFigura2.12apresentaumalgoritmoconceitualparaaOperaçãoEmpilha.SeaPilhaPestivercheia,sinalizamosatravésdoparâmetroDeuCertoqueoelementoXnãofoiinserido.Mas,seaPilhaPnãoestivercheia,Xseráinseridodaseguinteforma:incremen-tamosoTopodaPilhaP(P.Topo=P.Topo+1)earmazenamosXnovetorElementos,naposiçãoindicadapeloTopodaPilha(P.Elementos[P.Topo]=X).OelementoXpassaráaseroelementodoTopodaPilha.

Exercício 2.6 Operação DesempilhaConformeespecificadonaFigura2.5,aoperaçãoDesempilharecebecomoparâmetroaPilhadaqualqueremosretirarumelemento.CasoaPilhanãoestivervazia,aoperaçãoretornaovalordoelementoretirado.AaçãodaoperaçãoDesempilha,nasituaçãodaFigura2.13a,resultarianasituaçãodaFigura2.13b.

Figura 2.12 Algoritmo conceitual — Empilha.

Figura 2.13 Operação Desempilha.

26


Exercício 2.7 Operação CriaConformeespecificadonaFigura2.5,aoperaçãoCriarecebecomoparâmetroaPilhaquedeverásercriada.CriaraPilhasignificainicializarosvaloresdemodoaindicarqueaPilhaestávazia,ouseja,semnenhumelemento.

Exercício 2.8 Operação VaziaConformeespecificadonaFigura2.5,aoperaçãoVaziatestaseaPilhapassadacomoparâmetroestávazia(semelementos),retornandoovalorVerdadeiro(Pilhavazia)ouFalso(Pilhanãovazia).

Exercício 2.9 Operação CheiaConformeespecificadonaFigura2.5,aoperaçãoCheiatestaseaPilhapassadacomoparâmetroestácheia.APilhaestarácheiasenaestruturadearmazenamentonãocoubermaisnenhumelemento.

ConformemostraaFigura2.14,naoperaçãoCriainicializamosoTopodaPilhacomovalorzero,poisoselementoscomeçamaserarmazenadosnovetorElementosapartirdaposição1.Assim,comovalordeToposendozero,indicamosqueaPilhaestávazia.

Figura 2.14 Pilha Vazia e Pilha Cheia.


27

Noteque,emvezdecomeçarem1,seovetorcomeçaremzero(esseéopadrãonalinguagemC)asituaçãodePilhavaziaserácaracterizadaquandoovalordoTopofor−1.

AoperaçãoVaziasimplesmentetestaráseoTopodaPilhaestáapontandoparaovalorzero.SeovalordoTopoforzero,aPilhaestarávazia.SeovalordoToponãoestiveremzero,aPilhanãoestarávazia.Se,emvezdecomeçarem1,ovetorcomeçaremzero(padrãonalinguagemC)aPilhaestarávaziaquandoovalordoTopofor−1.

Analogamente,naoperaçãoCheiaverificamosseovalordoTopoéigualàconstanteTamanho,queindicaoTamanhodaPilha.Se,emvezdecomeçarem1,ovetorcomeçaremzero(padrãonalinguagemC)asituaçãodePilhacheiaserácaracterizadaquandoovalordoTopoforigualaTamanho−1.

Nofinaldestecapítulosãoapresentadassoluçõesousugestõesparaalgunsdosexercícios.Mas,paradesenvolverashabilidadespretendidas,proponhasuasprópriassoluçõesantesdeconsultarasrespostasesugestões.

2.6 Abrir ou não a televisão?SuponhaquequeiramosdesenvolverumaoperaçãoparaconsultarovalordoelementodotopodeumaPilha.Nãoqueremosretiraroelementodotopo;queremosapenasconsultaroseuvalor,semretirá-lodaPilha.Penseemduasestratégiasdiferentesparaimplementaressaoperação.

Exercício 2.10 Duas estratégias para elemento do topoDesenvolvaumaoperaçãoqueretorneovalordoelementodotopodeumaPilhasemretiraroelementodaPilha.Proponhaduassoluçõesdiferentesparaessaoperaçãoecompareassoluções,apontandosuasvantagensedesvantagens.Proponhaecompareassoluçõesantesdeprosseguiraleitura.

PodemosimplementaraoperaçãoElementodoTopobasicamentededuasmaneiras.Aprimeiramaneiraédependentedaestruturadearmazenamento,easegundamaneiraéindependentedaestruturadearmazenamento.NaFigura2.15apresentamosduassoluçõesparaaoperaçãoElementodoTopo.Adiferençaentreassoluçõesestádestacadaemnegrito.OquemudaéomododepegarainformaçãodoTopodaPilha.

Naprimeirasolução,pegamosovalordoelementodoToposimplesmenteatribuindoaXovalordeP.Elementos[P.Topo].Nessaprimeirasolução,ficaevidentequeaestruturadearmazenamentoutilizadaéumvetor.Ouseja,éumasoluçãodependentedaestruturadearmazenamento;sófuncionaránaestruturadearmazenamentoemquestão—umvetor.Nasegundaimplementação,pegamosovalordoelementodoTopoatravésdaoperaçãoDesempilha.AoperaçãoDesempilharetornaovalordoelementodoToponavariávelX,masretiraoelementodaPilha.Porisso,temosquerecolocaroelementonaPilhaatravésdaoperaçãoEmpilha.Nessasegundasolução,nãoficaevidenteaestruturadearmazenamentoutilizada.É,portanto,umasoluçãoindependentedaestruturadearmazenamento.

28


Quaisasvantagensdeumasoluçãoedeoutra?Aprimeirasoluçãofuncionaráexclusiva-mentenessaimplementaçãoquefizemosdaPilha,comAlocaçãoSequencialeEstáticadeMemória.NoscapítulosaseguirimplementaremosumaPilhacomoutrastécnicas,eessaprimeirasoluçãonãocontinuaráfuncionando;teráqueserreescrita.AsegundasoluçãoparaaoperaçãoElementodoTopoéindependentedaestruturadearmazenamento,poismanipulaaPilhaexclusivamenteatravésdosoperadoresVazia,EmpilhaeDesempilha.Assim,essasegundaimplementaçãocontinuaráfuncionandomesmoseadotarmosumanovaestruturadearmazenamentoparaaPilha,comofaremosnospróximoscapítulos.Porserindependentedaestruturadearmazenamento,asegundasoluçãoproporcionamaiorportabilidadedecódigo,conceitoqueestudamosnoCapítulo1.

Vocêpodeestarpensando:“Paraquecomplicar,sepodemossimplesmenteconsultarovalordoelementodoTopocomumcomandoX=P.Elementos[P.Topo]”?Sim,éumasoluçãoeficiente.Masédependentedaimplementaçãoenãoproporcionaportabilidadedecódigo.

PensetambémnassoluçõesdosExercícios2.1a2.4.OExercício2.2,porexemplo,verificaseumaPilhaP1possuimaiselementosdoqueumaPilhaP2.PodemosterumasoluçãoquesimplesmentecomparaosvaloresdoTopodasPilhasP1eP2,ouseja,seP1.TopoformaiordoqueP2.Topo,aPilhaP1temmaiselementosdoqueaPilhaP2.Essaseriaumasoluçãodependentedaestruturadearmazenamento;dependentedaim-plementação.Ocódigodessasoluçãonãoseriaportável.Seriacomoabrirumatelevisãocomumachavedefendaparaaumentarovolume.

UmasegundasoluçãopoderiadesempilhartodososelementosdeP1edeP2,colocandooselementosemPilhasauxiliaresecontandooselementosdecadaPilha.DepoisoselementospoderiamserdevolvidosàsPilhasoriginais.Essasegundasoluçãoseriain-dependentedaestruturadearmazenamento;independentedaimplementação.Umasoluçãoportável.ConformeestudamosnoCapítulo1,portabilidadeereusabilidade

Figura 2.15 Soluções para a operação Elemento do Topo.


29

decódigosãocaracterísticasextremamentedesejáveise,nolongoprazo,tornamassoluçõesmaisbaratas.

Chavedefendaoubotãodatelevisão?Qualdessassoluçõesvocêconsideramaisin-teressante?

Operações Primitivas e Não PrimitivasPodemosdizerque,emumaPilha,asoperaçõesEmpilha,Desempilha,Cria,VaziaeCheiasãoOperações Primitivas,poissópodemserimplementadasatravésdeumasoluçãodependentedaestruturadearmazenamento.JáasoperaçõesquedesenvolvemosnosExercícios2.1a2.4e2.10(transferirelementosdeumaPilhaaoutra,verificarseumaPilhatemmaiselementosqueoutra,verificarseumaPilhapossuiumelementocomvalorX,verificarseduasPilhassãoiguaisepegarovalordoElementodoTopodeumaPilha)sãoOperações Não Primitivas,poispodemserimplementadasapartirdechamadasaOperaçõesPrimitivasdoTADPilha,resultandoemumaimplementaçãoindependentedaestruturadearmazenamento.

Visandoproporcionarportabilidadeereusabilidadedecódigo,menorcustodedesenvol-vimentoemanutenção,amelhorformadeimplementarumaOperaçãoNãoPrimitivaédemodoabstrato,manipulandooTADemquestãoexclusivamentepelasOperaçõesPrimitivasou,ainda,pelos“botõesdatelevisão”.

2.7 Projeto FreeCell: Pilha Burra ou Pilha Inteligente?NoFreeCelltemosoitoPilhasIntermediáriasquepossuemalgumasrestriçõescomrelaçãoaovalordoselementosqueserãoempilhados.NessasPilhasIntermediáriassóépossívelempilharcartasemordemdecrescenteeemcoresalternadas—pretassobrevermelhasevermelhassobrepretas.

TemostambémnoFreeCellumsegundotipodePilha,asPilhasDefinitivas,quetambémpossuemsuasregrascomrelaçãoaovalordoselementosqueserãoempilhados.NessasquatroPilhasDefinitivassóépossívelempilharcartasdeummesmonaipeeemordemcrescente.

AcaracterísticabásicadeinserirelementossemprenoTopoéválidatantoparaasPilhasIntermediáriasquantoparaasPilhasDefinitivas.MasasregrascomrelaçãoaovalordoselementosqueserãoempilhadossãodiferentesparaPilhasIntermediáriasePilhasDefinitivas.

Figura 2.16 Definição de Operações Primitivas e Não Primitivas.

30


APilhaquedefinimoseimplementamosnasseçõesanterioreséuma“pilhaburra”,poiselanãofazqualquerverificaçãoquantoaovalordoelementoqueestásendoempilhado.Comovocêachaquepodemosimplementara”inteligência“dasPilhasIntermediáriasedasPilhasDefinitivas?Por”inteligência“queremosdizeraverificaçãodosvaloresqueestãosendoempilhados,parasabersepodemserinseridosemumaPilhaIntermediáriaouemumaPilhaDefinitiva,deacordocomasregrasdefuncionamentodoFreeCell.

AFigura2.18mostratrêsalternativasparaimplementara”inteligência“dasPilhas.Umaprimeiraalternativa(soluçãoA)seriautilizarumaPilhaBurraerealizartodasasverificaçõesnaaplicação.Ouseja,”fora“doTADPilhaéqueiríamosverificarseumacartapodeounãoserempilhada.NessasoluçãoA,tantoasPilhasIntermediáriasquantoasPilhasDefinitivaspoderiamserimplementadasatravésdomesmoTADPilhaBurra.

Umasegundaalternativa(soluçãoB)seriadesenvolverdoisTADsdiferentes,PilhaInterme-diáriaePilhaDefinitiva,cadaqualincorporandosuaprópriainteligência.Nessasolução,aaplicaçãoemsinãofariaqualquerverificaçãodevalores.Todaaverificaçãoseriafeita”dentro“dasPilhas.Se,pelasregrasdoFreeCell,umacartanãopuderserempilhada,a

Figura 2.17 Pilha Intermediária: ordem decrescente e em cores alternadas. Pilha Definitiva: ordem crescente e cartas do mesmo naipe.


31

própriaPilhavaiidentificarissoecomunicaràaplicação.Noteque,nasoluçãoB,temosduasimplementaçõesdistintasdePilha:aPilhaIntermediáriaeaPilhaDefinitiva.

AsoluçãoCéumavariaçãodasoluçãoB.AdiferençaéquenasoluçãoCaPilhaIn-termediáriaeaPilhaDefinitivasãoimplementadascombaseemumaPilhaBurra.Emumalinguagemorientadaaobjeto,comoC++,asPilhasIntermediáriaseasPilhasDefinitivaspodem”herdar“característicasdaPilhaBurraeagregarsuascaracterísticasprópriasediferenciadas—a”inteligência“.Mesmosemutilizaroconceitodeherançadaorientaçãoaobjetos,asoperaçõesdasPilhasIntermediáriaeDefinitivapodemserimplementadasatravésdechamadasàsoperaçõesdaPilhaBurra.

Astrêssoluçõesincluemummóduloqueimplementaainterfacedosistemacomousuário.Incluirummóduloindependenteparaainterfaceaumentaaportabilidadedasoluçãoefacilitaajustesoumesmoumatrocaradicaldeinterfaceoudeplataforma,semgrandesmudançasnosdemaismódulos.

Qualdessastrêssoluções—A,BouC—vocêconsideramaisadequadaaoseuprojeto?

Exercício 2.11 Avançar o Projeto FreeCell — propor uma arquitetura de softwarePilhaBurra?PilhaInteligente?ProponhaumaarquiteturadesoftwareparaoseuProjetoFreeCellidentificandoosprincipaismódulosdosistemaeorelacionamentoentreeles.TomecomopontodepartidaassoluçõesalternativaspropostasnaFigura2.18.Escolhaaalternativaqueformaisadequadaaoseuprojetoouadapteumadasalternativas,conformenecessário.Sugestãoparausoacadêmico:desenvolvaoProjetoFreeCellemgrupo.Promovaumadiscussão,definaaarquiteturadosoftwareedividaotrabalhoentreoscomponentesdogrupo.

Figura 2.18 Projeto FreeCell — soluções alternativas quanto à arquitetura do software.

32


SejaqualforaarquiteturadesoftwarequeadotarparaoseuProjetoFreeCell,visandoagregarportabilidadeereusabilidade,observeasseguintesrecomendaçõesnaim-plementação:

● ParamanipularasPilhasdeCartas,projeteeutilizeumTADPilha(sejaumaPilhaBurra,sejaumaPilhaInteligente).

● AaplicaçãoemsieoTADPilhadevemestaremunidadesdesoftwareindependenteseemarquivosseparados;utilizeumarquivoexclusivamenteparaaimplementaçãodoTADPilha.

●• Aaplicação(eoutrosmódulos)devemanipularoTADPilhaexclusivamenteatravésdosseusOperadoresPrimitivos:Empilha,Desempilha,Vazia,CriaeCheia.Aumenteovolumedatelevisãoapenaspelobotãodevolume.

● IncluanocódigodoTADPilhaexclusivamenteaçõespertinentesaoarmazena-mentoerecuperaçãodasinformaçõessobreasPilhasdeCartas.FaçaopossívelparanãoincluirnoTADPilhaaçõesrelativasàinterfaceouaqualqueroutroaspectoquenãosejaoarmazenamentoearecuperaçãodeinformaçõessobreasPilhasdeCartas.

Exercício 2.12 Implementar uma Pilha BurraImplementeumTADPilhaBurra(Pilhasemqualquerrestriçãoaosvaloresqueestãosendoempilhados)emumalinguagemdeprogramaçãocomoCouC++,semutilizarrecursosdaorientaçãoaobjetos.DefinaumtipoestruturadoeosOperadores.OselementosdaPilhadevemserdotipoInteiro.ImplementeaPilhacomoumaunidadeindependente.Emumarquivoseparado,façaoprogramaprincipalbemsimples,paratestarofuncionamentodaPilha.

Exercício 2.13 Implementar uma Pilha Burra como uma classeImplementeumTADPilhaBurra(Pilhasemqualquerrestriçãoaosvaloresqueestãosendoempilhados)emumalinguagemdeprogramaçãoorientadaaobjetos,comoC++.ImplementeaPilhacomoumaclasse.OselementosdaPilhadevemserdotipoInteiro.ImplementeaPilhacomoumaunidadeindependente.Emumarquivoseparado,façaoprogramaprincipalbemsimples,paratestarofuncionamentodaPilha.

Exercício 2.14 Avançar o Projeto FreeCell — defina e implemente a Carta do BaralhoDefinaeimplementeaCartadoBaralho,comoumaclasseoucomoumtipoes-truturado.Nãosepreocupe,nestemomento,comaspectosdainterface.Preocupe-seemdefinirumacartacomnaipe(ouro,paus,copasouespadas)evalor(A,2,3,4,5,6,7,8,9,10,J,Q,K).

Exercício 2.15 Avançar o Projeto FreeCell — implemente uma Pilha Intermediária InteligenteDefinaeimplementeumaPilhaIntermediária”Inteligente“,ouseja,comrestriçõesquantoàscartasqueserãoempilhadas,conformeasregrasdoFreeCellconvencionalouconformeasregrasdoseuProjetoFreeCell.OselementosdaPilhadevemserdotipoCarta,conformedefinidonoExercício2.14.ParaimplementaraPilhaIntermediáriaInteligente,utilizedealgummodoaPilhaBurraimplementadanoExercício2.12ouno


33

Exercício2.13.FaçaumprogramaparatestarofuncionamentodaPilhaIntermediáriaInteligentesemsepreocuparcomaqualidadedainterface.

Exercício 2.16 Avançar o Projeto FreeCell — implemente uma Pilha Definitiva InteligenteDefinaeimplementeumaPilhaDefinitiva”Inteligente“,ouseja,comrestriçõesquantoàscartasqueserãoempilhadas,conformeasregrasdoFreeCellconvencional.OselementosdaPilhadevemserdotipoCarta,conformedefinidonoExercício2.14.ParaimplementaraPilhaDefinitivaInteligente,utilizedealgummodoaPilhaBurraimplementadanoExercício2.12ounoExercício2.13.FaçaumprogramaparatestarofuncionamentodaPilhaDefinitivaInteligentesemsepreocuparcomaqualidadedainterface.

Exercício 2.17 Avançar o Projeto FreeCell — defina as regras, escolha um nome e inicie o desenvolvimento do seu FreeCellDefinaasregrasdoseuFreeCellalterandoasregrasdoFreeCellconvencionalemalgumaspecto.DêpersonalidadeprópriaaoseuFreeCelleescolhaparaoseujogoumnomequereflitasuascaracterísticasmaismarcantes.EscrevaasregrasdoseuFreeCellecoloqueemumarquivo-texto,paraquepossaserutilizadonadocumentaçãodojogoouemumaopçãodojogoqueensinecomojogar.Definaaarquiteturadosoftware(Exercício2.11),adapteasPilhasdesenvolvidas(Exercícios2.12a2.16)einicieodesenvolvimentodoseujogo.Sugestãoparausoacadêmico:desenvolvaoProjetoFreeCellemgrupo.Tomeasprincipaisdecisõesemconjuntoedividaotrabalhoentreoscomponentesdogrupo,cadaqualficandoresponsávelporpartedasatividades.

Exercício 2.18 Avançar o Projeto FreeCell — inicie o projeto da interface EmparaleloaodesenvolvimentodalógicadoFreeCell,escolhaeestudeumabibliotecagráficaparaajudaraconstruirumainterfacevisualeintuitivaparaoseujogo.VocêpodecomeçarestudandooTutorial de Programação GráficadisponívelnosMateriaisComplementaresdeEstruturas de dados com jogos,masfiquelivreparaes-tudaroutrosmateriaisouadotaroutrasferramentasgráficasnoseuFreeCell.Projeteainterfacedomodomaisindependentepossíveldosdemaismódulos.Seestivertrabalhandoemgrupo,umdosmembrosdogrupopodesededicaraestudarmaisintensamenteosaspectosreferentesàinterfaceedepoisajudarosdemaiscompo-nentesnoaprendizado.Vocêpodeoptartambémporimplementarprimeiramenteumainterfacebemsimples,textual,paratestarbemosdemaiscomponentesdojogoedepoissubstituirporumainterfacegráfica.Emalgummomento,vocêprecisarámesmoganharexperiêncianodesenvolvimentodesoftwareutilizandobibliotecasgráficas.Porquenãoagora?

Comece a desenvolver o seu FreeCell agora!

Façaumjogolegal!Façaumjogoquetenhaasuacara!Façaseujogoficaratrativo,distribuaparaosamigos,disponibilizepublicamente,façaseujogobombar!Aprenderaprogramarpodeserdivertido!

34


http://www.elsevier.com.br/edcomjogos

Consulte no Banco de Jogos AdaptaçõesdoFreeCellwww.elsevier.com.br/edcomjogos

Consulte nos Materiais Complementares TutorialdeProgramaçãoGráfica

Exercícios de fixaçãoExercício 2.19OqueéumaPilha?

Exercício 2.20ParaqueserveumaPilha?EmquetipodesituaçõesumaPilhapodeserutilizada?

Exercício 2.21OquesignificaAlocaçãoSequencialdeMemóriaparaumconjuntodeelementos?

Exercício 2.22OquesignificaAlocaçãoEstáticadeMemóriaparaumconjuntodeelementos?

Exercício 2.23FaçaoesquemadaimplementaçãodeumaPilhacomAlocaçãoSequen-cialeEstáticadeMemória,edescrevaoseufuncionamento.

Exercício 2.24 Desafio das Torres de Hanoi.ODesafiodasTorresdeHanoiéumjogoclássico,inspiradoemumaantigalenda.Ojogocontacomtrêshastesverticais.Umadashastescontémtrêsdiscos:embaixo,umprimeirodiscodediâmetromaior;emcimadesseprimeirodisco,háumsegundodiscodediâmetroumpoucomenor;eemcimadessesegundodisco,háumterceirodiscodediâmetroaindamenor,comoilustraaFigura2.19.Odesafiodojogoépassartodosostrêsdiscos,nessamesmasequência,paraumadasoutrashastesverticais.Épossívelutilizarastrêshastesparaauxiliaramovimentaçãodosdiscos.Masexistemalgumasrestriçõesnamovimentação:sóépos-sívelmovimentarumdiscodecadavez;sóépossívelretirarodiscodotopodeumapilhadediscos;sóépossívelinserirdiscosnotopodeumapilhadediscos;emnenhummomentovocêpodecolocarumdiscoemcimadeoutrodiscocomdiâmetromenor.SenãoconhecebemoDesafiodasTorresdeHanoi,joguealgumaspartidasemumaversãoon-line(porexemplo,noGamesOnenoUOLJogos—links1e2)ouassistaaalgumvídeo(porexemplo,noslinks3e4)parasefamiliarizarcomojogo.Épossívelaumentaraquantidadedediscosecomissoaumentarograudedificuldade.ComovocêpoderiausarumaoumaisPilhasparaimplementarumjogocomooDesafiodasTorresdeHanoi?

Exercício 2.25 Identificar outras aplicações de Pilhas.IdentifiqueelisteaplicaçõesdePilhas.IdentifiqueeanotealgunsjogosquepodemserimplementadoscomousodeumaPilhaeidentifiquetambémoutrasaplicaçõesdeforadomundodosgames.Suges-tãodeusoacadêmico:façaumadiscussãoemgrupo.Aofinal,cadagrupoapresenta




35

atodososestudantesasaplicaçõesqueidentificou.Podeserumaboafontedeideiasparanovosjogos.

Figura 2.19 Ilustração do Desafio das Torres de Hanoi.

36


Soluções e sugestões para alguns exercíciosExercício 2.2 Mais elementos?


37

Exercício 2.4 As Pilhas são iguais?

38


Exercício 2.12 Implementação de uma ”Pilha Burra“


39

40


Exercício 2.13 Pilha Burra como classe em C + +


41

42


Exercício 2.14 Carta do BaralhoSugestões:

● ACarta-do-Baralhopodeserumtipoestruturadoouumaclasse,comdoiscampos:Naipe(ouros,copas,espadasepaus)eValor(A,2,3,4,5,6,7,8,9,10,J,Q,K).Onaipepodeserdefinidocomoumtipoenumeradooudotipointeiro(nessecaso,estabelecendoumacorrelaçãodotipoouros=1,copas=2,eassimpordiante).Valorpodeserumtipoenumerado,dotipointeirooudotipoChar.

● Tambémépossíveldefiniroperaçõessobrecartas—operaçãopararetornaronaipe,retornarovalor,atualizaronaipe,atualizarovalor,entreoutras.

Exercício 2.15 e 2.16 Pilha Intermediária Inteligente e Pilha Definitiva InteligenteSugestões:

● DefinaumaclassePilhaBurradeelementosdotipoCarta-do-Baralho.EntãodefinaumaclassePilhaIntermediáriaherdandocaracterísticasdaclassePilhaBurra;rees-crevaaoperaçãoEmpilha,sópermitindoempilharcartasnasequênciacorreta;emumaPilhaIntermediáriapodemosempilharqualquercartaseaPilhaestivervaziaouemordemdecrescenteeemcoresalternadas,seaPilhanãoestivervazia.

● FaçaomesmoparaaclassePilhaDefinitiva;emumaPilhaDefinitivapodemosempi-lharsomenteacartadevalorAseaPilhaestivervaziaouemordemcrescenteedomesmonaipe,seaPilhanãoestivervazia.

● NapráticavocêterátrêsoperaçõesEmpilha(PilhaBurra,PilhaDefinitivaePilhaIntermediária).Ocódigodasdemaisoperaçõesserácomum.

Paraexemplificar,seguetrechodeimplementaçãodeumaPilhaInteligentecomelementosdotipointeiro,naqualsóépossívelempilharelementosmaioresdoqueoelementodotopodapilha.


43

Links1. GamesOn:TorredeHanoi:http://www.gameson.com.br/Jogos-Online/ClassicoPuzzle/

Torre-de-Hanoi.html(consultaemsetembrode2013).2. UOLJogos:TorredeHanoi:http://jogosonline.uol.com.br/torre-de-hanoi_1877.html

(consultaemsetembrode2013).3. YouTube:TorresdeHanoi:Bezerra:http://www.youtube.com/watch?v=yrNWiFFbcEY

(consultaemsetembrode2013).4. YouTube:TorresdeHanoi:Neves:http://www.youtube.com/watch?v=3qTe_X1yXEs

(consultaemsetembrode2013).

Referências e leitura adicionalKnuthD.The Art of Computer Programming.VolumeI:FundamentalAlgorithms.Reading,MA:Addi-

son-Wesley,1972.LangsamY,AugensteinMJ,TenenbaumAM.Data Structures Using C and C++.2nded.UpperSaddle

River.NewJersey:PrenticeHall,1996.PereiraSL.Estruturasdedadosfundamentais:conceitoseaplicações.SãoPaulo:Érica;1996.

http://www.gameson.com.br/Jogos-Online/ClassicoPuzzle/Torre-de-Hanoi.html

http://www.gameson.com.br/Jogos-Online/ClassicoPuzzle/Torre-de-Hanoi.html

http://jogosonline.uol.com.br/torre-de-hanoi_1877.html

http://www.youtube.com/watch?v=yrNWiFFbcEY

http://www.youtube.com/watch?v=3qTe_X1yXEs

http://refhub.elsevier.com/B978-85-352-7804-0.00002-7/ref0010

Documents

Cap-tulo-2-Pilhas-com-Aloca-o-Sequencial-e-Est-tica_2014_Estruturas-de-Dados-Com-Jogos.pdf