数据结构英文版课件：Chapter 2 Introduction to Stacks

Chapter2IntroductiontoStacksThischapterintroducesthestudyofstacks,oneofthesimplestbutmostimportantofalldatastructures.Theapplicationofstackstothereversalofdataisillustratedwithaprogramthatcallsonthestandard-librarystackimplementation.AcontiguousimplementationofastackdatastructureisthendevelopedandusedtoimplementareversePolishcalculatorandabracketcheckingprogram.Thechaptercloseswithadiscussionofthegeneralprinciplesofabstractdatatypesanddatastructures.本章引入栈的研究，栈是所有数据结构中最简单但也是最重要的数据结构。本节中先举了一个利用栈的标准库函数完成数据逆置的例子。然后，实现了一个顺序栈，并且在此结构下完成了逆波兰计算器和括号匹配程序。本章最后讨论了抽象数据类型和数据结构的基本原则。ContentPointsStackSpecificationsImplementationofStacksApplication:ADeskCalculatorApplication:BracketMatchingAbstractDataTypesandTheirImplementationsStackSpecification

ProblemReadanintegern,thenreadalistofnnumbers,andprintthelistinreverseorder.Solution1:useanarray.occupyingpartofanarrayoffixedsize,withsomeoftheentriesinthearrayremainingunused.

#include<iostream>usingnamespacestd;intmain()/*Pre:Theusersuppliesanintegernandndecimalnumbers.Post:Thenumbersareprintedinreverseorder.*/{ intn; doubleitem; doublenumbers[]; cout<<"Typeinanintegernfollowedbyndecimalnumbers."

<<endl<<"Thenumberswillbeprintedinreverseorder."<<endl; cin>>n; for(inti=0;i<n;i++){ cin>>item; numbers[i]=item; } cout<<endl<<endl; for(i=n-1;i>=0;i--){ cout<<numbers[i]; } cout<<endl;}25nThedifferencebetweenlistandarray表和数组的区别1、thelengthofalistcanbechangedbyinsertordeletesomeitemsfromthelist,butthelengthofanarrayisanconstant.

表的长度是可变的。即表中的数字是可以增加和删除的，因此，如果n=3，那么表中只有3个数字，如果n=19，那么表中就有19个数字。

数组（或称为向量），具体编程时的术语。数组中的元素个数是个常量，也即当程序被编译时，数组的长度就确定了。

2、Listisadynamicdatastructure,butarrayisanstaticdatastructure.表是一个动态数据结构，因为它的长度是可以变化的，然而，数组是一种静态数据结构，因为它的长度是固定的。

3、Listisalogicalconceptandarrayisaprogrammingfeature.表是一个逻辑层面的概念，数组是编程实现时的概念。TherelationbetweenlistandarrayAlistofvariablesizecanbeimplementedinacomputerbyoccupyingpartofanarrayoffixedsize,withsomeoftheentriesinthearrayremainedunused.

长度可变的表在计算机中的实现可以用一个定长数组实现，其中定长数组的部分单元并未使用。Butwewillfindthatthereareseveralwaystoimplementlists,usinganarrayisonlyoneofthem,weshouldn’tconfusethefundamentaldatastructurewiththechoiceofimplementations.

然而，我们以后会发现，有很多种方法可以用来完成表的实现，因此我们不能将实现方法的选择和更基本的数据结构的选择和定义相混淆。Solution2:useastack#include<stack>;usingnamespacestd;intmain()/*Pre:Theusersuppliesanintegernandndecimalnumbers.Post:Thenumbersareprintedinreverseorder.Uses:TheSTLclassstackanditsmethods*/{intn;doubleitem;stack<double>numbers;//declaresandinitializesastackofnumberscout<<"Typeinanintegernfollowedbyndecimalnumbers."<<endl<<"Thenumberswillbeprintedinreverseorder."<<endl;cin>>n;for(inti=0;i<n;i++){ cin>>item; numbers.push(item);}cout<<endl<<endl;while(!numbers.empty()){ cout<<numbers.top()<<""; numbers.pop();}cout<<endl;}StackSpecificationsSpecifications（定义）

Astack

