数据结构第三章-栈与队列(00001)课件.ppt

《数据结构第三章-栈与队列(00001)课件.ppt》由会员分享，可在线阅读，更多相关《数据结构第三章-栈与队列(00001)课件.ppt（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章 栈与队列数据结构本章主要内容l栈的定义与基本运算l栈的顺序存储和链式存储l队列的定义与基本运算l队列的线性存储和链式存储1、栈的定义与基本运算栈（Stack）在生活中非常常见，例如洗干净的盘子总是逐个往上叠放在已经洗好的盘子上面，而用的时候我们必须从上往下逐个取用，即后洗好的盘子反而要比先洗好的盘子更提前被使用到。这便是栈的典型特征：后进先出（last in first out）。例如：如果进栈顺序是a1，a2，则出栈顺序是：a1，a2或者a2，a1。出栈顺序的不唯一是因为可能够有如下两种情况：（1）a1入栈后马上出栈，然后a2入栈再出栈，因此出栈顺序是a1，a2。（2）在a1，a2都

2、入栈后a2在栈顶要先出栈，然后是a1出栈。1、栈的定义与基本运算规定：an为栈顶，a1为栈底(1).初始化操作：Init_Stack(s)；(2).判断栈是否为空：Empty_Stack(s)；(3).入栈：Push_Stack(s,x)；(4).出栈：Pop_Stack(s)；(5).读取栈顶元素：GetTop_Stack(s)；(6).销毁栈：Destroy_Stack(s)；(7).显示栈内所有数据：Traverse_Stack(s)；2、栈的顺序存储和链式存储用C语言的一维数组来定义动态顺序存储的类型：#define StackInitSize 100 /栈存储空间的初始分配量#def

3、ine StackIncrementSize 10 /栈存储空间的分配增量typedefstructSelemType*base;/栈底指针SelemType*top;/栈顶指针intstacksize;/当前分配的栈可使用最大存储容量 Seqstack;2、栈的顺序存储和链式存储如右图所示，top指向栈顶元素的下一位置，top=0表示空栈。top=StackSize-1表示栈满。当栈满时再做进栈运算必定产生空间溢出，简称“上溢”；当栈空时再做退栈运算也将产生溢出，简称“下溢”。上溢是一种出错状态，应该设法避免之。下溢一般是正常现象，常常用来作为程序控制转移的条件。2、栈的顺序存储和链式存储（

