算法与数据结构-sjtu3栈和队列

第三章栈和队列第三章栈和队列11、2、队3、优先队4、栈和队列的应1

1、BA限定仅只能在表尾端进 和删除的线性表BA时间有序表：LIFO2、栈的ADT Data初template<classclassAbsStack

AB出A

CBACCBA

AbsStack virtual~AbsStack(){} //析构函数virtualintIsEmpty()const=0; //判栈空吗？virtualintIsFull()const=0; //判栈满吗？virtualvoidMakeEmpty()=0; //将栈清空。virtualvoidPush emType&X0;//virtualvoidPop()=0;//virtual emType&Topconst0;//AbsStack(constAbsStack&){}//冻 1、ABACBADABACBADCBA3210

因为 因为top==-1是栈空标志，所以top指针指示真正的栈顶元素的下12储空间。将原栈的内容移入新栈。stacksize==1、·staticconstintInitStackSize=template<classElemType>classStack:publicAbsStack<ElemType>{ //int //top-int //voidDoubleArrayintMax //

Stack //构造函数初始时构造大小为InitStackSize~StackdeleteArray //voidMakeEmptytop1;};//intIsEmpty()const{returntop==-1;}; intIsFull()const{returntop==MaxSize-1;};//栈满为True,否则为False。 emType&Top()const; voidPush emType&X //将XvoidPop //constStack&operator=(constStack&R1、·template<classStack<ElemType>::Stack():top(-1),MaxSize(InitStackSize)//构造函数空间大小为MaxSizeArray=newElemType[MaxSize];}template<classElemType> emType&Stack<ElemType>::Top()const//对非空栈， Exception(IsEmpty(),”Underflow:SatckisEmpty!”);returnArray[top];}template<classElemType>voidStack<ElemType>::Push(cons emType&Xif(top+1==MaxSize) DoubleArray(2*MaxSize);Array[++top]=X; //新结点放入新的栈顶位置。}templateclassElemType>voidStack<ElemType>::Pop对非空栈,Exception(IsEmpty(),”Stackisunderflow!”);}1、·template<classconstStack<ElemType>&Stack<ElemType>::operator=(constStack<ElemType>&)if(this==&R)returndelete[Array=new //分 单元top=for(intj=0;j<=top;j++)Array[j]=R.Array[j];//逐 结点return}template<classvoidStack<ElemType>::DoubleArray(intMax){ElemType*oldarr=Array;Exception(MaxSize≥Max,“NewsizeistooArray=newfor(intk=0;k<=top;k++)Array[k]= //逐 结点MaxSize=Max;delete[]oldarr;}1、多栈 块顺 空间：栈顶指针指向实际栈顶的下一个单元1、二个栈 块顺 空间：栈顶指针指向实际栈顶的下一个单元。指针相遇时，栈满1、 表示的栈作：top

∧

Element∧∧

Element∧∧1、 表示的栈作：toptemplate<classElemType>classStack:publicAbsStack<ElemType>{ //topStack():top(NULL //构造函数:~StackMakeEmpty //voidMakeEmpty();//intIsEmptyconstreturntopNULL;};//栈空为True,否则为FalseintIsFullconstreturn0 // emType&Top()const; voidPush(cons emType&X); //将X的值进栈。voidPop(); //栈顶结点出栈。constStack&operator=(constStack&R);1、 表示的栈的PushElement ementXX

Element∧∧templatetemplate<classvoidStack<ElemType>::Push(emType&X)top=newListNode<ElemType>(X,}∧∧1、

表示的栈的PushXElement ementX

Element∧∧templatetemplate<classvoidStack<ElemType>::Push(emType&X)top=newListNode<ElemType>(X,}∧∧1、q

表示的栈的Poptemplate<classvoidtemplate<classvoidStack<ElemTypePop //Exception(IsEmpty(),”StackisListNode<ElemType>*q=top;top=top->Next;delete}

Element∧∧∧∧1、template<classvoidtemplate<classvoidStack<ElemTypePop //Exception(IsEmpty(),”StackisListNode<ElemType>*q=top;top=top->Next;delete}Element ementq

Element∧∧∧∧1、 表示的栈的Pop

templatetemplate<classvoidStack<ElemTypePop //Exception(IsEmpty(),”StackisListNode<ElemType>*q=top;top=top->Next;delete}

Element

∧Element∧∧∧1

2、队在表的一端进 队首：进行删除的一端出 进2、队列的

队 队template<class classAbsQueue

AbsQueue(){} //默认构造函数virtual~AbsQueue(){} //析构函数virtualintIsEmpty()const=0;//判队空吗？virtualintIsFull()const=0; //判队满吗？virtualvoidMakeEmpty()=0;//将队清空。virtualvoidEnQueue emType&X0;//virtualvoidDeQueue()= virtual emType&Frontconst0;//AbsQueue(constAbsQueue&){}//冻 2、队2·

210

AA

AA

BACBACBAmaxSize=4frontrear

当A进队时，如仍设队首指front和队尾指针rearfront==和队空标志因此，使front指向真正的队首,rear指向真正队尾的后一单元，是一种解决方案CBA2、CBA

CBCBA

ABCABCCBA因此，使front指向真正的队因此，使front指向真正的队首的前一结点而rear指。和队空标当A进队时，如仍设队首指针front和队尾指针rear指front==

D进队时，队尾指针要指向真正的队尾的后1单，由于此时0号单元已可以用，所rear==CBA2、CBA

CBCBA

CBACBADCBA因此，使front指向真正的队因此，使front指向真正的队首的前一结点而rear指。和队空标当A进队时，如仍设队首指针front和队尾指针rear指front==

当D进队时，队尾指针rear指向真正的队尾，由于0号单元已可以使用，所rear==2、队出队时应先判队是否空：条件出队时应先判队是否空：条件rear==front至最低下标(循环)进队时应先判队是否满：条件((rear+1)%maxSizerear是否会由最高下标跳2、队·基本操作的实现程序:templatetemplate<classvoid emType&x)//值为xifIsFull())DoubleQueue Array[rearx;//Increment //rear1;若为MaxSize，则rear取0}intIsFull()const{return(rear+1)%MaxSize==front;

3DCDCE10

CDCCDCDCE再进队 再进队循环、满再进队循环、不DCE

DCE2、DCE·基本操作进队的实现程序：扩大数组容量，“分期付款式”内存使用法 template<classvoid emType&x)//值为xif(IsFull())DoubleQueue( Array[rear]=Increment(}

EDEDCtemplate<classintIsFull()const{return(rear+1)%MaxSize==front;template<classvoidQueue<ElemType>::DoubleQueue()//重新创建数组单元个数多一倍的新数组 原队列中的结点intNewSize=2*MaxSize;ElemType*old=Array=newfor(intj=0,k=front;k<rear;j++,Increment(k))Array[j]=front=0; //新的队首指针。rear=j;//新的队尾指针。MaxSizeNewSize;deleteold;}

2、队·templatetemplate<classElemType>voidQueue<ElemType>::DeQueue()Exception(IsEmpty(),”Queueisunderflow!”);Increment(front);}intIsEmpty()const{returnfront==

21

ECEFECEF0出队不循 出队后循2、队求队中结点的个数：rear-front+MaxSizefrontABC CDEFGH CDEFGH CDEFGHI、J、CDEFGH 2、队表示的队列：参照下图所示。其中frontrear分别是队首和队尾指针。

∧∧2、队front=rear=队尾结点(队首结点∧∧

∧∧2、队 表示的队列：front、reartemplate<classElemType>classQueue:publicAbsQueue<ElemType>

> //> //Queue():front(NULL),rear(NULL){构造函数~QueueMakeEmpty voidMakeEmpty intIsEmpty()const{returnfront==NULL;intIsFullconstreturn0 总认为为False emType&Front()const;// voidEnQueue(cons emType&X); //将X的值进队。voidDeQueue(); //将队首结点出队。constQueue&operator=(constQueue&R);2、队 表示的队列：进队操作，front、reartemplatetemplate<classvoidQueue<ElemType>::EnQueue(emType&X)if(IsEmpty())front=rear=newListNode<ElemType>(Xelserear=rear->Next=newListNode<ElemType>(X}

∧∧

XX

∧∧1

3、优先队优先权数越小（如本书） 的优先队列：用数3、优先队 的优先队列：用数组：队空：front=rear=0;队满：rear=MaxSize- a.具有优先数为20、15、30、19的结点依次进队之b.具有优b.具有优先数为26、24的结点依次进队后O（n）c.c.具有最高优先数15的结点出队。用最后一个结点覆盖 d.剩余结点中具有最高优先数为19的结点出队之后，用最后一个结点结点覆盖它之后4、栈和队列的应·例如：108 83*a382*a28*a180* //1684=(82*a3+81*a2a14a0＝ 82*a3+81*a2+ // 余0=(8*a3+a2)余 即a1＝ 8*a3+ // 余5=(a3 余 即a2＝2504a325044、栈和队列的应·102例如： =(?0.4×8= (0.3 (0.0114、栈和队列的应·102例如： =(?0.4×8= (0.3 (0.0110.2×8= (0.31 (0.0110014、栈和队列的应·102例如： =(?0.4×8= (0.3 (0.0110.2×8= (0.31 (0.0110010.6×8= (0.314 4、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * >+->) //#为表达式结束标志，即书上的EOL符号如中缀式 3×(7-相应的后缀式 3.7.2.-.-27-273*534、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x=3×(7-2)。解：(↑> */ >+->)#如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2#4、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2#3#4、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2#3#4、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2×#×#4、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2×#×#4、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2(×(×#4、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2(×#3.(×#4、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2(×#3.(×#4、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2(×#3.(×#4、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2-(×#-(×#4、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2-(×#3.-(×#4、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2)-(×#3.-(×#4、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2)-(-(×#、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2)-(-(×#、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2)(×(×#、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2)(×(×#、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2)×#3.7.2.×#4、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式 3×(7-相应的后缀式 3.7.2.-.执行过程：3(7-2)×#×#、栈和队列的应·简单计算器的实现：重点为计算表达式的值；如：x3(7-2)解：(↑ * +->)如中缀式