isalistinwhichallinsertionsanddeletionsofentriesaremadeatoneend,calledthetopofthestack（栈顶）.Thelastentrywhichisinsertedisthefirstonethatwillberemoved（后进先出）.Emptystackmeansthestackhasnoitem.Example:platessittingonthecounterinabusycafeteria.Customerstaketraysoffthetopofstack.employeesreturnedtraysbackontopofthestack.Otherexamples…methods Push（入栈）

Pop（出栈）

empty(判空)top(取栈顶元素) sizeconstructor

Importantproperty:Lastin,firstout---LIFOExampleandsketchmapPushingandpoppingastackPushingandpoppingastackAProblem:Supposewehavefiveitemswhichwerepushedintoastackinturn,theorderofthepushis“abcde”,andthepopturnis“dceba”,pleasedecidetheminimumsizeofthestack.

假设有５个元素abcde顺序进栈（进栈过程中可以出栈），出栈序列为dceba，则该栈容量必定不小于多少。StandardTemplateLibrary(STL)FirstExample:ReversingaList(usingSTLclassstack)#include<stack>intmain()/*Pre:Theusersuppliesanintegernandndecimalnumbers.Post:Thenumbersareprintedinreverseorder.Uses:TheSTLclassstackanditsmethods*/{intn;doubleitem;stack<double>numbers;//declaresandinitializesastackofnumberscout<<"Typeinanintegernfollowedbyndecimalnumbers."<<endl<<"Thenumberswillbeprintedinreverseorder."<<endl;cin>>n;StandardTemplateLibrary(STL)FirstExample:ReversingaListfor(inti=0;i<n;i++){ cin>>item; numbers.push(item);}cout<<endl<<endl;while(!numbers.empty()){ cout<<numbers.top()<<""; numbers.pop();}cout<<endl;}//请参考C++STL中stack类，也可参考msdn或相关书籍。StandardTemplateLibrary(STL)Thestandardtemplatelibrary

(abbreviatedSTL)inC++containsmuchusefulinformation,manyfunctions,andmanyclasses.TheSTLprovidesconvenientimplementationsformanycommondatastructures（公用数据结构）,includingalmostallthedatastructuresweshallstudyinthisbook.WecanincludetheSTLstackimplementationintoourprogramswiththedirective#include<stack>andthenwecandefineinitiallyemptystackobjectsandapplymethodscalledpush,pop,top,andempty.StandardTemplateLibrary(STL)InC++,atemplateconstructionallowsustocreatedatastructureswhoseentrieshavedifferenttypes.Example:stack<double>numbersandstack<int>numbersTheSTLprovidesseveralimplementationsofvariousdatastructuressuchasstacks.（提供各种数据结构的多种实现手段）

Thecode

inaclientprogramshouldnotdependonaparticularchoiceofimplementation,buttheperformanceofthefinalprogrammayverymuchdependonthechoiceofimplementation.（客户程序中的代码不依赖于所用类的具体实现，但程序的性能受栈的具体实现手段的影响。）

Asecond,optionaltemplateparameterselectstheimplementation.Tostackthedefaultimplementationcomesfromdeque.(double-endedqueue)TheSTLimplementationsarehighlyefficient,convenientanddesignedwithenoughdefaultoptionstoallowprogrammerstousethemeasily.(高效、方便、很多可选项)InformationHiding

（信息隐藏）

informationhiding：ThemethodsforhandlingstacksareimplementedintheC++standardlibrary,andwecanusethemwithoutneedingtoknowthedetailsofhowstacksarekeptinmemoryorofhowthestackoperationsareactuallydone.

Oneimportantdifferencebetweenpracticinginformationhidingwithregardtoarraysandpracticinginformationhidingwithregardtostacks：

C++providesjustonebuilt-inimplementationofarrays,buttheSTLhasseveralimplementationsofstacks.InformationHiding

（信息隐藏）advantageofinformationhiding（信息隐藏的优点）

Iftheinstructionsformanipulatingastackhavebeenwrittenouteverytimeastackisused,theneveryoccurrenceoftheseinstructionswillneedtobechanged.Ifwehavepracticedinformationhidingbyusingseparatefunctionsformanipulatingstacks,thenonlythedeclarationswillneedtobechanged.（用方法封装栈的操作，当栈的实现改变时，修改更容易）---changeofimplementation

