第三章栈队列和递归

第三章栈队列和递归第1页，课件共73页，创作于2023年2月特殊线性表

栈队列

串⑴栈的定义⑵操作特性⑶ADT定义⑴队列定义⑵操作特性⑶ADT定义⑴串的定义⑵基本概念⑶ADT定义顺序栈链栈循环队列链队列顺序存储链接存储逻辑结构存储结构逻辑结构逻辑结构存储结构存储结构比较模式匹配比较比较⑴基本操作的实现⑵时间复杂度⑴基本操作的实现⑵时间复杂度第2页，课件共73页，创作于2023年2月3.1栈（Stack）

3.2队列

（Queue）１.逻辑结构２.存储结构与实现３.应用实例１.逻辑结构２.存储结构与实现３.应用实例第3页，课件共73页，创作于2023年2月３.1栈1、栈的逻辑结构空栈：不含任何数据元素的栈。

（a1,a2,……,an）栈：限定仅在一端进行插入和删除操作的线性表。栈顶栈底允许插入和删除的一端称为栈顶，另一端称为栈底。数据元素之间的逻辑关系：一对一。第4页，课件共73页，创作于2023年2月注：栈的运算规则只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。入栈：插入元素到栈顶（即表尾）的操作。出栈：从栈顶（即表尾）删除最后一个元素的操作。问：栈与一般线性表有什么不同？一般线性表（堆）栈逻辑结构：一对一逻辑结构：一对一存储结构：顺序表、链表存储结构：顺序栈、链栈运算规则：随机存取运算规则：后进先出(LIFO)

入栈操作演示出栈操作演示第5页，课件共73页，创作于2023年2月a1a2a3入栈栈底栈顶插入：入栈、进栈、压栈栈顶栈顶入栈的操作示图：栈顶第6页，课件共73页，创作于2023年2月a1a2a3栈底栈顶删除：出栈、弹栈栈顶栈顶出栈的操作示图：栈顶栈的操作特性：后进先出出栈第7页，课件共73页，创作于2023年2月思考题１：一个栈的输入序列为123，若在入栈的过程中允许出栈，且每个元素只允许进一次栈，则可能得到的出栈序列有哪些？答：可以通过穷举所有可能性来求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合计有5种可能性。第8页，课件共73页，创作于2023年2月思考题２：设依次进入一个栈的元素序列为c，a，b，d，则可得到出栈的元素序列是：

Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bA、D可以（B、C不行）。讨论：有无通用的判别原则？有。若输入序列i，j，k，则不存在输出序例k、i、j;答：第9页，课件共73页，创作于2023年2月2、栈的存储结构顺序栈、链式栈（１）顺序栈——栈的顺序存储结构(重点)如何改造数组实现栈的顺序存储？

012345678a1确定用数组的哪一端表示栈底。附设指针top指示栈顶元素在数组中的位置。

topS第10页，课件共73页，创作于2023年2月进栈核心语句：top++;S[top]=a1;栈空：top==-1

012345678topa1topa2top进栈的操作步骤如何？第11页，课件共73页，创作于2023年2月

012345678a1a2栈满：top==MAX_SIZE-1栈满的如何判断？topa3a4a5a6a7a8a9第12页，课件共73页，创作于2023年2月动态栈类的定义：template<classtype>//定义模板类DSeqStackclassDSeqStack{public:

DSeqStack(intsize);//构造函数，栈的初始化

~DSeqStack(){delete[]S;}//析构函数

voidPush(consttype&item);//将元素item入栈typePop();//将栈顶元素弹出typeGetTop(); //取栈顶元素（并不删除）

intEmpty(){returntop==-1;}

//判断栈是否为空

intfull()const{returntop==MaxSize-1;}//为满则返回1，否则返回0

voidclear(){top=-1;}//清空栈private:

type*S;//存放栈元素的数组起始地址

inttop;//栈顶指针，指示栈顶元素在数组中的下标

intMaxSize;//栈最大可容纳元素个数};第13页，课件共73页，创作于2023年2月顺序栈的构造函数算法实现template<classtype>DSeqStack<type>::DSeqStack(intsize):top(-1),MaxSize(size){//建立一个最大尺寸为size的空栈