4、1）构造一个空栈SvoidInit_Stack(SeqStack*S)S.base=(SelemType*)malloc(StackInitSize*sizeof(Selemtype);if(!S.base)printf(“存储空间分配失败”);S.top=S.base;S.stacksize=STACK_INIT_SIZE;printf(“存储空间分配成功”);2、栈的顺序存储和链式存储（3）入栈操作void Push(SeqStack*S,SelemType e)if(S.top-S.base=S.stacksize)/栈满，追加存储空间S.base=(SelemType*)realloc

5、(S.base,(S.stacksize+StackIncrementSize)*sizeof(Selemtype);if(!S.base)printf(“存储空间分配失败”);S.top=S.base+S.stacksize;S.stacksize+=StackIncrementSize;*S.top+=e;printf(“存储空间分配成功”);2、栈的顺序存储和链式存储（4）出栈操作，退出一个栈内节点并得到栈顶数据元素的值。首先判断栈是否为空栈，若不空则取得栈顶元素并且栈高度-1void Pop_Stack(SeqStack*S,SelemType*e)if(S.top=S.base)pr

6、intf(“当前栈空，出栈失败”);e=*S.top-;printf(“出栈成功”);2、栈的顺序存储和链式存储栈除了顺序存储方式外还有链式存式存储，栈用链式存储结构实现简称链栈。链栈的节点结构和链表的节点结构相同，值得注意的是，链栈中指针的方向是从栈顶指向栈底链栈中指针的方向是从栈顶指向栈底链栈中指针的方向是从栈顶指向栈底链栈中指针的方向是从栈顶指向栈底。2、栈的顺序存储和链式存储下面我们简单介绍的一些链栈的基本操作。（1）建立一个空栈只要利用已经定义的链表的节点指针类型声明一个栈顶指针，并将其置为空即可。建立一个空栈的代码语句如下：NODEPTR top;top=NULL;2、栈的顺序存储

7、和链式存储（2）进栈操作，让一个数据元素e进入链栈在链式存储结构下，不需要判断栈未满，只需建立一个新节点并为其分内存空间，之后挂载到链头位置即可。void Push_Stack(NODEPTR*top,elemtype e)NODEPTR p;p=(NODEPTR)malloc(LEN);if(p=NULL)printf(“系统分配空间失败！”);return;p-data=e;/存入新节点元素值p-next=(*top);/新节点与原栈顶相连接(*top)=p;/新节点作为新栈顶3、队列的定义与基本运算队列（Queue）是限定只能在一端进行插入，在另外一端进行删除的线性表。在队列中，允许插入

8、的一端被称为队尾（rear），允许删除的一端被称为队头（front）。例如：a1是队头元素，an是队尾元素。通过看下图我们可以知道队列中的元素是以a1，a2，a3an的顺序入队的，则退出时肯定也是以a1，a2，a3an的顺序出队的。即a1是第一个出队列的元素，只有在a1，a2，an-1都离开了队列之后，an才能出队列。队列的修改是依据“先进先出”的原则进行，因此队列又称FIFO（First In First Out）表。3、队列的定义与基本运算规定：a1为队头，an为队尾(1).初始化操作：Init_Queue(q)；(2).入队操作：In_Queue(q,x)；(3).出队操作：Out_Qu

9、eue(q,x)；(4).读队头元素：Front_Queue(q)；(5).判断队列是否为空：Empty_Queue(q)；(6).求队列长度：Len_Queue(q)；(7).销毁队列：Destroy_Queue(q)；4、队列的顺序存储和链式存储队列是线性表性表的一种特殊情况，所以队列也和一般的线性表一样，有两种存储结构：顺序队列和链式队列。采用顺序结构存储的队列被称为顺序队列顺序队列顺序队列顺序队列，队列是在队头和队尾进行各种操作的，它们的位置都有可能发生变化，因此为了操作方便，除了队列的数据区外还设置了队头、队尾两个指针。队列的数据区域为sq-data0，sq-dataMAXSIZE-

10、1，队头指针为队头指针为队头指针为队头指针为sq-frontsq-front，队尾指针为队尾指针为队尾指针为队尾指针为sq-rearsq-rear。4、队列的顺序存储和链式存储顺序队的定义代码如下：#define MAXSIZE 100/定义顺序队列的最大容量typedef structdatatype dataMAXSIZE;/定义队列元素的存储空间int front,rear;/定义队头和队尾指针SeqQueue定义指向队列的指针变量SeqQueue*sq;申请顺序队的存储空间sq=malloc(sizeof(SeqQueue);4、队列的顺序存储和链式存储一般情况下，设队头指针指向队头元

11、素的前一个位置，即队头指针位置+1才是队列的第一个元素所在存储地址，队尾指针指向队列的最后一个元素。在不考虑队列的溢出问题的前提下，入队操作可以分为两步来进行，首先将队尾指针rear+指向新的队尾位置，其次将插入元素放进队尾指针指向空间，完成入队操作即可。具体代码实现如下：sq-rear+;sq-datasq-rear=a;/将新元素a进行入队4、队列的顺序存储和链式存储顺序队列的“假溢出假溢出假溢出假溢出”现象：下页图是顺序队各种操作示意，从图中可以看到不管是入队操作还是出队操作，整个队列都会随着操作的进展向数组中下标较大的位置方向移动，因为从上述相关操作可以看到，都会执行“+”这一步，于是

12、就出现了d的情况，此时队尾指针rear已经移到了所分配空间的最后一个位置，但是此时队列中并没有满载，可以看出所分配的存储空间的下半部分几乎完全空闲，并没有元素存储进来。这种现象我们称为“假溢出假溢出”。出现假溢出现象的主要原因是队列本身主要原因是队列本身“队尾进入，队尾进入，队头出队头出”的特性所造成的限制的特性所造成的限制。4、队列的顺序存储和链式存储9rear-a98rear-a8a87a7a76a6a65a5a54rear-a4front-front-3a32a21a10a0front-front-rear-（a）空队列（b）5个元素入队（c）出队入队（d）假溢出情况4、队列的顺序存储和

13、链式存储如何解决这种假溢出现象，使存储空间能得到充分的利用呢？很明显的一点，我们必须想方设法让MAXSIZE的下一个元素进入的时候，能够进入到0开始的地址里去。也就是说，我们需要设计一种方法，使的队列的数据区data0MAXSIZE-1能够形成一个循环关系，头尾指针front、rear的指示特性不变，这种结构称为循循循循环队环队列列列列。入队的时候，将队尾的自加1操作修改为sq-rear=(sq-front+1)%MAXSIZE;出队的时候，将队头指针自加1操作修改为sq-front=(sq-front+1)%MAXSIZE;4、队列的顺序存储和链式存储“空队列和满队列判定条件一致”问题的解决

14、方案：方案1：少用一个元素空间，即把上页中的（d）图视为队列已经满，此时的指针状态是队尾指针+1就才与队头指针重合，于是此时队满的判定条件就变成了（rear+1）%MAXSIZE=front，队空的判定条件依然还是front=rear，以此区分出队满还是队空的状态；方案2：附设一个实时变化的存储变量来记录当下队列中元素个数的变量，例如设变量num，当num=0时，表示队列为空队列，当num=MAXSIZE时，表示队列为满队列；方案3：附设一个标志flag，当front=rear且flag=0时，队列为空，当front=rear且flag=1时，队列为满；4、队列的顺序存储和链式存储方案1的实现

15、：类型定义代码实现如下：typedef structdatatype dataMAXSIZE;/定义数据的存储空间int front,rear;/定义队头和队尾指针c_SeqQueue;/定义循环队列c_SeqQue相应操作算法如下：(1)置空队列c_SeqQueue*Init_SeqQueue()q=malloc(sizeof(c_SeqQueue);q-front=q-rear=-1;return q;4、队列的顺序存储和链式存储方案1的实现：(3)出队操作int Out_SeqQueue(c_SeqQueue*q,datatype*e)if(q-front=q-rear)printf(“

16、队列为空！”);return-1;/队列为空，不能完成出队操作else q-front=(q-front+1)%MAXSIZE;*e=q-dataq-front;/取队头元素指赋给ereturn 1;4、队列的顺序存储和链式存储方案1的实现：(4)判队列是否为空int Empty_SeqQueue(c_SeqQueue*q)if(q-front=q-rear)return 1;elsereturn 0;方案2的实现：类型定义代码实现如下：typedef structdatatype dataMAXSIZE;/定义数据的存储空间int front,rear;/定义队头和队尾指针int num;/

17、定义元素个数的统计变量c_SeqQueue;/定义循环队列c_SeqQue4、队列的顺序存储和链式存储方案2的实现：相应操作算法如下：(1)置空队c_SeqQueue*Init_SeqQueue()q=malloc(sizeof(c_SeqQueue);q-front=q-rear=-1;q-num=0;return q;(2)入队操作int In_SeqQueue(c_SeqQueue*q,datatype e)if(num=MAXSIZE)printf(“队列已经满！”);return-1;else q-rear=(q-rear+1)%MAXSIZE;4、队列的顺序存储和链式存储方案2的实

18、现：q-dataq-rear=e;num+;return 1;(3)出队操作int Out_SeqQueue(c_SeqQueue*q,datatype*e)if(num=0)printf(“队列为空！”);/队列为空，不能完成出队操作return-1;else q-front=(q-rear+1)%MAXSIZE;*e=q-dataq-front;/获取队头元素值num-;return 1;4、队列的顺序存储和链式存储方案2的实现：(4)判定队列是否为空int Empty_SeqQueue(c_SeqQueue*q)if(num=0)return 1;elsereturn 0;第三种解决方案

19、相对较为简单，有兴趣的同学可以自行实现相关算法。4、队列的顺序存储和链式存储队列是线性表性表的一种特殊情况，所以队列也和一般的线性表一样，有两种存储结构：顺序队列和链式队列。链队列链队列链队列链队列和链表的存储结构完全相同，与链栈类似，我们一般是用单链表来实现链队单链表来实现链队单链表来实现链队单链表来实现链队。对链队来说，除了队头（即链头）指针front之外，还要使用队尾（即链尾）指针rear。4、队列的顺序存储和链式存储链队的数据类型定义如下：typedef struct nodeelemtype data;struct node*next;NODE,*NODEPTR/定义链队的数据节点类

20、型#define LEN sizeof(NODE);typedef struct NODEPTR front,rear;/定义链队LINKQUEUE;4、队列的顺序存储和链式存储(1)建立一个空队列利用已经定义的链表的节点指针类型声明一个队头和队尾指针，并将指针置为空即可，这里不再像顺序存储的章节里面那样需要一个队长度，因为在链队列里面不需要做队满判断，只要内存空间还存在可用的位置，就可以不停的完成入队操作；而队空判定的时候也只需要查验队头指针是否为空即可，也不再需要借助队伍中元素的个数来判断。所以建立一个空链队列的算法如下：void Init_Queue(LINKQUEUE*q)(*q).f

21、ront=(*q).rear=NULL;(2)判断一个队列是否为空，算法如下：int Empty_Queue(LINKQUEUE q)if(q.front=NULL)return 1;elsereturn 0;4、队列的顺序存储和链式存储(3)入队操作让一个数据元素e进入队列，首先要建立一个新节点e，然后判断队列是否为空，若是空队列，则此e进入队列后既是队头又是队尾，否则就将节点e直接链到队尾，并将队尾指针后移一个节点即可。void In_Queue(LINKQUEUE*q,elemtype e)NODEPTR p;p=(NODEPTR)malloc(LEN);p-data=e;if(*q).

22、front=NULL)(*q).front=(*q).rear=pp-next=NULL;else(*q).rear-next=p;(*q).rear=p;p-next=NULL;4、队列的顺序存储和链式存储(4)出队操作出队操作的结果是将队列的队头数据元素获取到，并同时将队头节点出队。首先判断队列是否为空，如果为空的话则无法完成出队操作；如果不为空，则取得队头节点数据元素值，并将队头指针向后移动一个位置。void Out_Queue(LINKQUEUE*q,elemtype*e)NODEPTR p;if(*q).front=NULL)printf(“队列为空，不能完成出队！”);return 0;else*e=(*q).front-data;p=(*q).front;(*q).front=(*q).front-next;free(p);if(*q).front=NULL)(*q).rear=NULL;4、队列的顺序存储和链式存储(5)获取队头元素值void Get_Queue(LINKQUEUE q,elemtype*e)if(q.front)*e=q.front-data;elseprintf(“队列为空，无法取值！”);