Anotheradvantageofinformationhidingshowsupinprogramsthatusestackswheretheveryappearanceofthewordspushandpop

immediatelyalertapersonreadingtheprogramtowhatisbeingdone,whereastheinstructionsthemselvesmightbemoreobscure.---clarityofprogram

Weshallfindthatseparatingtheuseofdatastructuresfromtheirimplementationwillhelpusimprovethetop-downdesignofbothourdatastructuresandourprograms.---top-downdesign

ImplementationofStack

（栈的实现）

StackSpecificationofMethodsforStacksconstructor---initialization（构造函数---初始化）Theconstructorisafunctionwiththesamenameasthecorrespondingclassandnoreturntype.Itisinvokedautomaticallywheneveranobjectoftheclassisdeclared.SpecificationofMethodsforStacks

EntryTypes,Generics（泛型）

Forgenerality,weuseStack_entryforthetypeofentriesinaStack.AclientcanspecifythistypewithadefinitionsuchastypedefintStack_entry;ortypedefcharStack_entry;Theabilitytousethesameunderlyingdatastructureandoperationsfordifferententrytypesiscalledgenerics.typedef

providessimplegenerics.StartinginChapter6,weshalluseC++templatesforgreatergenerality.SpecificationofMethodsforStacks

ErrorProcessing

（出错处理）

WeshalluseasingleenumeratedtypecalledError_codetoreporterrorsfromallofourprogramsandfunctions.TheenumeratedtypeError_codeispartoftheutilitypackageinAppendixC.StacksusethreevaluesofanError_code:success,overflow,underflowLater,weshalluseseveralfurthervaluesofanError_code.DeterminethemethodsandtheirspecificationsfortheStackclass,similarastheSTLstackclass: pop push top empty

SpecificationofMethodsforStacks

SpecificationforMethods（方法的定义）Error_codeStack::push(constStack_entry&item);pre:None.post:IftheStackisnotfull,itemisaddedtothetopoftheStack.IftheStackisfull,anError_codeofoverflow（上溢）

isreturnedandtheStackisleftunchanged.Error_codeStack::pop();pre:None.post:IftheStackisnotempty,thetopoftheStackisremoved.IftheStackisempty,anError_codeofunderflow（下溢）

isreturnedandtheStackisleftunchanged.SpecificationofMethodsforStacks

SpecificationforMethods（方法的定义）boolStack::empty()const;precondition:None.postcondition:AresultoftrueisreturnediftheStackisempty,otherwisefalseisreturned.Error_codeStack::top(Stack_entry&item)const;precondition:None.postcondition:ThetopofanonemptyStackiscopiedtoitem.AcodeoffailisreturnediftheStackisempty.DeterminethedatamembersoftheStackclass栈顶First,wemuststorethedatainthestackHowtostorethedata?Anarray(acontiguousimplementation)ThearrayhasamaxsizefixedsizeThestackoccupyonlypartofthearrayspaceSecond,howmany?AcounterTheClassSpecification

（类的定义）Wesetupanarraytoholdtheentriesinthestackandacountertoindicatehowmanyentriesthereare.constintmaxstack=10;//smallvaluefortestingclassStack{public:Stack();boolempty()const;Error_codepop();Error_codetop(Stack_entry&item)const;Error_codepush(constStack_entry&item);private:intcount;Stack_entryentry[maxstack];};Pushing,Popping,andOtherMethodsWenotethatthedatamembercountrepresentsthenumberofitemsinaStack.Therefore,thetopofaStackoccupiesentry[count-1],asshowninFigure2.4.

