数据结构教程-第3章-栈和队列

数据结构（C＋＋版）南京中医药大学信息技术学院第3章栈和队列本章的基本内容是：栈栈与递归队列优先级队列双端队列数据结构（C＋＋版）南京中医药大学信息技术学院3.1栈3.1.1栈的定义空栈：不含任何数据元素的栈。（a1,a2,……,an）栈：限定仅在表尾进行插入和删除操作的线性表。栈顶栈底允许插入和删除的一端称为栈顶，另一端称为栈底。数据结构（C＋＋版）南京中医药大学信息技术学院a1a2a3入栈出栈栈底栈顶插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈顶栈的示意图栈的操作特性：后进先出3.1.1栈的定义3.1栈数据结构（C＋＋版）南京中医药大学信息技术学院栈的操作特性：后进先出a1a2a3入栈出栈栈底插入：入栈、进栈、压栈删除：出栈、弹栈栈顶栈的示意图3.1.1栈的定义3.1栈数据结构（C＋＋版）南京中医药大学信息技术学院例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？栈底栈顶ab栈顶c栈顶情况1：3.1.1栈的定义3.1栈数据结构（C＋＋版）南京中医药大学信息技术学院栈底栈顶ab栈顶c栈顶出栈序列：c出栈序列：c、b出栈序列：c、b、a例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？情况1：3.1.1栈的定义3.1栈数据结构（C＋＋版）南京中医药大学信息技术学院栈底栈顶ab栈顶出栈序列：b情况2：例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？3.1.1栈的定义3.1栈数据结构（C＋＋版）南京中医药大学信息技术学院栈底a出栈序列：b出栈序列：b、c出栈序列：b、c、ac栈顶栈顶注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？情况2：3.1.1栈的定义3.1栈数据结构（C＋＋版）南京中医药大学信息技术学院constintmaxSize=50enumbool{false,true};templateclassTclassStack{public:Stack(){};virtualvoidPush(constT&x)=0;virtualboolPop(T&x)=0;virtualboolgetTop(T&x)const=0;virtualboolIsEmpty()const=0;virtualboolIsFull()const=0;virtualintgetSize()const=0;};3.1.1栈的定义栈的类定义3.1栈数据结构（C＋＋版）南京中医药大学信息技术学院3.1.2顺序栈顺序栈——栈的顺序存储结构如何改造数组实现栈的顺序存储？012345678a1确定用数组的哪一端表示栈底。附设指针top指示栈顶元素在数组中的位置。top3.1栈数据结构（C＋＋版）南京中医药大学信息技术学院出栈：top减1进栈：top加1栈空：top=-1012345678a1topa2topa3top栈满：top=MAX_SIZE3.1栈3.1.2顺序栈数据结构（C＋＋版）南京中医药大学信息技术学院顺序栈类定义templateclassTclassSeqStack:publicStackT{public:SeqStack(intsz=50);~SeqStack(){delete[]elements;}voidPush(constT&x);boolPop(T&x);boolgetTop(T&x);boolIsEmpty()const{return(top==-1)?true:false;}boolIsFull()const{return(top==maxSize-1)?true:false;}intgetSize()const{returntop+1;}voidMakeEmpty(){top=-1;}private:T*elements;inttop,maxSize;voidoverflowProcess();};3.1栈数据结构（C＋＋版）南京中医药大学信息技术学院顺序栈的实现——构造函数templateclassTSeqStackT::SeqStack(intsz):top(-1),maxSize(sz){elements=newT[maxSize];assert(elements!=NULL);//断言：动态存储分配成功与否}注意断言的使用！3.1栈3.1.2顺序栈数据结构（C＋＋版）南京中医药大学信息技术学院顺序栈的实现——入栈templateclassTvoidSeqStack::Push(constT&x){if(IsFull()==true)overflowProcess();elements[++top]=x;}时间复杂度？3.1栈3.1.2顺序栈具体实现见P90数据结构（C＋＋版）南京中医药大学信息技术学院顺序栈的实现——出栈templateclassTboolSeqStack::Pop(T&x){if(IsEmpty()==true)returnfalse;x=elements[top--];returntrue;}时间复杂度？3.1栈3.1.2顺序栈数据结构（C＋＋版）南京中医药大学信息技术学院两栈共享空间解决方案1：直接解决：为每个栈开辟一个数组空间。解决方案2：顺序栈单向延伸——使用一个数组来存储两个栈在一个程序中需要同时使用具有相同数据类型的两个栈，如何顺序存储这两个栈？会出现什么问题？如何解决？3.1栈3.1.2顺序栈数据结构（C＋＋版）南京中医药大学信息技术学院两栈共享空间：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。两栈共享空间3.1栈3.1.2顺序栈数据结构（C＋＋版）南京中医药大学信息技术学院栈0的底固定在下标为0的一端；栈1的底固定在下标为maxSize-1的一端。t[0]和t[1]分别为栈0和栈1的栈顶指针；b[0]和b[1]分别为栈0和栈1的栈底；maxSize为整个数组空间的大小；t[0]012……maxSize-1t[1]b[0]b[1]3.1栈两栈共享空间3.1.2顺序栈Vector数据结构（C＋＋版）南京中医药大学信息技术学院t[0]=b[0]什么时候栈0为空？012……maxSize-1t[1]t[0]3.1栈两栈共享空间3.1.2顺序栈Vectorb[0]b[1]数据结构（C＋＋版）南京中医药大学信息技术学院t[0]=b[0]什么时候栈0为空？t[0]012……maxSize-1什么时候栈1为空？b[1]t[1]=b[1]3.1栈两栈共享空间3.1.2顺序栈Vectorb[0]t[1]数据结构（C＋＋版）南京中医药大学信息技术学院t[0]=b[0]什么时候栈0为空？t[0]012……maxSize-1t[1]什么时候栈1为空？t[1]=b[1]什么时候栈满？t[1]=t[0]+13.1栈两栈共享空间3.1.2顺序栈Vectorb[0]b[1]数据结构（C＋＋版）南京中医药大学信息技术学院boolPush(DualStack&DS,Tx,intd){//在双栈中插入元素x，d=0，插在栈0中，否则，插在栈1中if(DS.t[0]+1==DS.t[1])returnfalse;if(d==0)DS.t[0]++;elseDS.t[1]--;DS.Vector[DS.t[i]]=x;returntrue;};两栈共享空间的实现——入栈3.1栈3.1.2顺序栈数据结构（C＋＋版）南京中医药大学信息技术学院两栈共享空间的实现——退栈3.1栈3.1.2顺序栈boolPop(DualStack&DS,Tx,intd){//从双栈中推出栈顶元素，d=0，从栈0中退，否则，从栈1中退if(DS.t[i]==DS.b[i])returnfalse;x=DS.Vector[DS.t[i]];if(d==0)DS.t[0]--;elseDS.t[1]++;returntrue;};数据结构（C＋＋版）南京中医药大学信息技术学院3.1.3链式栈链栈：栈的链接存储结构firsta1a2an∧ai链栈需要加头结点吗？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将链头作为栈顶，方便操作。链栈不需要附设头结点。3.1栈数据结构（C＋＋版）南京中医药大学信息技术学院栈顶栈底链栈：栈的链接存储结构topanan-1a1∧firsta1a2an∧ai两种示意图在内存中对应同一种状态topa1an-1an∧栈顶栈底3.1栈3.1.3链式栈数据结构（C＋＋版）南京中医药大学信息技术学院链栈的类定义templateclassTclassLinkedStack:publicStackT{public:LinkedStack():top(NULL){}~LinkedStack(){makeEmpty();}voidPush(constT&x);boolPop(T&x);boolgetTop(T&x)const;boolIsEmpty()const{return(top==NULL)?true:false;}intgetSize()const;voidMakeEmpty();private:LinkNodeT*top;};3.1栈数据结构（C＋＋版）南京中医药大学信息技术学院算法描述：templateclassTvoidLinkedStack::Push(constT&x){top=newLinkNodeT(x,top);assert(top!=NULL);}topanan-1a1∧链栈的实现——入栈xtop3.1栈3.1.3链式栈数据结构（C＋＋版）南京中医药大学信息技术学院算法描述：templateclassTboolLinkedStack::Pop(constT&x){if(IsEmpty==true)returnfalse;LinkNodeT*p=top;top=top-link;x=p-data;deletep;returntrue;}链栈的实现——退栈topanan-1a1∧topptop++可以吗？3.1栈3.1.3链式栈数据结构（C＋＋版）南京中医药大学信息技术学院顺序栈和链栈的比较时间性能：相同，都是常数时间O(1)。空间性能：顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。3.1栈数据结构（C＋＋版）南京中医药大学信息技术学院3.2栈与递归3.2.1递归的概念子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。递归的基本思想问题分解：把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。递归的定义数据结构（C＋＋版）南京中医药大学信息技术学院递归的要素⑴递归边界条件：确定递归到何时终止，也称为递归出口；⑵递归模式：大问题是如何分解为小问题的，也称为递归体。3.2栈与递归3.2.1递归的概念数据结构（C＋＋版）南京中医药大学信息技术学院以下3中情况需要用到递归的方法⑴定义是递归的；⑵数据结构是递归的；⑶问题的解法是递归的。3.2栈与递归3.2.1递归的概念数据结构（C＋＋版）南京中医药大学信息技术学院例1阶乘函数递归算法intfact(intn){if(n==0)return1;elsereturnn*fact(n-1);}-*=时当时当)!1(1!n≥1n＝1nnn3.2栈与递归数据结构（C＋＋版）南京中医药大学信息技术学院求解阶乘n!的过程计算fact(4)计算4*fact(3)计算3*fact(