實驗二棧和隊列的基本操作實現(xiàn)及其應用一、實驗目的1、熟練掌握棧和隊列的基本操作在兩種存儲結構上的實現(xiàn)。2、會用棧和隊列解決簡單的實際問題。二、實驗內容（可任選或全做）題目一、試寫一個算法，判斷依次讀入的一個以@為結束符的字符序列，是否為回文。所謂“回文“是指正向讀和反向讀都一樣的一字符串,如“321123”或“ableelba”相關常量及結構定義：#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOK1#defineERROR0typedefintSElemType;//棧類型定義typedefstructSqStack {SElemType*base;SElemType*top;intstacksize;}SqStack;設計相關函數(shù)聲明：判斷函數(shù)：intIsReverse()棧：intInitStack(SqStack&S)intPush(SqStack&S,SElemTypee)intPop(SqStack&S,SElemType&e)intStackEmpty(s)題目二、編程模擬隊列的管理，主要包括：出隊列、入隊、統(tǒng)計隊列的長度、查找隊列某個元素e、及輸出隊列中元素。[實現(xiàn)提示]：參考教材循環(huán)隊列的有關算法，其中后兩個算法參考順序表的實現(xiàn)。題目三、RailsDescriptionThereisafamousrailwaystationinPopPush

ThelocaltraditionisthateverytrainarrivingfromthedirectionAcontinuesinthedirectionBwithcoachesreorganizedinsomeway.AssumethatthetrainarrivingfromthedirectionAhasN<=1000coachesnumberedinincreasingorder1,2,...,N.ThechieffortrainreorganizationsmustknowwhetheritispossibletomarshalcoachescontinuinginthedirectionBsothattheirorderwillbea1,a2,...,aN.Helphimandwriteaprogramthatdecideswhetheritispossibletogettherequiredorderofcoaches.YoucanassumethatsinglecoachescanbedisconnectedfromthetrainbeforetheyenterthestationandthattheycanmovethemselvesuntiltheyareonthetrackinthedirectionB.Youcanalsosupposethatatanytimetherecanbelocatedasmanycoachesasnecessaryinthestation.ButonceacoachhasenteredthestationitcannotreturntothetrackinthedirectionAandalsoonceithasleftthestationinthedirectionBitcannotreturnbacktothestation.InputTheinputconsistsofblocksoflines.Eachblockexceptthelastdescribesonetrainandpossiblymorerequirementsforitsreorganization.InthefirstlineoftheblockthereistheintegerNdescribedabove.Ineachofthenextlinesoftheblockthereisapermutationof1,2,...,N.Thelastlineoftheblockcontainsjust0.

Thelastblockconsistsofjustonelinecontaining0.OutputTheoutputcontainsthelinescorrespondingtothelineswithpermutationsintheinput.AlineoftheoutputcontainsYesifitispossibletomarshalthecoachesintheorderrequiredonthecorrespondinglineoftheinput.OtherwiseitcontainsNo.Inaddition,thereisoneemptylineafterthelinescorrespondingtooneblockoftheinput.Thereisnolineintheoutputcorrespondingtothelast``null''blockoftheinput.SampleInput512345541230665432100SampleOutputYesNoYes題目四、SlidingWindowDescriptionAnarrayofsizen≤106isgiventoyou.Thereisaslidingwindowofsizekwhichismovingfromtheveryleftofthearraytotheveryright.Youcanonlyseetheknumbersinthewindow.Eachtimetheslidingwindowmovesrightwardsbyoneposition.Followingisanexample:

Thearrayis[1

3

-1

-3

5

3

6

7],andkis3.WindowpositionMinimumvalueMaximumvalue[1

3

-1]

-3

5

3

6

7

-13

1

[3

-1

-3]

5

3

6

7

-33

1

3

[-1

-3

5]

3

6

7

-35

1

3

-1

[-3

5

3]

6

7

-35

1

3

-1

-3

[5

3

6]

7

36

1

3

-1

-3

5

[3

6

7]37Yourtaskistodeterminethemaximumandminimumvaluesintheslidingwindowateachposition.InputTheinputconsistsoftwolines.Thefirstlinecontainstwointegersnandkwhicharethelengthsofthearrayandtheslidingwindow.Therearenintegersinthesecondline.OutputTherearetwolinesintheoutput.Thefirstlinegivestheminimumvaluesinthewindowateachposition,fromlefttoright,respectively.Thesecondlinegivesthemaximumvalues.SampleInput8313-1-35367SampleOutput-1-3-3-333335567題目五（選作考查串知識）DNAEvolution【Description】Evolutionisaseeminglyrandomprocesswhichworksinawaywhichresemblescertainapproachesweusetogetapproximatesolutionstohardcombinatorialproblems.Youarenowtodosomethingcompletelydifferent.GivenaDNAstringSfromthealphabet{A,C,G,T},findtheminimalnumberofcopyoperationsneededtocreateanotherstringT.Youmayreversethestringsyoucopy,andcopybothfromSandthepiecesofyourpartialT.Youmayputthesepiecestogetheratanytime.YoumayonlycopycontiguouspartsofyourpartialT,andallcopiedstringsmustbeusedinyourfinalT.Example:FromS=“ACTG”createT=“GTACTAATAAT”GetGT.........bycopyingandreversing"TG"fromS.GetGTAC...bycopying"AC"fromS.GetGTACTA…..bycopying"TA"fromthepartialT.GetGTACTAATbycopyingandreversing"TA"fromthepartialT.GetGTACTAATAATbycopying"AAT"fromthepartialT.【Input】Thefirstlineofinputgivesasingleinteger,1≤k≤10,thenumberoftestcases.Thenfollow,foreachtestcase,alinewiththestringS,lengthofSislessthen19,andalinewiththestringT,lengthofTislessthen19.【Output】OutputforeachtestcasethenumberofcopyoperationsneededtocreateTfromS,or"impossible"ifitcannotbedone.【SampleInput】4ACGTTGCAACACGTTCGATCGAAAAAAAAAAAAAAAAAAAA【Sampleoutput】1impossible46題目六（選作考查數(shù)組知識）MagicSquares描述Followingthesuccessofthemagiccube,Mr.Rubikinventeditsplanarversion,calledmagicsquares.Thisisasheetcomposedof8equal-sizedsquares:12348765Inthistaskweconsidertheversionwhereeachsquarehasadifferentcolor.Colorsaredenotedbythefirst8positiveintegers.Asheetconfigurationisgivenbythesequenceofcolorsobtainedbyreadingthecolorsofthesquaresstartingattheupperleftcornerandgoinginclockwisedirection.Forinstance,theconfigurationofFigure3isgivenbythesequence(1,2,3,4,5,6,7,8).Thisconfigurationistheinitialconfiguration.Threebasictransformations,identifiedbytheletters`A',`B'and`C',canbeappliedtoasheet:'A':exchangethetopandbottomrow,'B':singlerightcircularshiftingoftherectangle,'C':singleclockwiserotationofthemiddlefoursquares.Belowisademonstrationofapplyingthetransformationstotheinitialsquaresgivenabove:A:87651234B:41235876C:17248635Allpossibleconfigurationsareavailableusingthethreebasictransformations.Youaretowriteaprogramthatcomputesaminimalsequenceofbasictransformationsthattransformstheinitialconfigurationabovetoas