Pushing,Popping,andOtherMethodsError_codeStack::push(constStack_entry&item)/*Pre:None.Post:IftheStackisnotfull,itemisaddedtothetopoftheStack.IftheStackisfull,anError_codeofoverflowisreturnedandtheStackisleftunchanged.*/{Error_codeoutcome=success;if(count>=maxstack) outcome=overflow;elseentry[count++]=item;returnoutcome;}Pushing,Popping,andOtherMethodsError_codeStack::pop()/*Pre:None.Post:IftheStackisnotempty,thetopoftheStackisremoved.IftheStackisempty,anError_codeofunderflowisreturned.*/{Error_codeoutcome=success;if(count==0)outcome=underflow;else--count;returnoutcome;}Pushing,Popping,andOtherMethodsError_codeStack::top(Stack_entry&item)const/*Pre:None.Post:IftheStackisnotempty,thetopoftheStackisreturnedinitem.IftheStackisemptyanError_codeofunderflowisreturned.*/{Error_codeoutcome=success;if(count==0)outcome=underflow;elseitem=entry[count-1];returnoutcome;}Pushing,Popping,andOtherMethodsboolStack::empty()const/*Pre:None.Post:IftheStackisempty,trueisreturned.Otherwisefalseisreturned.*/{booloutcome=true;if(count>0)outcome=false;returnoutcome;}Stack::Stack()/*Pre:None.Post:Thestackisinitializedtobeempty.*/{count=0;}算法的时间复杂度O(1)Encapsulation

（封装）

Noticethatourstackimplementationforcesclientcodetomakeuseofinformationhiding.OurdeclarationofprivatevisibilityforthedatamakesitisimpossibleforaclienttoaccessthedatastoredinaStackexceptbyusingtheofficialmethodspush(),pop(),andtop().OneimportantresultofthisdataprivacyisthataStackcannevercontainillegalorcorrupteddata.EveryStackobjectwillbeinitializedtorepresentalegitimateemptystackandcanonlybemodifiedbytheofficialStackmethods,freeofanydatacorruption.(assuranceofdataintegrity)

WesummarizethisprotectionthatwehavegivenourStackobjectsbysayingthattheyareencapsulated.Ingeneral,dataissaidtobeencapsulatedifitcanonlybeaccessedbyacontrolledsetoffunctions.Application:ADeskCalculator（计算器）ReversePolishCalculator（逆波兰计算器）

InaReversePolishcalculator,theoperands(numbers,usually)areenteredbefore

anoperation(likeaddition,subtraction,multiplication,ordivision)isspecified.(a*(b-c))+

d-->abc-*d+

TheadvantageofareversePolishcalculatoristhatanyexpression,nomatterhowcomplicated,canbespecifiedwithouttheuseofparentheses.（括号）PostfixExpressionInfixExpressionApplication:ADeskCalculatorReversePolishCalculator（逆波兰计算器）

Weshallwrite?todenoteaninstructiontoreadanoperand;+

,-,*,and/representarithmeticoperations;and=isaninstructiontoprintthevaluejustgot.Eg1:wewritea,b,c,anddtodenotenumericalvaluessuchas3.14or-7.Theinstructions?a?b+

=meanreadandstorethenumbersaandb,calculateandstoretheirsum,andthenprintthesum.Eg2:Theinstructions?a?b+

?c?d+

*=requestfournumericaloperands,andtheresultprintedisthevalueof(a+

b)*(c+

d).Eg3:theinstructions?a?b?c-=*?d+

=meanreadthenumbersa,b,c,caculateb-candprintitsvalue,thencalculatea*(b-c),readd,andfinallycalculateandprint(a*(b-c))+

d.依次输入：?1?2+?3*=后，显示计算结果9算法思想：程序从键盘接受命令符如输入的命令为“?”则继续读入一个操作数，由于对该操作数执行的运算符还未知，所以暂时将它存储起来；如输入的是“+-*/”等运算符则此时应将最近保存过的数拿出两个作算术运算，并将运算的中间结果存储起来。由于最近存储的操作数（或是最近存储的中间结果）即是即将拿出来作运算的操作数，也即后存储的先取出来，即满足“后进先出”的原则，因此，应把这些操作数存储在栈中。如输入的命令为“=”将刚才的运算结果即栈顶显示出来。?1?2+?3*=?denoteaninstructiontoreadanoperandandpushitontothestack;+

