第三章栈和队列精选PPT.ppt

《第三章栈和队列精选PPT.ppt》由会员分享，可在线阅读，更多相关《第三章栈和队列精选PPT.ppt（90页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 栈和队列栈和队列第1页，本讲稿共90页纲要纲要Q3.1 栈的定义及其运算Q3.2 栈的表示和实现栈的表示和实现3.2.1 栈的顺序存储结构栈的顺序存储结构3.2.2 栈的链式存储结构栈的链式存储结构Q3.3 栈的应用栈的应用Q3.4 队队 列列Q3.5 队列的表示和实现队列的表示和实现3.5.1 队列的链式存储结构队列的链式存储结构3.5.2 队列的顺序存储结构Q3.6 队列的运用第2页，本讲稿共90页C从数据结构角度看，栈和队列是从数据结构角度看，栈和队列是操作受限操作受限的线性的线性表，他们的逻辑结构相同。表，他们的逻辑结构相同。C栈栈只允许在表的一端进行插入或删除操作只允许

2、在表的一端进行插入或删除操作C队列队列只允许在表的一端进行插入操作、而只允许在表的一端进行插入操作、而在另一端进行删除操作。在另一端进行删除操作。第三章第三章 栈和队列栈和队列第3页，本讲稿共90页3.1 栈的逻辑结构1栈的定义栈的定义栈的示意图栈的示意图栈：栈：限定限定仅在仅在表尾表尾进行插入和删除操作的进行插入和删除操作的线性表线性表。允许插入和删除的一端称为允许插入和删除的一端称为栈顶栈顶，另一个固定端称为，另一个固定端称为栈底栈底。（a1,a2,an）出栈出栈 a1 a2 a n-1 a n栈顶栈顶栈顶栈顶toptop栈底栈底栈底栈底basebase入栈入栈第4页，本讲稿共90页3.1

3、 栈的逻辑结构设栈设栈S=（a1 a1,a2,an）,则则 a1为为栈底栈底元素，元素，an为为栈顶栈顶元素元素栈也称为后进先出（栈也称为后进先出（Last In First Out）的线性表（简称）的线性表（简称为为LIFO表表）出栈出栈 a1 a2 a n-1 a n栈顶栈顶栈顶栈顶toptop栈底栈底栈底栈底basebase入栈入栈插入插入：入栈、进栈、压栈：入栈、进栈、压栈删除删除：出栈、退栈：出栈、退栈空栈：空栈：不含任何数据元素的不含任何数据元素的栈。栈。栈的操作特性：栈的操作特性：后进先出后进先出栈的示意图栈的示意图第5页，本讲稿共90页3.1 栈的逻辑结构注意：注意：注意：注意

4、：栈只是对表插入和删除操作的位置进行了限栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。制，并没有限定插入和删除操作进行的时间。有三个元素按有三个元素按a、b、c的次序依次进栈，且的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列每个元素只允许进一次栈，则可能的出栈序列有多少种？有多少种？思考：思考：思考：思考：第6页，本讲稿共90页3.1 栈的逻辑结构2、栈的抽象数据类型定义、栈的抽象数据类型定义 ADT StackData 栈中元素具有相同类型及后进先出特性，栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系Ope

5、ration InitStack（&s）初始条件：栈不存在初始条件：栈不存在 输入：无输入：无 功能：栈的初始化功能：栈的初始化 输出：无输出：无 操作结果：构造一个空栈操作结果：构造一个空栈 第7页，本讲稿共90页3.1 栈的逻辑结构DestroyStack(&s)初始条件：栈已存在初始条件：栈已存在 输入：无输入：无 功能：销毁栈功能：销毁栈 输出：无输出：无 操作结果：释放栈所占用的存储空间操作结果：释放栈所占用的存储空间Push(&s,x)初始条件：栈已存在初始条件：栈已存在 输入：元素值输入：元素值x 功能：在栈顶插入一个元素功能：在栈顶插入一个元素x 输出：如果插入不成功，抛出异常