S=newtype[MaxSize];//创建存储栈的数组 if(S==NULL)//分配不成功 {cerr<<"动态存储失败！"<<endl; exit(1);//stdlib.h }}操作接口：

template<classtype>DSeqStack<type>::DSeqStack(intsize);算法实现：第14页，课件共73页，创作于2023年2月顺序栈的入栈操作算法实现template<classtype>voidDSeqStack<type>::Push(consttype&item){if(top==MaxSize-1)throw"栈满！";

top++;//栈未满，则入栈

S[top]=item;}操作接口：

template<classtype>voidDSeqStack<type>::Push(consttype&item)算法实现：时间复杂度？O(1)第15页，课件共73页，创作于2023年2月出栈核心语句：Item=S[top];top--;边界条件栈空：top==-1;

012345678topa1topa2top出栈的操作步骤如何？第16页，课件共73页，创作于2023年2月顺序栈的出栈操作算法实现template<classtype>typeDSeqStack<type>::Pop(){typeitem;if(top==-1)throw"栈空！";

item=S[top--];//等价于item=S[top];top--;returnitem;}操作接口：

template<classtype>typeDSeqStack<type>::Pop();算法实现：时间复杂度？O(1)第17页，课件共73页，创作于2023年2月其它类型栈举例：如两栈共享空间

解决方案1：直接解决：为每个栈开辟一个数组空间。

解决方案2：

使用一个数组来存储两个栈。使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。在一个程序中需要同时使用具有相同数据类型的两个栈，如何顺序存储这两个栈？会出现什么问题？如何解决？第18页，课件共73页，创作于2023年2月栈1的栈底:固定靠下标为0的这一端；栈2的栈底:固定靠下标为MaxSize-1的这一端。top1和top2分别为栈1和栈2的栈顶指针；MaxSize:整个数组空间的大小（图中用S表示）；a1

a2…aitop1012…

…S-1top2bj

……b2

b1栈1底栈2底Ｓ两栈共享空间栈顶与栈底如何设置？第19页，课件共73页，创作于2023年2月栈1为空条件：top1==-1栈2为空条件：top2==MaxSize什么时候两栈为空？012…

…S-1top2top1第20页，课件共73页，创作于2023年2月a1

a2……aitop1012…

…S-1top2bj

……b2

b1栈满条件为：top2=top1+1什么时候栈为满？第21页，课件共73页，创作于2023年2月（２）链式栈——栈的链式存储结构如何改造链表实现栈的链接存储？链栈需要加头结点吗？将哪一端作为栈顶？注：链栈不需要附设头结点。(栈底)(栈顶)topa3a2a4a1^第22页，课件共73页，创作于2023年2月链栈类的定义：template<classtype>classLinkStack;//声明template<classtype>classNode{friendclassLinkStack<type>;private:

typedata;Node<type>*next;//此处<T>也可以省略};template<classtype>classLinkStack{public:LinkStack();//构造函数，置空链栈~LinkStack();//析构函数，释放链栈中各结点的存储空间voidPush(typeitem);//将元素item入栈typePop();//将栈顶元素出栈typeGetTop();//取栈顶元素（并不删除）boolEmpty();//判断链栈是否为空栈private:

Node<type>*top;//栈顶指针即链栈的头指针};第23页，课件共73页，创作于2023年2月链栈的构造函数算法实现template<classtype>LinkStack<type>::LinkStack(){

top=NULL;//初始化空栈}操作接口：

template<classtype>LinkStack<type>::LinkStack();算法实现：第24页，课件共73页，创作于2023年2月算法实现：template<classtype>voidinkStack<type>::Push(typex){

Node<type>*s;s=newNode<type>;

s->data=x;s->next=top;

top=s;}topanan-1a1∧链栈的入栈算法实现xstop操作接口：template<classtype>voidLinkStack<type>::Push(typex)；为什么没有判断栈满？第25页，课件共73页，创作于2023年2月算法实现：template<classtype>typeLinkStack<type>::Pop(){Node<type>*p;typex;if(top==NULL)throw“栈空";

x=top->data;p=top;

top=top->next;

deletep;returnx;}链栈的出栈算法实现：操作接口：template<classT>TLinkStack<T>::Pop();topanan-1a1∧topp

top++可以吗？第26页，课件共73页，创作于2023年2月顺序栈和链栈的比较时间性能：相同，都是常数时间O(1)。空间性能：顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。

总之，采用顺序栈存储方式，可使多个栈共享空间；当栈中元素个数变化较大，且存在多个栈的情况下，链栈是栈的首选存储方式。第27页，课件共73页，创作于2023年2月调用函数或子程序非它莫属；递归运算的有力工具；用于保护现场和恢复现场；简化了程序设计的问题；其它应用：如括号匹配问题、表达式计算问题等。答：3、栈的应用举例为什么要设计栈？它有什么独特用途？第28页，课件共73页，创作于2023年2月数制转换（十转八进制）

设计思路：用栈暂存低位值算法分析：NNdiv8Nmod87492911101栈的应用实例１：如：(74)10=(112)8第29页，课件共73页，创作于2023年2月voidconversion(){//对于输入的任意一个非负十进制整数，//打印输出与其等值的八进制数；

SeqStack<int>s1(10); intN,n;inte;

cout<<"请输入一十进制数："<<endl; cin>>N;

n=N; while(n){ s1.Push(n%８); n=n/８; }

while(!s1.Empty()){ e=s1.Pop(); cout<<e; }cout<<endl;}第30页，课件共73页，创作于2023年2月3.1栈（Stack）

3.2队列

（Queue）１.逻辑结构２.存储结构与实现３.应用实例１.逻辑结构２.存储结构与实现第31页，课件共73页，创作于2023年2月３.2队列1、队列的逻辑结构空队：不含任何数据元素的队列。

（a1,a2,……,an）队列：只允许在一端进行插入操作，而在另一端进行删除操作的线性表。。队尾队头允许插入的一端称为队尾，另一端允许删除的称为队头。数据元素之间的逻辑关系：一对一。第32页，课件共73页，创作于2023年2月注：队列的运算规则只能在队尾进行插入运算，在队头进行删除运算;且访问结点时依照先进先出（FIFO）或后进后出（LILO）的原则。入队：插入元素到队列的队尾的操作。出队：从队头删除一个元素的操作。问：队列与一般线性表有什么不同？一般线性表队列逻辑结构：一对一逻辑结构：一对一存储结构：顺序表、链表存储结构：顺序队、链队运算规则：随机存取运算规则：先进先出(FIFO)

第33页，课件共73页，创作于2023年2月队列的操作特性：先进先出a1a2a3入队队尾队头出队队头入队出队操作示意图:队尾队尾队尾第34页，课件共73页，创作于2023年2月2、队列的存储结构与实现顺序队列、链式队列（１）顺序队列——队列的顺序存储结构(重点)如何改造数组实现队列的顺序存储？

012345678a1确定用数组如何表示队头、队尾。附设指示器rear指示队尾元素（在数组中最后一个元素的位置），指示器front指示队头（队头元素所在位置的前一位置）。

rearSfront第35页，课件共73页，创作于2023年2月01234入队出队实例1：a1a2a3a4依次入队a1a2a3a4rearrearrearrear入队操作时间性能为O(1)front第36页，课件共73页，创作于2023年2月实例2：a1a2依次出队01234入队出队a1a2a3a4rearfrontfrontfront出队操作时间性能为O(1)队列的移动有什么特点？整个队列向数组下标较大方向移动单向移动性第37页，课件共73页，创作于2023年2月假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做假溢出。继续入队会出现什么情况？01234入队出队a3a4rearfronta5rear第38页，课件共73页，创作于2023年2月循环队列：将存储队列的数组头尾相接。如何解决假溢出？01234入队出队a3a4fronta5rearreara6第39页，课件共73页，创作于2023年2月a3a2a10123N-1rearfront循环队列（臆造）顺序队列a3a2a1frontrear0123..N-1新问题：在循环队列中，空队特征是front==rear；队满时也会有front==rear；判决条件将出现二义性！解决方案有三：①加设标志位，让删除动作使其为1,插入动作使其为0,则可识别当前front==rear②使用一个计数器记录队列中元素个数（即队列长度）；③人为浪费一个单元，令队满特征为front==(rear+1)%N；第40页，课件共73页，创作于2023年2月队空条件:front==rear

(初始化时：front=rear)队满条件：front==(rear+1)%N(N=maxsize)队列长度：L=（N＋rear－front）%NJ2J3

J1J4

J5frontrear问2：在具有n个单元的循环队列中，队满时共有多少个元素？

n-1个5

问1：左图中队列长度L=？第41页，课件共73页，创作于2023年2月例1：一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?front

J5rear解：由图可知，初始状态,队头和队尾指针的初态分别为front=0和rear=5。删除4个元素后(front+4)%6=4；再插入4个元素后，r=(rear+4)%6=(5+4)%6=3

frontfrontfrontfrontJ1J2

J5rearfrontrearrearrearrear

J6

J7

J8

J9J3J4第42页，课件共73页，创作于2023年2月动态循环队列类的定义：（重点）//DCirQueue.h#ifndefDCirQueue_H#defineDCirQueue_Htemplate<classT>//定义模板类DCirQueueclassDCirQueue{public:

DCirQueue(intsize=10);//构造函数，置空队~DCirQueue(){delete[]queue;};//析构函数

voidEnQueue(Tx);//将元素x入队TDeQueue();//将队头元素出队TGetQueue();//取队头元素（并不删除）boolIsEmpty();//判断队列是否为空

intIsfull()const{return(rear+1)%maxsize==front;} //队列满则返回1，否则返回0private:

T*queue;//存放队列元素的数组intfront,rear;//队头和队尾指针，分别指向队头元素的前一个位置和队尾元素的位置

intmaxsize;//队列最大可容纳元素个数为maxsize-1};#endif第43页，课件共73页，创作于2023年2月循环队列的构造函数算法实现template<classT>DCirQueue<T>::DCirQueue(intsize):front(0),rear(0),maxsize(size){

queue=newT[maxsize]; if(queue==NULL) throw"动态分配失败!";}操作接口：