,-,*,and/representarithmeticoperations;Whenanoperationisperformed,itpopsitsoperandsfromthestackandpushesitsresultbackontothestack.=isaninstructiontoprintthevalue.Application:ADeskCalculatortypedefdoubleStack_entry;#include“Stack.h"intmain()/*Post:Theprogramhasexecutedsimplearithmeticcommandsenteredbytheuser.Uses:TheclassStackandthefunctionsintroduction,instructions,do_command,andget_command.*/{Stackstored_numbers;introduction();instructions();while(do_command(get_command(),stored_numbers));}Theauxiliaryfunctionget_commandobtainsacommandfromtheuser,checkingthatitisvalidandconvertingittolowercasebyusingthestringfunctiontolower()thatisdeclaredinthestandardheaderfilecctype.Application:ADeskCalculatorcharget_command(){charcommand;boolwaiting=true;cout<<"Selectcommandandpress<Enter>:";while(waiting){cin>>command;command=tolower(command);if(command==‘?’

||command=='='||command=='+'||command=='-'||command=='*'||command=='/'||command=='q')waiting=false;else{cout<<"Pleaseenteravalidcommand:"<<endl<<"[?]pushtostack[=]printtop"<<endl<<"[+][-][*][/]arearithmeticoperations"<<endl<<"[Q]uit."<<endl;}}returncommand;}Application:ADeskCalculatorbooldo_command(charcommand,Stack&numbers)/*Pre:Thefirstparameterspecifiesavalidcalculatorcommand.Post:ThecommandspecifiedbythefirstparameterhasbeenappliedtotheStackofnumbersgivenbythesecondparameter.Aresultoftrueisreturnedunlesscommand=='q'.Uses:TheclassStack.*/{doublep,q;switch(command){case'?'://readcout<<"Enterarealnumber:"<<flush;cin>>p;if(numbers.push(p)==overflow)cout<<"Warning:Stackfull,lostnumber"<<endl;break;case'='://print

if(numbers.top(p)==underflow)cout<<"Stackempty"<<endl;elsecout<<p<<endl;break;Application:ADeskCalculatorcase'+':if(numbers.top(p)==underflow)cout<<"Stackempty"<<endl;else{numbers.pop();if(numbers.top(q)==underflow){cout<<"Stackhasjustoneentry"<<endl;numbers.push(p);}else{numbers.pop();if(numbers.push(q+p)==overflow)cout<<"Warning:Stackfull,lostresult"<<endl;}}break;//Addoptionsforfurtherusercommands.Application:ADeskCalculatorcase'q':

cout<<"Calculationfinished.\n";returnfalse;}returntrue;}

Incallingthisfunction,wemustpasstheStackparameterbyreference,becauseitsvaluemightneedtobemodified.Forexample,ifthecommandparameteris+,thenwenormallypoptwovaluesofftheStacknumbersandpushtheirsumbackontoit:ThisshouldcertainlychangetheStack.Thefunctiondo_commandallowsforanadditionalusercommand,q,thatquitstheprogram.进一步思考如果是读入一个由后缀表达式组成的字符串呢？34*51/+如果是一个中缀表达式呢？(3-4)+(5/1)Application:BracketMatching（括号匹配）

Wedevelopaprogramtocheckthatbracketsarecorrectlymatchedinaninputtextfile.Welimitourattentiontothebrackets{,},(,),[,and].Wereadasinglelineofcharactersandignoreallinputotherthanbracketcharacters.

Algorithm:Readthefilecharacterbycharacter.Eachopeningbracket(,[,or{thatisencounteredisconsideredasunmatchedandisstoreduntilamatchingbracketcanbefound.Anyclosingbracket),],or}mustcorrespond,inbracketstyle,tothelastunmatchedopeningbracket,whichshouldnowberetrievedandremovedfromstorage.Finally,attheendoftheprogram,wemustcheckthatnounmatchedopeningbracketsareleftover.Application:BracketMatchingTheprogramneedstoprocessitsinputfilecharacterbycharacter,and,asitworksitswaythroughtheinput,itneedssomewaytorememberanycurrentlyunmatchedbrackets.Thesebracketsmustberetrievedintheexactreverseoftheirinputorder,andthereforeaStackprovidesanattractiveoptionfortheirstorage.Ourprogramneedonlyloopovertheinputcharacters,untileitherabracketingerrorisdetectedortheinputfileends.Wheneverabracketisfound,anappropriateStackoperationisapplied.{3*[A+(b*cd)]}3*A+(b*cd]+53*A+(b*cd)dfg]{3*A+(b*cd)+5Application:BracketMatchingBracketMatchingProgram（括号匹配程序）

#include“Stack.h”intmain()/*Post:Theprogramhasnotifiedtheuserofanybracketmismatchinthestandardinputfile.Uses:TheclassStack.*/{Stackopenings;charsymbol;boolis_matched=true;while(is_matched&&(symbol=cin.get())!='\n'){if(symbol=='{'||symbol=='('||symbol=='[')openings.push(symbol);if(symbol=='}'||symbol==')'||symbol==']'){}

}if(!openings.empty())cout<<"Unmatchedopeningbracket(s)detected."<<endl;}