6、输出：如果插入不成功，抛出异常 操作结果：如果插入成功，栈顶增加了一个元素操作结果：如果插入成功，栈顶增加了一个元素2、栈的抽象数据类型定义、栈的抽象数据类型定义 第8页，本讲稿共90页3.1 栈的逻辑结构Pop(&s,&x)初始条件：栈已存在初始条件：栈已存在 输入：无输入：无 功能：删除栈顶元素功能：删除栈顶元素 输出：如果删除成功，返回被删元素值输出：如果删除成功，返回被删元素值x，否则，抛出异常，否则，抛出异常 操作结果：如果删除成功，栈减少了一个元素操作结果：如果删除成功，栈减少了一个元素GetTop(s,&x)初始条件：栈已存在初始条件：栈已存在 输入：无输入：无 功能：读取当前的

7、栈顶元素功能：读取当前的栈顶元素 输出：若栈不空，返回当前的栈顶元素值输出：若栈不空，返回当前的栈顶元素值 操作结果：栈不变操作结果：栈不变2、栈的抽象数据类型定义、栈的抽象数据类型定义 第9页，本讲稿共90页3.1 栈的逻辑结构StackEmpty(s)初始条件：栈已存在初始条件：栈已存在 输入：无输入：无 功能：判断栈是否为空功能：判断栈是否为空 输出：如果栈为空，返回输出：如果栈为空，返回TRUE，否则，返回，否则，返回FALSE 操作结果：栈不变操作结果：栈不变endADT2、栈的抽象数据类型定义、栈的抽象数据类型定义 第10页，本讲稿共90页3.2 栈的顺序存储结构及实现栈的顺序存储

8、结构及实现 因栈是一种特殊的线性表，同线性表类因栈是一种特殊的线性表，同线性表类似，栈也有两种存储结构：似，栈也有两种存储结构：Q顺序存储结构顺序存储结构Q链表存储结构链表存储结构第11页，本讲稿共90页3.2 栈的顺序存储结构及实现栈的顺序存储结构及实现顺序栈顺序栈栈的顺序存储结构栈的顺序存储结构如何改造数组实现栈的顺序存储？如何改造数组实现栈的顺序存储？确定用数组的哪一端表示栈底。确定用数组的哪一端表示栈底。附设指示器附设指示器top指示栈顶元素在数组中的位置。指示栈顶元素在数组中的位置。0 1 2 3 4 5 6 7 8a1top第12页，本讲稿共90页 （a）空栈）空栈(top=bas

9、e或或top=-1)；（b）插入元素）插入元素A后；后；（c）插入元素）插入元素B、C、D、E后后(栈满栈满)；（d）删除元素）删除元素E、D后后 （e）删除元素）删除元素C、B、A后（后（栈空栈空）top（b）栈中元素与栈顶指针的变化栈中元素与栈顶指针的变化:3.2 栈的顺序存储结构及实现栈的顺序存储结构及实现顺序栈的几种状态顺序栈的几种状态topA（c）DCBEtop（d）CBAtopbase（e）topbase（a）43210A第13页，本讲稿共90页“上溢上溢”-当当s.top=stacksize-1表示栈满，此时，再表示栈满，此时，再做进栈运算必定产生空间溢出，简称做进栈运算必定产生

