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

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

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.

Estruturas de Dados com Jogos

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

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

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.

Estruturas de Dados com Jogos

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

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

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.

Estruturas de Dados com Jogos

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

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

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.

Estruturas de Dados com Jogos

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

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

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.

Estruturas de Dados com Jogos

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

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

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.

Estruturas de Dados com Jogos

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

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

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

Estruturas de Dados com Jogos

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

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

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

Estruturas de Dados com Jogos

35

atodososestudantesasaplicaçõesqueidentificou.Podeserumaboafontedeideiasparanovosjogos.

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

36

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

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

Estruturas de Dados com Jogos

37

Exercício 2.4 As Pilhas são iguais?

38

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

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

Estruturas de Dados com Jogos

39

40

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

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

Estruturas de Dados com Jogos

41

42

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

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.

Estruturas de Dados com Jogos

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.