if(openings.empty()){cout<<"Unmatchedclosingbracket"<<symbol<<"detected."<<endl;is_matched=false;}else{charmatch;openings.top(match);openings.pop();is_matched=(symbol=='}'&&match=='{')||(symbol==')'&&match=='(')||(symbol==']'&&match=='[');if(!is_matched)cout<<"Badmatch"<<match<<symbol<<endl;}

boolis_matched(char*s){Stackopenings;charsymbol;boolis_matched=true;inti=0;while(s[i]!='\0'){if(s[i]=='('||s[i]=='[‘||s[i]==‘{‘) openings.push(s[i]);if(s[i]==')'||s[i]==']‘||s[i]==‘{‘){ if(openings.empty()) returnfalse; else{charmatch;openings.top(match);openings.pop();is_matched=((s[i]==')'&&match=='(')||(s[i]==']'&&match=='[‘)||(s[i]==‘}'&&match==‘{'));If(!is_matched)returnfalse;}}i++;}if(!openings.empty())returnfalse;returntrue;}算法示例voidconvert(intN){Stackmodu;intm;while(N>0) {modu.push(N%8); N=N/8; }while(!modu.empty()){modu.top(m);modu.pop();cout<<m;}}AbstractDataTypesandTheirImplementations

（抽象数据类型及其实现）

GeneralDefinitions

atomictypes:suchasint,float,andchar

structuredtypes：Avalueofastructuredtypehastwoingredients:Itismadeupofcomponentelements,andthereisastructure,asetofrulesforputtingthecomponentstogether.suchasarrays,classes,andpointers.1、Drawingaclearseparationbetweenthelogicalstructureofourdataanditsimplementationincomputermemorywillhelpusindesigningprograms.2、Sequential（有序）contiguous（连续）--asequentiallistinacontiguousimplementation.AbstractDataTypesAbstractStacksThedefinitionofafinitesequenceallowsustodefinealistofitemsofatypeTasafinite

sequenceofelementsofthesetT.Nextwewishtodefineastack.Butthereisnothingregardingthesequenceofitemstodistinguishastackfromalist.Theprimarycharacteristicofastackisthesetofoperations

ormethods

bywhichchangesoraccessescanbemade.AbstractDataTypes

DEFINITION:AstackofelementsoftypeTisafinitesequenceofelementsofT,togetherwiththefollowingoperations:

Createthestack,leavingitempty.TestwhetherthestackisEmpty.

Pushanewentryontothetopofthestack,providedthestackisnotfull.

Poptheentryoffthetopofthestack,providedthestackisnotempty.

RetrievetheTopentryfromthestack,providedthestackisnotempty.Includingastatementoftheseoperationswiththestructuralrulesdefiningafinitesequence,weobtainNotethatthisdefinitionmakesnomentionofthewayinwhichtheabstractdatatypestackistobeimplemented.Inthecomingchapterswewillstudydifferentimplementationsofstacks,andthisnewdefinitionfitsanyoftheseimplementationsequallywell.Thisdefinitionproduceswhatiscalledanabstractdatatype,oftenabbreviatedasADT.Theimportantprincipleisthatthedefinitionofanyabstractdatatypeinvolvestwoparts:Firstisadescriptionofthewayinwhichthecomponentsarerelatedtoeachother,andsecondisastatementoftheoperationsthatcanbeperformedonelementsoftheabstractdatatype.AbstractDataTypesRefinementofDataSpecificationOntheabstractlevelwedecidehowthedataarerelatedtoeachotherandwhatoperationsareneeded,butwedecidenothingconcerninghowthedatawill