数据结构件—栈和队列学习教案.pptx

会计学1数据结构数据结构(sh j ji u)件件栈和队列栈和队列第一页，共73页。3.1 3.1 栈栈栈栈栈的逻辑栈的逻辑(lu j)结构结构（a1,a2,an）p栈：限定仅在表的一端进行栈：限定仅在表的一端进行(jnxng)插入和删除操插入和删除操作的线性表。作的线性表。p允许插入和删除的一端称为栈顶，另一端称为栈底。允许插入和删除的一端称为栈顶，另一端称为栈底。p空栈：不含任何数据元素的栈。空栈：不含任何数据元素的栈。栈顶栈顶栈底栈底第1页/共73页第二页，共73页。a1a2a3入栈入栈出栈出栈栈底栈底栈顶栈顶插入插入(ch r)：入栈、进栈、：入栈、进栈、压栈压栈删除：出栈、弹栈删除：出栈、弹栈栈顶栈顶栈顶栈顶 3.1 3.1 栈栈栈栈栈的逻辑栈的逻辑(lu j)结构结构第2页/共73页第三页，共73页。栈的操作栈的操作(cozu)特性：后进先出特性：后进先出a1a2a3入栈入栈出栈出栈栈底栈底栈顶栈顶插入插入(ch r)：入栈、进栈、：入栈、进栈、压栈压栈删除：出栈、弹栈删除：出栈、弹栈栈顶栈顶 3.1 3.1 栈栈栈栈栈的逻辑栈的逻辑(lu j)结构结构第3页/共73页第四页，共73页。例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个元素只的次序依次进栈，且每个元素只允许进一次栈，则可能允许进一次栈，则可能(knng)的出栈序列有多少种？的出栈序列有多少种？栈底栈底栈顶栈顶ab栈顶栈顶c栈顶栈顶 情况情况(qngkung)1：栈的逻辑栈的逻辑(lu j)结构结构 3.1 3.1 栈栈栈栈第4页/共73页第五页，共73页。栈底栈底栈顶栈顶ab栈顶栈顶c栈顶栈顶出栈序列出栈序列(xli)：c出栈序列出栈序列(xli)：c、b出栈序列出栈序列(xli)：c、b、a例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个元的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构栈的逻辑结构 情况情况1：3.1 3.1 栈栈栈栈第5页/共73页第六页，共73页。栈底栈底栈顶栈顶ab栈顶栈顶出栈序列出栈序列(xli)：b 情况情况(qngkung)2：例：有三个元素按例：有三个元素按a、b、c的次序的次序(cx)依次进栈，且每个依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？元素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构栈的逻辑结构 3.1 3.1 栈栈栈栈第6页/共73页第七页，共73页。栈底栈底a出栈序列出栈序列(xli)：b出栈序列出栈序列(xli)：b、c出栈序列出栈序列(xli)：b、c、ac栈顶栈顶栈顶栈顶注意：注意：栈只是对表插入和删除操作的位置进行了限制，栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。并没有限定插入和删除操作进行的时间。例：有三个元素按例：有三个元素按a、b、c的次序依次进栈，且每个元的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？素只允许进一次栈，则可能的出栈序列有多少种？栈的逻辑结构栈的逻辑结构 情况情况2：3.1 3.1 栈栈栈栈第7页/共73页第八页，共73页。栈的抽象数据类型定义栈的抽象数据类型定义(dngy)ADT StackData 栈中元素具有相同栈中元素具有相同(xin tn)类型及后进先类型及后进先出特性，出特性，相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系Operation InitStack 前置条件：栈不存在前置条件：栈不存在 输入：无输入：无 功能：栈的初始化功能：栈的初始化 输出：无输出：无 后置条件：构造一个空栈后置条件：构造一个空栈 3.1 3.1 栈栈栈栈第8页/共73页第九页，共73页。DestroyStackDestroyStack 前置条件：栈已存在前置条件：栈已存在前置条件：栈已存在前置条件：栈已存在 输入：无输入：无输入：无输入：无 功能：销毁栈功能：销毁栈功能：销毁栈功能：销毁栈 输出：无输出：无输出：无输出：无 后置条件：释放栈所占用的存储空间后置条件：释放栈所占用的存储空间后置条件：释放栈所占用的存储空间后置条件：释放栈所占用的存储空间Push Push 前置条件：栈已存在前置条件：栈已存在前置条件：栈已存在前置条件：栈已存在 输入：元素输入：元素输入：元素输入：元素(yun s)(yun s)值值值值x x 功能：在栈顶插入一个元素功能：在栈顶插入一个元素功能：在栈顶插入一个元素功能：在栈顶插入一个元素(yun s)x(yun s)x 输出：如果插入不成功，抛出异常输出：如果插入不成功，抛出异常输出：如果插入不成功，抛出异常输出：如果插入不成功，抛出异常 后置条件：如果插入成功，栈顶增加了一个元素后置条件：如果插入成功，栈顶增加了一个元素后置条件：如果插入成功，栈顶增加了一个元素后置条件：如果插入成功，栈顶增加了一个元素(yun s)(yun s)栈的抽象数据类型定义栈的抽象数据类型定义(dngy)3.1 3.1 栈栈栈栈第9页/共73页第十页，共73页。Pop Pop 前置条件：栈已存在前置条件：栈已存在前置条件：栈已存在前置条件：栈已存在 输入输入输入输入(shr)(shr)：无：无：无：无 功能：删除栈顶元素功能：删除栈顶元素功能：删除栈顶元素功能：删除栈顶元素 输出：如果删除成功，返回被删元素值，否则，抛出异常输出：如果删除成功，返回被删元素值，否则，抛出异常输出：如果删除成功，返回被删元素值，否则，抛出异常输出：如果删除成功，返回被删元素值，否则，抛出异常 后置条件：如果删除成功，栈减少了一个元素后置条件：如果删除成功，栈减少了一个元素后置条件：如果删除成功，栈减少了一个元素后置条件：如果删除成功，栈减少了一个元素GetTopGetTop 前置条件：栈已存在前置条件：栈已存在前置条件：栈已存在前置条件：栈已存在 输入输入输入输入(shr)(shr)：无：无：无：无 功能：读取当前的栈顶元素功能：读取当前的栈顶元素功能：读取当前的栈顶元素功能：读取当前的栈顶元素 输出：若栈不空，返回当前的栈顶元素值输出：若栈不空，返回当前的栈顶元素值输出：若栈不空，返回当前的栈顶元素值输出：若栈不空，返回当前的栈顶元素值 后置条件：栈不变后置条件：栈不变后置条件：栈不变后置条件：栈不变栈的抽象数据类型定义栈的抽象数据类型定义(dngy)3.1 3.1 栈栈栈栈第10页/共73页第十一页，共73页。Empty 前置条件：栈已存在前置条件：栈已存在 输入：无输入：无 功能：判断栈是否为空功能：判断栈是否为空 输出：如果栈为空，返回输出：如果栈为空，返回1，否则，否则(fuz)，返，返回回0 后置条件：栈不变后置条件：栈不变endADT栈的抽象数据类型定义栈的抽象数据类型定义(dngy)3.1 3.1 栈栈栈栈第11页/共73页第十二页，共73页。栈的顺序存储结构栈的顺序存储结构(jigu)及实现及实现 顺序顺序(shnx)栈栈栈的顺序栈的顺序(shnx)存储结构存储结构如何改造数组实现栈的顺序存储如何改造数组实现栈的顺序存储？0 1 2 3 4 5 6 7 8a1确定用数组的哪一端确定用数组的哪一端(ydun)表示栈底。表示栈底。附设指针附设指针top指示栈顶元素在数组中的位置。指示栈顶元素在数组中的位置。top 3.1 3.1 栈栈栈栈第12页/共73页第十三页，共73页。出栈：出栈：top减减1进栈：进栈：top加加1栈空：栈空：top=-1 0 1 2 3 4 5 6 7 8a1topa2topa3top栈满：栈满：top=MAX_SIZE-1栈的顺序存储结构栈的顺序存储结构(jigu)及实及实现现 3.1 3.1 栈栈栈栈第13页/共73页第十四页，共73页。顺顺序序(shnx)栈栈类类的的声声明明const int MAX_SIZE=100;template class seqStack public:seqStack();seqStack();void Push(DataType x);DataType Pop();DataType GetTop();bool Empty();private:DataType dataMAX_SIZE;int top;3.1 3.1 栈栈栈栈第14页/共73页第十五页，共73页。顺序顺序(shnx)(shnx)栈的实现栈的实现入栈入栈template template void seqStack:Push(DataType x)void seqStack:Push(DataType x)if(top=MAX_SIZE-1)throw “if(top=MAX_SIZE-1)throw “溢出溢出溢出溢出(y ch)”;(y ch)”;top+;top+;datatop=x;datatop=x;操作操作(cozu)(cozu)接口：接口：void Push(DataType void Push(DataType x);x);时间复杂度？时间复杂度？data+top=x 3.1 3.1 栈栈栈栈第15页/共73页第十六页，共73页。顺序顺序(shnx)(shnx)栈的实现栈的实现出栈出栈template template DataType seqStack:Pop()DataType seqStack:Pop()if(top=-1)throw “if(top=-1)throw “溢出溢出溢出溢出(y ch)”;(y ch)”;x=datatop-;x=datatop-;return x;return x;操作操作(cozu)(cozu)接口：接口：DataType Pop();DataType Pop();时间复杂度？时间复杂度？3.1 3.1 栈栈栈栈第16页/共73页第十七页，共73页。两栈共享空间两栈共享空间(kngjin)解决方案解决方案1：直接解决：为每个栈开辟一个数组空间。直接解决：为每个栈开辟一个数组空间。解决方案解决方案2：顺顺序序栈栈单单向向延延伸伸使使用用一一个个数数组组来来存存储储(cn ch)两个栈两个栈在一个程序中需要在一个程序中需要同时同时使用具有使用具有相同相同数据类型的数据类型的两个栈两个栈，如何顺序存储这两个栈？如何顺序存储这两个栈？会出现什么问题？如何解决？会出现什么问题？如何解决？3.1 3.1 栈栈栈栈第17页/共73页第十八页，共73页。两栈共享空间：使用一个数组来存储两个栈，让一个栈的两栈共享空间：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自两个栈从各自(gz)(gz)的端点向中间延伸。的端点向中间延伸。两栈共享空间两栈共享空间(kngjin)3.1 3.1 栈栈栈栈第18页/共73页第十九页，共73页。栈栈1的底固定在下标为的底固定在下标为0的一端；的一端；栈栈2的底固定在下标为的底固定在下标为StackSize-1的一端。的一端。top1和和top2分别为栈分别为栈1和栈和栈2的栈顶指针；的栈顶指针；Stack_Size为整个数组空间为整个数组空间(kngjin)的大小（图中用的大小（图中用S表示表示）；）；a1 a2 aitop10 1 2 S-1两栈共享空间两栈共享空间(kngjin)top2bj b2 b1栈栈1底底栈栈2底底 3.1 3.1 栈栈栈栈第19页/共73页第二十页，共73页。top1=-1什么时候栈什么时候栈1为空？为空？a1 a2 aitop10 1 2 S-1两栈共享空间两栈共享空间(kngjin)top2bj b2 b1top1 3.1 3.1 栈栈栈栈第20页/共73页第二十一页，共73页。top1=-1什么时候栈什么时候栈1为空？为空？a1 a2 aitop10 1 2 S-1两栈共享空间两栈共享空间(kngjin)top2bj b2 b1什么时候栈什么时候栈2为空？为空？top2top2=Stack_Size 3.1 3.1 栈栈栈栈第21页/共73页第二十二页，共73页。top1=-1什么时候栈什么时候栈1为空？为空？a1 a2 aitop10 1 2 S-1两栈共享空间两栈共享空间(kngjin)top2bj b2 b1什么时候栈什么时候栈2为空？为空？top2=Stack_Size什么时候栈满？什么时候栈满？top2=top1+1 3.1 3.1 栈栈栈栈第22页/共73页第二十三页，共73页。const int Stack_Size=100;template class BothStack public:BothStack()();BothStack()();void Push(int i,DataType x);DataType Pop(int i);DataType GetTop(int i);bool Empty(int i);private:DataType dataStack_Size;int top1,top2;两两栈栈共共享享空空间间(kngjin)类类的的声声明明 3.1 3.1 栈栈栈栈第23页/共73页第二十四页，共73页。1.如果栈满，则抛出上溢异常如果栈满，则抛出上溢异常(ychng)；2.判断是插在栈判断是插在栈1还是栈还是栈2；2.1 若在栈若在栈1插入，则插入，则加加1;在在top1处填入处填入x；2.2 若在栈若在栈2插入，则插入，则减减1;在在top2处填入处填入x；两栈共享空间的实现两栈共享空间的实现(shxin)插入插入 操作操作(cozu)接口：接口：void Push(int i,DataType x);3.1 3.1 栈栈栈栈第24页/共73页第二十五页，共73页。1.若是在栈若是在栈1删除，则删除，则 1.1 若栈若栈1为空栈，抛出下溢异常为空栈，抛出下溢异常(ychng)；1.2 删除并返回栈删除并返回栈1的栈顶元素；的栈顶元素；2.若是在栈若是在栈2删除，则删除，则 2.1 若栈若栈2为空栈，抛出下溢异常为空栈，抛出下溢异常(ychng)；2.2 删除并返回栈删除并返回栈2的栈顶元素；的栈顶元素；两栈共享空间的实现两栈共享空间的实现(shxin)删除删除 操作操作(cozu)接口：接口：DataType Pop(int i);3.1 3.1 栈栈栈栈第25页/共73页第二十六页，共73页。栈的链接存储结构栈的链接存储结构(jigu)及实及实现现 链栈：栈的链接存储链栈：栈的链接存储(cn ch)结构结构firsta1a2anai链栈需要加头结点吗？链栈需要加头结点吗？如何改造链表实现栈的链接存储如何改造链表实现栈的链接存储？将哪一端作为栈顶？将哪一端作为栈顶？将链头作为将链头作为(zuwi)栈顶，栈顶，方便操作。方便操作。链栈不需要附设头结点。链栈不需要附设头结点。3.1 3.1 栈栈栈栈第26页/共73页第二十七页，共73页。栈的链接存储栈的链接存储(cn ch)结构及实现结构及实现 栈顶栈顶栈底栈底链栈：栈的链接链栈：栈的链接(lin ji)存储存储结构结构topanan-1a1firsta1a2anai两种示意图在内存两种示意图在内存(ni cn)中对应同一种状态，启示？中对应同一种状态，启示？topa1an-1an栈顶栈顶栈底栈底 3.1 3.1 栈栈栈栈第27页/共73页第二十八页，共73页。链链栈栈的的类类声声明明template class LinkStack public:LinkStack()();LinkStack()();void Push(DataType x);DataType Pop()();DataType GetTop()();bool Empty()();private:Node*top;3.1 3.1 栈栈栈栈第28页/共73页第二十九页，共73页。template void LinkStack:Push(DataType x)s=new Node;s-data=x;s-next=top;top=s;topanan-1a1链栈的实现链栈的实现(shxin)插入插入 xstop操作操作(cozu)接口：接口：void Push(DataType x);为什么没有判断栈满？为什么没有判断栈满？3.1 3.1 栈栈栈栈第29页/共73页第三十页，共73页。template DataType LinkStack:Pop()if(top=NULL)throw 下溢下溢;x=top-data;p=top;top=top-next;delete p;return x;链栈的实现链栈的实现(shxin)插入插入操作操作(cozu)接口：接口：DataType Pop();topanan-1a1topptop+可以吗？可以吗？3.1 3.1 栈栈栈栈第30页/共73页第三十一页，共73页。顺序顺序(shnx)栈和链栈的比较栈和链栈的比较时间时间(shjin)性能：相同，都是常数时间性能：相同，都是常数时间(shjin)O(1)。空间空间(kngjin)性能：性能：顺序栈：有元素个数的限制和空间顺序栈：有元素个数的限制和空间(kngjin)浪费的问题。浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间链栈：没有栈满的问题，只有当内存没有可用空间(kngjin)时才会出现栈满，但是每个元素都需要一个指时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。针域，从而产生了结构性开销。总之，当栈的使用过程中元素总之，当栈的使用过程中元素个数变化个数变化较大时，用链栈是较大时，用链栈是适宜的，反之，应该采用顺序栈。适宜的，反之，应该采用顺序栈。3.1 3.1 栈栈栈栈第31页/共73页第三十二页，共73页。3.2 3.2 队列队列队列队列(duli)(duli)队列队列(duli)的逻辑结构的逻辑结构p 队列：只允许在一端进行插入操作，而另一端进行队列：只允许在一端进行插入操作，而另一端进行删除删除(shnch)操作的线性表。操作的线性表。p 允许插入（也称入队、进队）的一端称为队尾，允允许插入（也称入队、进队）的一端称为队尾，允许删除许删除(shnch)（也称出队）的一端称为队头。（也称出队）的一端称为队头。p 空队列：不含任何数据元素的队列。空队列：不含任何数据元素的队列。（a1,a2,an）队尾队尾队头队头第32页/共73页第三十三页，共73页。队列队列(duli)的操作特性：的操作特性：先进先出先进先出a1a2a3入队入队(r du)队尾队尾队头队头出队出队队头队头队列队列(duli)的逻辑结构的逻辑结构3.2 3.2 队列队列队列队列第33页/共73页第三十四页，共73页。队列队列(duli)的抽象数据类型的抽象数据类型定义定义 ADT Queue Data 队列中元素具有相同队列中元素具有相同(xin tn)类型及先进先出特性，类型及先进先出特性，相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系Operation InitQueue 前置条件：队列不存在前置条件：队列不存在 输入：无输入：无 功能：初始化队列功能：初始化队列 输出：无输出：无 后置条件：创建一个空队列后置条件：创建一个空队列3.2 3.2 队列队列队列队列(duli)(duli)第34页/共73页第三十五页，共73页。DestroyQueue DestroyQueue 前置条件：队列已存在前置条件：队列已存在 输入：无输入：无 功能：销毁队列功能：销毁队列 输出：无输出：无 后置条件：释放队列所占用的存储空间后置条件：释放队列所占用的存储空间 EnQueue EnQueue 前置条件：队列已存在前置条件：队列已存在 输入：元素值输入：元素值x x 功能：在队尾插入一个功能：在队尾插入一个(y(y )元素元素 输出：如果插入不成功，抛出异常输出：如果插入不成功，抛出异常 后置条件：如果插入成功，队尾增加了一个后置条件：如果插入成功，队尾增加了一个(y(y )元素元素队列队列(duli)的抽象数据类型的抽象数据类型定义定义 3.2 3.2 队列队列队列队列(duli)(duli)第35页/共73页第三十六页，共73页。DeQueue DeQueue 前置条件：队列已存在前置条件：队列已存在 输入：无输入：无 功能：删除队头元素功能：删除队头元素 输出：如果删除成功，返回输出：如果删除成功，返回(f(f nhu)nhu)被删元素值被删元素值 后置条件：如果删除成功，队头减少了一个元素后置条件：如果删除成功，队头减少了一个元素 GetQueue GetQueue 前置条件：队列已存在前置条件：队列已存在 输入：无输入：无 功能：读取队头元素功能：读取队头元素 输出：若队列不空，返回输出：若队列不空，返回(f(f nhu)nhu)队头元素队头元素 后置条件：队列不变后置条件：队列不变队列队列(duli)的抽象数据类型的抽象数据类型定义定义 3.2 3.2 队列队列队列队列(duli)(duli)第36页/共73页第三十七页，共73页。Empty 前置条件：队列已存在前置条件：队列已存在 输入：无输入：无 功能：判断功能：判断(pndun)队列是否为空队列是否为空 输出：如果队列为空，返回输出：如果队列为空，返回1，否则，返回，否则，返回0 后置条件：队列不变后置条件：队列不变endADT队列队列(duli)的抽象数据类型的抽象数据类型定义定义 3.2 3.2 队列队列队列队列(duli)(duli)第37页/共73页第三十八页，共73页。0 1 2 3 4 入队入队出队出队队列队列(duli)的顺序存储结构及实的顺序存储结构及实现现 顺序队列顺序队列(duli)队列队列(duli)的顺序存储的顺序存储结构结构如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2a3a4依次依次(yc)入队入队a1a2a3a4rearrear rear rear入队操作时间性能为入队操作时间性能为O(1)3.2 3.2 队列队列队列队列第38页/共73页第三十九页，共73页。如何改造数组实现如何改造数组实现(shxin)队列的顺序存队列的顺序存储？储？例：例：a1a2依次依次(yc)出出队队队列的顺序存储结构队列的顺序存储结构(jigu)及实及实现现 0 1 2 3 4 入队入队出队出队a1a2a3a4rear3.2 3.2 队列队列队列队列第39页/共73页第四十页，共73页。如何改造如何改造(gizo)数组实现队列的顺序存储数组实现队列的顺序存储？例：例：a1a2依次依次(yc)出出队队队列的顺序存储结构队列的顺序存储结构(jigu)及实及实现现 0 1 2 3 4 入队入队出队出队a2a3a4rear3.2 3.2 队列队列队列队列第40页/共73页第四十一页，共73页。如何改造数组实现如何改造数组实现(shxin)队列的顺序队列的顺序存储？存储？例：例：a1a2依次依次(yc)出队出队队列队列(duli)的顺序存储结构及的顺序存储结构及实现实现 0 1 2 3 4 入队入队出队出队a3a4rear出队操作时间性能为出队操作时间性能为O(n)3.2 3.2 队列队列队列队列第41页/共73页第四十二页，共73页。队列的顺序存储结构队列的顺序存储结构(jigu)及实现及实现 如何改进出队的时间性能？如何改进出队的时间性能？放宽队列的所有元素必须存储在数组的前放宽队列的所有元素必须存储在数组的前n个单元这一个单元这一条件条件，只要求队列的元素存储在数组中连续的位置。，只要求队列的元素存储在数组中连续的位置。设置队头、队尾两个指针设置队头、队尾两个指针 3.2 3.2 队列队列队列队列(duli)(duli)第42页/共73页第四十三页，共73页。队列队列(duli)的顺序存储结构及实现的顺序存储结构及实现 0 1 2 3 4 入队入队出队出队例：例：a1a2a3a4依次依次(yc)入入队队a1a2a3a4rearrear rear rear入队入队(r du)操作时间性能仍操作时间性能仍为为O(1)front rear3.2 3.2 队列队列队列队列约定：队头指针约定：队头指针front指向队头元素的前一个位置，指向队头元素的前一个位置，队尾指针队尾指针rear指向队尾元素。指向队尾元素。第43页/共73页第四十四页，共73页。例：例：a1a2依次依次(yc)出队出队队列的顺序存储结构队列的顺序存储结构(jigu)及及实现实现 0 1 2 3 4 入队入队出队出队a1a2a3a4rearfrontfrontfront出队操作时间出队操作时间(shjin)性能提性能提高为高为O(1)3.2 3.2 队列队列队列队列第44页/共73页第四十五页，共73页。例：例：a1a2依次依次(yc)出队出队队列队列(duli)的顺序存储结构及实的顺序存储结构及实现现 0 1 2 3 4 入队入队出队出队a3a4rearfront队列的移动有什么特点？队列的移动有什么特点？3.2 3.2 队列队列队列队列(duli)(duli)第45页/共73页第四十六页，共73页。例：例：a1a2依次依次(yc)出队出队队列队列(duli)的顺序存储结构及实的顺序存储结构及实现现 0 1 2 3 4 入队入队出队出队a3a4rearfront整个队列向数组下标较大方向移动整个队列向数组下标较大方向移动单向移动性单向移动性3.2 3.2 队列队列队列队列(duli)(duli)第46页/共73页第四十七页，共73页。假溢出：当元素被插入到数组中下标最大的位置上之后，假溢出：当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象这种现象(xinxing)叫做假溢出。叫做假溢出。队列的顺序存储结构队列的顺序存储结构(jigu)及实现及实现 继续入队会出现什么情况？继续入队会出现什么情况？0 1 2 3 4 入队入队出队出队a3a4rearfronta5rear3.2 3.2 队列队列队列队列(duli)(duli)第47页/共73页第四十八页，共73页。循环队列：将存储循环队列：将存储(cn ch)队列的数组头尾相接。队列的数组头尾相接。队列的顺序存储结构队列的顺序存储结构(jigu)及实现及实现 如何解决假溢出？如何解决假溢出？0 1 2 3 4 入队入队(r du)出队出队a3a4fronta5rearreara63.2 3.2 队列队列队列队列第48页/共73页第四十九页，共73页。不存在物理的循环结构，用软件方法不存在物理的循环结构，用软件方法(fngf)实现。实现。求模：（求模：（41）mod 50队列队列(duli)的顺序存储结构及实的顺序存储结构及实现现 如何实现循环队列？如何实现循环队列？0 1 2 3 4 入队入队(r du)出队出队a3a4frontreara63.2 3.2 队列队列队列队列第49页/共73页第五十页，共73页。如何判断循环队列队空？如何判断循环队列队空？队空的临界状态队空的临界状态(ln ji zhun ti)队列的顺序存储结构队列的顺序存储结构(jigu)及实及实现现 0 1 2 3 4 入队入队(r du)出队出队a3rearfront3.2 3.2 队列队列队列队列第50页/共73页第五十一页，共73页。如何判断循环队列队空？如何判断循环队列队空？执行执行(zhxng)出出队操作队操作队空：队空：front=rear队列的顺序存储结构队列的顺序存储结构(jigu)及实现及实现 0 1 2 3 4 入队入队(r du)出队出队a3frontrearfront3.2 3.2 队列队列队列队列第51页/共73页第五十二页，共73页。如何判断循环队列队满？如何判断循环队列队满？队满的临界状态队满的临界状态(ln ji zhun ti)队列队列(duli)的顺序存储结构及实的顺序存储结构及实现现 0 1 2 3 4 入队入队(r du)出队出队a3a4fronta5reara63.2 3.2 队列队列队列队列第52页/共73页第五十三页，共73页。如何判断循环队列队满？如何判断循环队列队满？执行入队执行入队(r du)操操作作队满：队满：front=rear队列的顺序存储结构队列的顺序存储结构(jigu)及及实现实现 0 1 2 3 4 入队入队(r du)出队出队a3a4fronta5reara6reara73.2 3.2 队列队列队列队列第53页/共73页第五十四页，共73页。方法一：附设一个存储队列中元素个数的变量方法一：附设一个存储队列中元素个数的变量num，当，当num=0时队空，当时队空，当num=QueueSize时为队满；时为队满；方法二：修改方法二：修改(xigi)队满条件，浪费一个元素空间，队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元；队满时数组中只有一个空闲单元；方法三：设置标志方法三：设置标志flag，当，当front=rear且且flag=0时为队空，时为队空，当当front=rear且且flag=1时为队满。时为队满。如何确定不同的队空、队满的判定条件？如何确定不同的队空、队满的判定条件？为什么要将队空和队满的判定条件分开？为什么要将队空和队满的判定条件分开？队列的顺序存储结构队列的顺序存储结构(jigu)及实现及实现 3.2 3.2 队列队列队列队列(duli)(duli)第54页/共73页第五十五页，共73页。队满的条件队满的条件(tiojin)：(rear+1)mod QueueSize=front队列的顺序存储结构队列的顺序存储结构(jigu)及实现及实现 0 1 2 3 4 入队入队rearfronta3a4fronta5reara6出队出队3.2 3.2 队列队列队列队列(duli)(duli)第55页/共73页第五十六页，共73页。循循环环队队列列类类的的声声明明const int QueueSize=100;template class CirQueue public:CirQueue()()；CirQueue()()；void EnQueue(DataType x);DataType DeQueue()();DataType GetQueue()();bool Empty()()；private:DataType dataQueueSize;int front,rear;3.2 3.2 队列队列队列队列(duli)(duli)第56页/共73页第五十七页，共73页。template void CirQueue:EnQueue(DataType x)if(rear+1)%QueueSize=front)throw 上溢上溢;rear=(rear+1)%QueueSize;datarear=x;循环队列的实现循环队列的实现(shxin)入队入队0 1 2 3 4 入队入队出队出队a3a4rearfronta5rear3.2 3.2 队列队列队列队列(duli)(duli)第57页/共73页第五十八页，共73页。0 1 2 3 4 入队入队(r du)a4a5a6出队出队template DataType CirQueue:DeQueue()if(rear=front)throw 下溢下溢;front=(front+1)%QueueSize;return datafront;循环队列循环队列(duli)的实现的实现出出队队frontrearfronta33.2 3.2 队列队列队列队列(duli)(duli)第58页/共73页第五十九页，共73页。template DataType CirQueue:GetQueue()if(rear=front)throw 下溢下溢;i=(front+1)%QueueSize;return datai;循环队列循环队列(duli)的实现的实现读队读队头元素头元素0 1 2 3 4 入队入队(r du)a4a5a6出队出队frontreara3 i3.2 3.2 队列队列队列队列(duli)(duli)第59页/共73页第六十页，共73页。队列队列(duli)的链接存储结构及实的链接存储结构及实现现 链队列链队列(duli)：队列：队列(duli)的链接存储的链接存储结构结构 队头指针队头指针(zhzhn)即为链表即为链表的头指针的头指针(zhzhn)firsta1a2an如何改造单链表实现队列的链接存储？如何改造单链表实现队列的链接存储？rearfront3.2 3.2 队列队列队列队列第60页/共73页第六十一页，共73页。队列的链接存储队列的链接存储(cn ch)结构及实结构及实现现 非空链队列非空链队列(duli)fronta1a2anrear空链队列空链队列(duli)frontrear3.2 3.2 队列队列队列队列第61页/共73页第六十二页，共73页。链链队队列列类类的的声声明明template class LinkQueue public:LinkQueue()();LinkQueue()();void EnQueue(DataType x);DataType DeQueue()();DataType GetQueue()()；bool Empty()()；private:Node*front,*rear;3.2 3.2 队列队列队列队列(duli)(duli)第62页/共73页第六十三页，共73页。操作操作(cozu)接口：接口：LinkQueue();算法算法(sun f)描述：描述：template LinkQueue:LinkQueue()front=new Node;front-next=NULL;rear=front;链队列链队列(duli)的实现的实现构造构造函数函数frontrear3.2 3.2 队列队列队列队列第63页/共73页第六十四页，共73页。xs链队列的实现链队列的实现(shxin)入队入队操作操作(cozu)接口：接口：void EnQueue(DataType x);fronta1anrearrearfront xsrearrear算法算法(sun f)描述：描述：s-next=NULL;rear-next=s;rear=s;如何没有头结点会怎样？如何没有头结点会怎样？3.2 3.2 队列队列队列队列第64页/共73页第六十五页，共73页。xs链队列的实现链队列的实现(shxin)入队入队操作操作(cozu)接口：接口：void EnQueue(DataType x);fronta2anrearrear算法算法(sun f)描述：描述：s-next=NULL;rear-next=s;rear=s;如何没有头结点会怎样？如何没有头结点会怎样？a13.2 3.2 队列队列队列队列第65页/共73页第六十六页，共73页。链队列的实现链队列的实现(shxin)入队入队操作操作(cozu)接口：接口：void EnQueue(DataType x);front=rear=NULL xsrear算法算法(sun f)描述：描述：s-next=NULL;rear=s;front=s;如何没有头结点会怎样？如何没有头结点会怎样？front算法描述：算法描述：s-next=NULL;rear-next=s;rear=s;3.2 3.2 队列队列队列队列第66页/共73页第六十七页，共73页。链队列链队列(duli)的实现的实现入队入队template void LinkQueue:EnQueue(DataType x)s=new Node;s-data=x;s-next=NULL;rear-next=s;rear=s;3.2 3.2 队列队列队列队列(duli)(duli)第67页/共73页第六十八页，共73页。链队列链队列(duli)的实现的实现出队出队fronta1a