第02章基本数据结构stacksqueuesliststrees教学提纲.ppt

ElementaryDataStructuresStacks,Queues,&ListsAmortizedanalysisTrees1ElementaryDataStructuresTheStackADT(§)TheStackADTstoresarbitraryobjectsInsertionsanddeletionsfollowthelast-infirst-outschemeThinkofaspring-loadedplatedispenserMainstackoperations:push(object):insertsanelementobjectpop():removesandreturnsthelastinsertedelementAuxiliarystackoperations:objecttop():returnsthelastinsertedelementwithoutremovingitintegersize():returnsthenumberofelementsstoredbooleanisEmpty():indicateswhethernoelementsarestored2ElementaryDataStructuresApplicationsofStacksDirectapplicationsPage-visitedhistoryinaWebbrowserUndosequenceinatexteditorChainofmethodcallsintheJavaVirtualMachineorC++ponentofotherdatastructures3ElementaryDataStructuresArray-basedStack(§)AsimplewayofimplementingtheStackADTusesanarrayWeaddelementsfromlefttorightAvariabletkeepstrackoftheindexofthetopelement(sizeist+1)S012t…Algorithmpop(): ifisEmpty()then throwEmptyStackException else tt1 returnS[t+1]Algorithmpush(o) ift=1then throwFullStackException else tt+1 S[t]paretheincrementalstrategyandthedoublingstrategybyanalyzingthetotaltimeT(n)neededtoperformaseriesofnpushoperationsWeassumethatwestartwithanemptystackrepresentedbyanarrayofsize1Wecallamortizedtimeofapushoperationtheaveragetimetakenbyapushovertheseriesofoperations,.,T(n)/n6ElementaryDataStructuresAnalysisoftheIncrementalStrategyWereplacethearrayk=n/ctimesThetotaltimeT(n)ofaseriesofnpushoperationsisproportionalton+c+2c+3c+4c+…+kc=n+c(1+2+3+…+k)=n+ck(k+1)/2Sincecisaconstant,T(n)isO(n+k2),.,O(n2)TheamortizedtimeofapushoperationisO(n)7ElementaryDataStructuresDirectAnalysisoftheDoublingStrategyWereplacethearrayk=log2ntimesThetotaltimeT(n)ofaseriesofnpushoperationsisproportionalton+1+2+4+8+…+2k=n+2k+1-1=2n-1T(n)isO(n)TheamortizedtimeofapushoperationisO(1)puterasacoin-operateddevicerequiring1cyber-