10、空间溢出，简称“上溢上溢”“下溢下溢”-当当s.top=s.base(或或s.top=-1）时表示栈时表示栈空，此时再做退栈运算也将产生溢出，简称空，此时再做退栈运算也将产生溢出，简称“下溢下溢”。上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象上溢是一种出错状态，应该设法避免之；下溢则可能是正常现象，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢，因为栈在程序中使用时，其初态或终态都是空栈，所以下溢常常用来作为程序控制转移的条件。常常用来作为程序控制转移的条件。3.2 栈的顺序存储结构及实现栈的顺序存储结构及实现第14页，本讲稿共90页-（简易版）简易版）#define max

11、size 100typedef struct /顺序栈定义 ElemTypeelemmaxsize;/栈数组 int top;/栈顶指示器 SqStack;3.2 栈的顺序存储结构及实现栈的顺序存储结构及实现top(栈空栈空栈空栈空:top=-1:top=-1)elem顺序栈的顺序存储类型描述顺序栈的顺序存储类型描述第15页，本讲稿共90页顺序栈的顺序存储表示顺序栈的顺序存储表示-（完整版）（完整版）#define stack_Init_Size100#defineStackIncreament10typedef struct /顺序栈定义 ElemType*base;/栈底指示器ElemTy

12、pe*top;/栈顶示器 int StackSize;/当前已分配的存储空间 SqStack;3.2 栈的顺序存储结构及实现栈的顺序存储结构及实现Top(栈空：栈空：top=base)base第16页，本讲稿共90页顺序栈的实现顺序栈的实现（1）初始化栈）初始化栈void initStack(SqStack&s)/*创建一个空栈由指针创建一个空栈由指针S指出指出*/s.base=(elemtype*)malloc(sizeof(elemtype);if(!s.base)return FALSE;s.top=s.base;return ok;3.2 栈的顺序存储结构及实现栈的顺序存储结构及实现第

13、17页，本讲稿共90页int PushStack(SqStack&s,Elemtype x)/*将元素将元素x插入到栈插入到栈s中，作为中，作为s的新栈顶的新栈顶*/if(s.top=stacksize)return FALSE;/*栈满栈满*/s.elems.top=x;s.top+;return TRUE;（2）入栈操作）入栈操作3.2 栈的顺序存储结构及实现栈的顺序存储结构及实现时间复杂度？时间复杂度？第18页，本讲稿共90页 int PopStack(SqStack&s,Elemtype&x)/*若栈若栈s不为空，则删除栈顶元素不为空，则删除栈顶元素*/if(s.topdata);链栈

14、的实现链栈的实现-取栈顶元素取栈顶元素3.3 栈的链式存储结构及实现栈的链式存储结构及实现第33页，本讲稿共90页3.3 栈的链式存储结构及实现栈的链式存储结构及实现lsanan-1a1 xpls为为什什么么没没有有判判断断栈栈满满？算法描述：算法描述：Void push(LkStack&ls,elemtype x)p=(snode*)malloc(sizeof(snode);pdata=x;pnext=ls;ls=p;return ok;链栈的实现链栈的实现-入栈入栈第34页，本讲稿共90页算法描述算法描述void pop(LkStack&ls,elemtype&x)if(ls=NULL)r

15、eturn NULL;p=ls;x=p-data;ls=ls-next;free(p);return ok;链栈的实现链栈的实现-出栈出栈lsanan-1a1lsp ls+可以吗？可以吗？3.3 栈的链式存储结构及实现栈的链式存储结构及实现第35页，本讲稿共90页3.3 栈的链式存储结构及实现栈的链式存储结构及实现顺序栈和链栈的比较顺序栈和链栈的比较时间性能：时间性能：相同，都是常数时间相同，都是常数时间O(1)。空间性能：空间性能：顺序栈：有元素个数的限制和空间浪费的问题。顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间链栈：没有栈满的问题，只有当内存没

16、有可用空间时才会出现满的情况，但是每个元素都需要一个指针时才会出现满的情况，但是每个元素都需要一个指针域，从而产生了结构性开销。域，从而产生了结构性开销。总之，当栈的使用过程中元素总之，当栈的使用过程中元素个数变化个数变化较大时，用链栈较大时，用链栈是适宜的，反之，应该采用顺序栈。是适宜的，反之，应该采用顺序栈。第36页，本讲稿共90页 由于栈结构具有后进先出的固有特性，由于栈结构具有后进先出的固有特性，致使栈成为程序设计中常用的工具。以致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。下是几个栈应用的例子。3.4 栈的应用栈的应用第37页，本讲稿共90页3.4 栈的应用栈的应用1.借助

17、栈来实现单链表逆置算法借助栈来实现单链表逆置算法【分析】【分析】利用栈的特征，先沿着链表从头至尾扫利用栈的特征，先沿着链表从头至尾扫描一遍，将链表的每个结点的描一遍，将链表的每个结点的data域的值域的值依次进栈，然后再沿着链表从头至尾扫描依次进栈，然后再沿着链表从头至尾扫描一遍，同时栈中元素依次出栈，并填入到一遍，同时栈中元素依次出栈，并填入到链表的每个结点的链表的每个结点的data域中。域中。第38页，本讲稿共90页算法算法Status reverse(LinkList&L)Lkstack ls;elemtype x;initstack(ls);/初始化栈初始化栈 p=L-next;whi

18、le(p!=null)push(ls,p-data);p=p-next;p=L-next;while(!emptystack(ls)pop(ls,x);p-data=x;p=p-next;第39页，本讲稿共90页2.2.行编辑程序行编辑程序 一个简单的行编辑程序功能是：接受用户从终端输入的程序或一个简单的行编辑程序功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出差错不能保证不出差错,如原为输入：如原为输入：while(*s)却输成：却输成：whliilre(s)。在编辑程序中，设立一个输入

19、缓冲区，用于接受用户输在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。错误，并在发现有误时可以及时更正。比如：比如：whli#ilr#e(s#*s)whli#ilr#e(s#*s)outchaputchar(*s=#+)outchaputchar(*s=#+)实际上为：实际上为：while(*s)while(*s)putchar(*s+)putchar(*s+)3.4 栈的应用栈的应用第40页，本讲稿共90页算法如下算法如下:void lineedit()/vo

20、id lineedit()/利用字符栈利用字符栈S S，从终端接收一行，从终端接收一行并传送至调用过程的数据区并传送至调用过程的数据区 initstack(s);/initstack(s);/构造空栈构造空栈S S ch=gether();/ch=gether();/从终端接收一个字符从终端接收一个字符 while(ch!=eof)/while(ch!=eof)/若全文未结束若全文未结束 while(ch!=eof&ch!=while(ch!=eof&ch!=nn)switch(ch)case#:pop(s,c);break;/仅当栈非空时退栈仅当栈非空时退栈 case :clearstack

21、(s);break;/重置重置s为空栈为空栈 default:push(s,ch);break;/有效字符进栈，未有效字符进栈，未考虑栈满情形考虑栈满情形 第41页，本讲稿共90页 ch=getchar();/从终端接收下一个字符从终端接收下一个字符 /将从栈底到栈顶的栈内字符传送至调用过程的数据区将从栈底到栈顶的栈内字符传送至调用过程的数据区 clearstack(s);/重置重置s为空栈为空栈 if(ch!=eof)ch=gethar();destroystack(s);/结束字符输入后销毁栈结束字符输入后销毁栈 第42页，本讲稿共90页3.5 队队 列列QQ定义定义 队列是只允许在一端进

22、行插入操作，在另一队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表端进行删除操作的线性表 允许插入（也称入队、进队）的一端叫做队允许插入（也称入队、进队）的一端叫做队尾尾(rearrear)，允许删除（也称出队）的一端叫做，允许删除（也称出队）的一端叫做，允许删除（也称出队）的一端叫做，允许删除（也称出队）的一端叫做队头队头队头队头(frontfront)。空队列：空队列：不含任何数据元素的队列。不含任何数据元素的队列。3.5.1 队列的逻辑结构队列的逻辑结构（a1,a2,an）队尾队尾队头队头第43页，本讲稿共90页3.5 队队 列列队列的操作特性：队列的操作特性：先进先出先进先

23、出(FIFO,First In First Out)a1a2a3入队入队队尾队尾队头队头出队出队队头队头队列的逻辑结构队列的逻辑结构（a1,a2,an）队尾队尾队头队头栈与队列有什么异同点？栈与队列有什么异同点？第44页，本讲稿共90页3.5.1 队列的逻辑结构队列的逻辑结构队列的抽象数据类型定义队列的抽象数据类型定义 ADT Queue Data 队列中元素具有相同类型及先进先出特性，队列中元素具有相同类型及先进先出特性，相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系Operation InitQueue(&Q)初始条件：队列初始条件：队列Q不存在不存在 输入：无输入：无 功能：初始化

24、队列功能：初始化队列 输出：无输出：无 操作结果：创建一个空队列操作结果：创建一个空队列第45页，本讲稿共90页3.5.1 队列的逻辑结构队列的逻辑结构 DestroyQueue(&Q)初始条件：队列初始条件：队列Q已存在已存在 输入：无输入：无 功能：销毁队列功能：销毁队列 输出：无输出：无 操作结果：释放队列所占用的存储空间操作结果：释放队列所占用的存储空间 EnQueue(&Q,e)初始条件：队列初始条件：队列Q已存在已存在 输入：元素值输入：元素值e 功能：在队尾插入一个元素功能：在队尾插入一个元素 输出：如果插入不成功，抛出异常输出：如果插入不成功，抛出异常 操作结果：插入元素操作结

25、果：插入元素e为新的队尾元素为新的队尾元素队列的抽象数据类型定义队列的抽象数据类型定义 第46页，本讲稿共90页3.5.1 队列的逻辑结构队列的逻辑结构 DeQueue(&Q,&e)初始条件：队列初始条件：队列Q已存在已存在 输入：无输入：无 功能：删除队头元素功能：删除队头元素 输出：如果删除成功，返回被删元素值输出：如果删除成功，返回被删元素值 操作结果：删除操作结果：删除Q的队头元素，并用的队头元素，并用e返回其值返回其值 GetQueue(Q)初始条件：队列初始条件：队列Q已存在已存在 输入：无输入：无 功能：读取队头元素功能：读取队头元素 输出：若队列不空，返回队头元素输出：若队列不

26、空，返回队头元素 操作结果：队列不变操作结果：队列不变队列的抽象数据类型定义队列的抽象数据类型定义 第47页，本讲稿共90页3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 链队列：链队列：队列的链式存储结构队列的链式存储结构 队头指针即为链表的头指针队头指针即为链表的头指针如何改造单链表实现队列的链式存储？如何改造单链表实现队列的链式存储？rearfronthead1、队列的链队列、队列的链队列链队列是否需要附设头结点吗？链队列是否需要附设头结点吗？第48页，本讲稿共90页3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 Q.frontQ.rear带头结点的链队列带头结点

27、的链队列非空链队列非空链队列空链队列空链队列Q.frontQ.rear第49页，本讲稿共90页3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 2、链队列的类型定义、链队列的类型定义typedef struct Qnode /*定义队列的结点结构定义队列的结点结构*/ElemTypedata;/队列结点数据队列结点数据struct Qnode*next;/结点链指针结点链指针QNode,*QueuePtr;typedefstruct /*链队列结构链队列结构*/QueuePtrfront;/*队头指针队头指针*/QueuePtrrear;/*队尾指针队尾指针*/LkQueue;定义一

28、个指向链队列的指针：定义一个指向链队列的指针：LkQueue *q;第50页，本讲稿共90页int initLkqueue(Lkqueue&q)/*创建一个空链队列创建一个空链队列q*/q.front=(Queueptr)malloc(sizeof(Qnode if(!q.front)return FALSE;q.front-next=NULL;/头结点无后继头结点无后继q.rear=q.front;/队尾也指向头结点队尾也指向头结点 return ok;3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 Q.rearQ.front3、链队列的实现、链队列的实现-初始化队列初始化队列第

29、51页，本讲稿共90页3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 xs链队列的实现链队列的实现入队入队fronta1anrearrearfront xsrearrear算法描述：算法描述：s-next=NULL;rear-next=s;rear=s;（一）带头结点的链队列（一）带头结点的链队列插入元素插入元素x为为Q的新的队尾元素的新的队尾元素第52页，本讲稿共90页3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 xs链队列的实现链队列的实现入队入队fronta2anrearrear算法描述：算法描述：s-next=NULL;rear-next=s;rear=s;如

30、何没有头结点会怎样？如何没有头结点会怎样？a1（二）无头结点的链队列（二）无头结点的链队列第53页，本讲稿共90页3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 xs链队列的实现链队列的实现入队入队fronta2anrearrearfront=rear=NULL xsrear算法描述：算法描述：s-next=NULL;rear=s;front=s;如何没有头结点会怎样？如何没有头结点会怎样？a1front（二）无头结点的链队列（二）无头结点的链队列第54页，本讲稿共90页void EnQueue(LkQueue&Q,Elemtype x)/*将元素将元素x插入到链队列插入到链队列Q

31、中，作为中，作为Q的新队尾的新队尾*/if(s=(Queueptr)malloc(sizeof(Qnode)=NULL)return FALSE;s-data=x;s-next=NULL;Q.rear-next=s;Q.rear=s;return OK;链队列的实现链队列的实现入队入队3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 第55页，本讲稿共90页3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 链队列的实现链队列的实现出队出队fronta1a2anrearp算法描述：算法描述：p=front-next;front-next=p-next;第56页，本讲稿共90页

32、3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 链队列的实现链队列的实现出队出队fronta1a2anrearp考虑边界情况：队列中只有一个元素？考虑边界情况：队列中只有一个元素？fronta1prearrear算法描述：算法描述：if(p-next=NULL)rear=front;如何判断边界情况？如何判断边界情况？第57页，本讲稿共90页Void DeQueue(LkQueue&Q,Elemtype x)/*若链队列若链队列q不为空，则删除队头元素，返回其元素值不为空，则删除队头元素，返回其元素值*/if(Q.front-next=NULL)return NULL;P=Q.fr

33、ont-next;x=p-data;Q.front-next=p-next;If(p-next=null)Q.rear=Q.front;free(p);return x;链队列的实现链队列的实现出队出队3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 也可用也可用Q.rear=p描述描述第58页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 01234入队入队出队出队顺序队列：顺序队列：队列的顺序存储结构队列的顺序存储结构如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2a3a4依次入队依次入队a1a2a3a4rearrear

34、 rear rear入队操作时间性能为入队操作时间性能为O(1)第59页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2依次出队依次出队队列的顺序存储结构队列的顺序存储结构01234入队入队出队出队a1a2a3a4rear第60页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2依次出队依次出队队列的顺序存储结构队列的顺序存储结构01234入队入队出队出队a2a3a4rear第61页

35、，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2依次出队依次出队01234入队入队出队出队a3a4rear出队操作时间性能为出队操作时间性能为O(n)队列的顺序存储结构队列的顺序存储结构第62页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 队列的顺序存储结构队列的顺序存储结构如何改进出队的时间性能？如何改进出队的时间性能？放宽队列的所有元素必须存储在数组的前放宽队列的所有元素必须存储在数组的前n个单元这一条个单元这一条件件，只要求队列的元素存储在数组中连续的

36、位置。，只要求队列的元素存储在数组中连续的位置。设立两个指示器：一个为指向队头元素位置的指示器设立两个指示器：一个为指向队头元素位置的指示器frontfront，另一个为指向队尾的元素位置的指示器，另一个为指向队尾的元素位置的指示器rearrear。a1 a2 an-1，anfrontrear第63页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 队列的顺序存储结构队列的顺序存储结构01234入队入队出队出队例：例：a1a2a3a4依次入队依次入队a1a2a3a4rearrear rear rear入队操作时间性能仍为入队操作时间性能仍为O(1)front rear

37、第64页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 例：例：a1a2依次出队依次出队队列的顺序存储结构队列的顺序存储结构01234入队入队出队出队a1a2a3a4rearfront front front出队操作时间性能提高为出队操作时间性能提高为O(1)第65页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 例：例：a1a2依次出队依次出队队列的顺序存储结构队列的顺序存储结构01234入队入队出队出队a3a4rearfront队列的移动有什么特点？队列的移动有什么特点？整个队列向数组下标较大方向移动整个队列向数组下标较大方向移动单向

38、移动性单向移动性第66页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 假溢出：假溢出：当元素被插入到数组中下标最大的位置上之后，当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做这种现象叫做假溢出假溢出。队列的顺序存储结构队列的顺序存储结构继续入队会出现什么情况？继续入队会出现什么情况？01234入队入队出队出队a3a4rearfronta5rear第67页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 循环队列：循环队列：将存储

39、队列的数组头尾相接。将存储队列的数组头尾相接。队列的顺序存储结构队列的顺序存储结构如何解决假溢出？如何解决假溢出？01234入队入队出队出队a3a4fronta5rearreara6第68页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 队列的顺序存储结构及实现队列的顺序存储结构及实现 如何解决假溢出？如何解决假溢出？循环队列循环队列第69页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q第一种情况第一种情况用队头指针用队头指针Q.front指向队头元素所在的单指向队头元素所在的单元，用队尾指针元，用队尾指针Q.rear指向队尾元素所在

40、指向队尾元素所在的单元的单元 第70页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q第二种情况第二种情况-队头指针队头指针Q.front指向队头指向队头元素所在单元的前一个单元元素所在单元的前一个单元，队尾指针，队尾指针Q.rear指向队尾元素所在的单元指向队尾元素所在的单元 第71页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q第三种情况第三种情况-队尾指针队尾指针Q.rear指向队尾指向队尾元素所在单元的下一个单元元素所在单元的下一个单元，队头指针，队头指针Q.front指向队头元素所在的单元指向队头元素所在的单元第72页，本

41、讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q在循环数组中，不论用哪一种方式来指示队头与队尾元素，在循环数组中，不论用哪一种方式来指示队头与队尾元素，我们都要我们都要解决两个问题解决两个问题:Q1.当当Q.rear或或Q.front=maxsize-1时，再加时，再加1怎样回到怎样回到“0”的位置的位置？Q2.如何表示满队列和空队列？如何表示满队列和空队列？对于第一个问题，可采用对于第一个问题，可采用“%”运算运算-取模取模(余数余数)运算来解决运算来解决 让队头、队尾指针加让队头、队尾指针加1后取余运算，就能实现自动回后取余运算，就能实现自动回“0”，即，即 Q.

42、front=（Q.front+1）%maxsize Q.rear=(Q.rear+1)%maxsize注：循环队列的下标序号为注：循环队列的下标序号为0.maxsize-1队满、队空队满、队空第73页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q2.如何表示满队列和空队列？如何表示满队列和空队列？如图设如图设MaxSize=6，队列中已有，队列中已有3个元素。我们用上述个元素。我们用上述3种方法来指示队头和队尾元素，分别如图种方法来指示队头和队尾元素，分别如图 所示所示(1)(2)(3)第74页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构

43、及实现 Q现在，另有现在，另有3个元素个元素a4,a5,a6相继入队，相继入队，使队列呈使队列呈满满的状态的状态 队满：队满：Q.rear=Q.front第75页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q如果如果3个元素个元素a1,a2,a3相继出队，使队列相继出队，使队列呈呈“空空”的状的状 态态队空：队空：Q.rear=Q.front第76页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q队满队满、队空的解决办法、队空的解决办法Q通常有两种处理方法来解决这个问题。通常有两种处理方法来解决这个问题。Q方法一方法一：另设一个标志

44、位以区别队列是：另设一个标志位以区别队列是“空空”还是还是“满满”。比如设一个布尔量来注。比如设一个布尔量来注明队列是空还是满。明队列是空还是满。Q方法二方法二：少用一个元素空间，约定以：少用一个元素空间，约定以“以以队尾指针加队尾指针加1等于队头指针等于队头指针”作为队列呈作为队列呈“满满”状态的标志。状态的标志。即（即（Q.rear+1）%maxsize=Q.front/队满队满 Q.rear=Q.front /队空队空约定：约定：约定：约定：采用第二种方法采用第二种方法采用第二种方法采用第二种方法第77页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q改进后

45、的队满情况改进后的队满情况 第78页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q循环队列类型说明如下：循环队列类型说明如下：#define MAXSIZE 100 /最大队列长度最大队列长度typedef struct elemtype dataMAXSIZE;/队列元素队列元素 Int front;/头指示器，若队列不空，指向队列头头指示器，若队列不空，指向队列头元素元素 Int rear;/尾指示器，若队列不空，指向队列尾元素尾指示器，若队列不空，指向队列尾元素的下一个位置的下一个位置cirqueue;第79页，本讲稿共90页status initqueu

46、e(cirqueue&Q)Q.front=Q.rear=0;return ok;（1）队列初始化）队列初始化循环队列的实现循环队列的实现3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 第80页，本讲稿共90页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现(2)入队列入队列 将一个新元素将一个新元素x插入到队尾插入到队尾Q步骤步骤当当(Q.rear+1）%maxsize Q.front时，按时，按以下步骤：以下步骤：（1）Q.dataQ.rear=x;(2)Q.rear=(Q.rear+1)%maxsize;第81页，本讲稿共90页算法算法 status Enqueue(

47、cirqueue&Q,elemtype x)if(Q.rear+1）%maxsize=Q.front)error(“queue overflow”)Q.dataQ.rear=x;/新元素新元素x键入队尾键入队尾 Q.rear=(Q.rear+1)%maxsize;/队尾后移队尾后移 return ok;(2)入队列入队列3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 第82页，本讲稿共90页（3）出队列）出队列Q当当Q.frontQ.rear时，按以下步骤：时，按以下步骤：（1）x=Q.dataQ.front (2)Q.front=(Q.front+1)%maxsize;3.5.3

48、队列的顺序存储结构及实现队列的顺序存储结构及实现 第83页，本讲稿共90页算法算法 status Dequeue(cirqueue&Q)if(Q.front=Q.rear)return ERROR;x=Q.dataq.front;/取出队头元素取出队头元素 Q.front=(Q.front+1)%maxsize;/队头指针加队头指针加1 return ok;（3）出队列）出队列3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 第84页，本讲稿共90页3.5 队列队列循环队列和链队列的比较循环队列和链队列的比较时间性能时间性能:循环队列和链队列的基本操作都需要常数时间循环队列和链队列的

49、基本操作都需要常数时间O(1)。空间性能空间性能:循循环环队队列列：必必须须预预先先确确定定一一个个固固定定的的长长度度，所所以以有有存存储元素个数的限制和空间浪费的问题。储元素个数的限制和空间浪费的问题。链链队队列列：没没有有队队列列满满的的问问题题，只只有有当当内内存存没没有有可可用用空空间间时时才才会会出出现现队队列列满满，但但是是每每个个元元素素都都需需要要一一个个指指针针域域，从从而而产生了结构性开销。产生了结构性开销。第85页，本讲稿共90页 其它队列除除了了栈栈和和队队列列之之外外，还还有有一一种种限限定定性性数数据据结结构构，它它们是双端队列（们是双端队列（double-end

50、ed queue）。）。端1端2插入删除双端队列的示意图双端队列的示意图a1a2aia0an-1删除插入插入双双端端队队列列-限限定定插插入入和和删删除除操操作作在在线线性性表表的的两两端端进进行行，我我们们可可以以将将它它看看成成是是栈栈底底连连在在一一起起的的两两个个栈栈，但但它它与与两两个个栈栈共共享享存存储储空空间间是是不不同同的的。共共享享存存储储空空间间中中的的两两个个栈栈的的栈栈顶顶指指针针是是向向两两端端扩扩展展的的，因因而而每每个个栈栈只只需需一一个个指指针针；而而双双端端队队列列允允许许两两端端进进行行插插入入和和删删除除元元素素，因因而而每每个个端端点必须设立两个指针，如