template<classT>DCirQueue<T>::DCirQueue(intsize);算法实现：01234rearfront第44页，课件共73页，创作于2023年2月循环队列的入队算法实现template<classT>voidDCirQueue<T>::EnQueue(Tx){if((rear+1)%maxsize==front)throw“队满";

rear=(rear+1)%maxsize;

//队尾指针在循环意义下加1queue[rear]=x;//在队尾处插入元素}操作接口：

template<classT>voidDCirQueue<T>::EnQueue(Tx)算法实现：01234rearfrontreara1第45页，课件共73页，创作于2023年2月循环队列的出队算法实现template<classT>TDCirQueue<T>::DeQueue(){if(rear==front)throw"下溢";

front=(front+1)%maxsize;

//队头指针在循环意义下加1returnqueue[front];//读取并返回出队前的队头元素，注意队头指针}操作接口：

template<classT>TDCirQueue<T>::DeQueue()算法实现：a101234入队a4a5a6出队frontrearfronta3第46页，课件共73页，创作于2023年2月循环队列的读队头元素算法实现template<classT>TDCirQueue<T>::GetQueue(){inti;if(rear==front)throw“队空!";

i=(front+1)%maxsize;

//注意不要给队头指针赋值returnqueue[i];}操作接口：

template<classT>TDCirQueue<T>::GetQueue()算法实现：a101234a4a5a6出队frontreara3i入队第47页，课件共73页，创作于2023年2月（2）队列的链接存储结构及实现

链队列：队列的链接存储结构队头指针即为链表的头指针；常用不带头结点链表结构。a1a2an∧如何改造单链表实现队列的链接存储？rearfront第48页，课件共73页，创作于2023年2月front==NULL;front==rear;空链队列如何表示？rearfrontNULLNULL链队列满如何表示？无需考虑满的情况。第49页，课件共73页，创作于2023年2月链式队列类的定义：template<classT>structNode{Tdata;Node<T>*next;//此处<T>也可以省略};template<classT>classLinkQueue{public:LinkQueue();//构造函数，初始化一个空的链队列~LinkQueue();//析构函数，释放链队中各结点的存储空间voidEnQueue(Tx);//将元素x入队TDeQueue();//将队头元素出队TGetQueue();//取链队列的队头元素boolEmpty();//判断链队列是否为空private:

Node<T>*front,*rear;

//队头和队尾指针，分别指向头结点和终端结点};第50页，课件共73页，创作于2023年2月链队的构造函数算法实现template<classT>LinkQueue<T>::LinkQueue(){

front=rear=NULL;}操作接口：

template<classT>LinkQueue<T>::LinkQueue()；算法实现：第51页，课件共73页，创作于2023年2月

xs链队列的实现——入队fronta1an∧rear∧rearfrontxs∧rearrear队不空核心算法描述：Node<T>*s=newNode<T>;s->data=x;s->next=NULL;rear->next=s;rear=s;操作接口：

template<classT>voidLinkQueue<T>::EnQueue(Tx)NULLfront队空时核心算法描述：Node<T>*s=newNode<T>;s->data=x;s->next=NULL;front=rear=s;第52页，课件共73页，创作于2023年2月template<classT>voidLinkQueue<T>::EnQueue(Tx){ Node<T>*s;s=newNode<T>;s->data=x;//申请一个数据域为x的结点ss->next=NULL; if(front==NULL)//空队列，新结点既是队头，又是队尾 {front=rear=s; } else

{rear->next=s;//将结点s插入到队尾rear=s;}}算法实现：第53页，课件共73页，创作于2023年2月链队列的实现——出队操作接口：template<classT>TLinkQueue<T>::DeQueue()fronta2an∧rearNode<T>*p=front;x=p->data;Front=NULL;rear=front;deletep;pa2∧rear队列不空时算法描述：Node<T>*p=front;x=p->data;front=front->next;deletep;队列只有一个元素时?a1frontfrontP第54页，课件共73页，创作于2023年2月链队的出队操作算法实现template<classT>TLinkQueue<T>::DeQueue(){ Node<T>*p;intx;if(front==NULL)throw“队空";

p=front; x=p->data;//暂存队头元素

front=front->next;//将队头元素所在结点摘链if(front==NULL)rear=front;

//判断出队前队列长度是否为1

deletep;returnx;}操作接口：template<classT>TLinkQueue<T>::DeQueue()；算法实现：第55页，课件共73页，创作于2023年2月链队的获得队首元素操作算法实现template<classT>TLinkQueue<T>::GetQueue(){if(front!=NULL) returnfront->data;}操作接口：template<classT>TLinkQueue<T>::GetQueue()算法实现：第56页，课件共73页，创作于2023年2月队列的其它链接存储结构用带头结点的单链表实现队列的链接存储？队头指针即为链表的头指针，指向头结点。a1a2an∧rearfront空链队列front∧rear第57页，课件共73页，创作于2023年2月xsfronta1an∧rear∧rearfrontxs∧∧rearrear核心算法描述：Node<T>*s=front->next;s->data=x;s->next=NULL;rear->next=s;rear=s;队列为空时如何入队如何操作？用带头结点的单链表如何实现队列的入队操作？第58页，课件共73页，创作于2023年2月fronta1an∧rearfronta1p∧∧rearrear核心算法描述：Node<T>*p=front->next;x=p->data;front->next=p->next;deletep;队列中仅有一个元素时出队如何操作？用带头结点的单链表如何实现队列的出队操作？a2p核心算法描述：rear=front;第59页，课件共73页，创作于2023年2月练习1：数组Ｑ[n]用来表示一个循环队列，f为当前队列首元素的前一位置，r为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素个数的公式为:（Ａ）r－f（Ｂ）（n＋f－r）%n（Ｃ）n＋r－f（Ｄ）（n＋r－f）%n4种公式哪种合理？当r≥f时（A）合理；当r<f时（C）合理；分析：综合2种情况，以（D）的表达最为合理练习2：在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是先

，后

。

移动队首指针取出元素√第60页，课件共73页，创作于2023年2月离散事件的模拟（模拟事件发生的先后顺序）；操作系统中多道作业的处理（一个CPU执行多个作业）；3.简化程序设计。答：为什么要设计队列？它有什么独特用途？第61页，课件共73页，创作于2023年2月小结线性表、栈与队的异同点相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。不同点：①运算规则不同，线性表为