数据结构精品课程PPT5

MainIndexContents11MainIndexContentsStacksStackExamplesPushing/PoppingaStackClassStack(vector/miniVector)UsingaStacktoCreateaHex#UncouplingStackClassStack(array)ClassStack(LinkedList)RecursivecodeRPNInfixNotationLecture5–StacksMainIndexContents2StacksAstackisasequenceofitemsthatareaccessibleatonlyoneendofthesequence.MainIndexContents33MainIndexContentsFurtherStackExamplesMainIndexContents4Pushing/PoppingaStackBecauseapopremovestheitemlastaddedtothestack,wesaythatastackhasLIFO(last-in/first-out)ordering.MainIndexContents5StackImplementationtemplatetypenameTclassminiStack{public:miniStack();voidpush(constT&item);voidpop();T&top();constT&top()const;boolempty()const;intsize()const;private:vectorTstackVector;};MainIndexContents6StackImplementationtemplatetypenameTminiStackT::miniStack(){}templatetypenameTvoidminiStackT::push(constT&item){stackVector.push_back(item);}templatetypenameTvoidminiStackT::pop(){if(empty())throwunderflowError(miniStackpop():stackempty);stackVector.pop_back();}MainIndexContents7StackImplementation(vector)templatetypenameTT&miniStackT::top(){if(empty())throwunderflowError(miniStacktop():stackempty);returnstackVector.back();}templatetypenameTboolminiStackT::empty()const{returnstackVector.size()==0;}templatetypenameTintminiStackT::size()const{returnstackVector.size();}MainIndexContents88MainIndexContentsUsingaStacktoCreateaHexNumber'1''A''F''A''F''F'431%16=15431/16=2626%16=1026/16=11%16=11/16=0PushDigitCharacters'1''A''F''A''F''F'Pop'1'numStr=1PopDigitCharactersPop'A'numStr=1APop'F'numStr=1AFMainIndexContents9UsingaStacktoCreateaHexNumberStringmultibaseOutput(intnum,intb){stringdigitChar=“0123456789ABCDEF”,numStr=“”;stackcharstk;do{stk.push(digitChar[num%b]);num/=b;}while(num!=0);while(!stk.empty()){numstr+=stk.top();stk.pop();}returnnumStr;}MainIndexContents1010MainIndexContentsUncouplingStackElementsTrainBeforeUncouplingEABCDEMainIndexContents1111MainIndexContentsUncouplingStackElementsUncoupleE.MovetosidetrackABCDEMainIndexContents1212MainIndexContentsUncouplingStackElementsUncoupleD.MovetosidetrackABCDEMainIndexContents1313MainIndexContentsUncouplingStackElementsUncoupleCMoveasideABCDEMainIndexContents1414MainIndexContentsUncouplingStackElementsAttachDtoendoftrainABDCEMainIndexContents1515MainIndexContentsUncouplingStackElementsAttachEtoendoftrainABDECMainIndexContents16UncoupleAlgorithmTemplatetypenameBooluncouple(stackT&s,constT&target){stackTtmpStk;boolfoundTarget=true;while(!s.empty()&&s.top()!=target){tmpstk.push(s.top());s.pop();}if(!s.empty())s.pop();elsefoundTarget=false;while(!tmpStk.empty()){s.push(tmpStk.top());tmpStk.pop();}returnfoundTarget;}MainIndexContents1717MainIndexContentsCLASSstackConstructorstackstack();CreateanemptystackCLASSstackOperationsstackboolempty();constCheckwhetherthestackisempty.Returntrueifitisemptyandfalseotherwise.MainIndexContents1818MainIndexContentsCLASSstackOperationsstackvoidpop();Removetheitemfromthetopofthestack.Precondition:Thestackisnotempty.Postcondition:Eitherthestackisemptyorthestackhasanewtopmostitemfromapreviouspush.voidpush(constT&item);Inserttheargumentitematthetopofthestack.Postcondition:Thestackhasanewitematthetop.MainIndexContents1919MainIndexContentsCLASSstackOperationsstackintsize()const;Returnthenumberofitemsonthestack.T&top()const;Returnareferencetothevalueoftheitematthetopofthestack.Precondition:Thestackisnotempty.constT&top()const;Constantversionoftop().MainIndexContents20StackImplementation(array)constMAXSTACKSIZE=50;templatetypenameTclassbStack//有限栈{public:bStack();voidpush(constT&item);voidpop();T&top();constT&top()const;boolempty()const;boolfull()const;intsize()const;private:TstackList[MAXSTACKSIZE];inttopIndex;};76543210-1MainIndexContents21StackImplementation(array)templatetypenameTbStackT::bStack(){topIndex=-1;}templatetypenameTvoidbStackT::push(constT&item){if(full())throwunderflowError(miniStacktop():stackempty);//exit(1);topIndex++;stackList[topIndex]=item;}templatetypenameTvoidbStackT::pop(){if(empty())throwunderflowError(miniStacktop():stackempty);topIndex--;}MainIndexContents22StackImplementation(array)templatetypenameTT&bStackT::top(){if(empty())throwunderflowError(miniStacktop():stackempty);returnstackList[topIndex];}templatetypenameTconstT&bStackT::top()const{if(empty())throwunderflowError(miniStacktop():stackempty);returnstackList[topIndex];}templatetypenameTboolbStackT::empty()const{returntopIndex==-1;}MainIndexContents23StackImplementation(array)templatetypenameTboolbStackT::full()const{returntopIndex=MAXSTACKSIZE-1;}templatetypenameTintbStackT::size()const{returntopIndex+1;}MainIndexContents24StackImplementation(LinkedList)#include“d_node.h”templatetypenameTclassLinkedStack{public:LinkedStack();voidpush(constT&item);voidpop();T&top();constT&top()const;boolempty()const;//boolfull()const;intsize()const;private:nodeT*Header;intcount;};HeaderMainIndexContents25StackImplementation(LinkedList)templatetypenameTLinkedStackT::Lin