第三章栈和队列精选文档.ppt

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

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

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

3、1 a1,a2,an）,则则 a1为为栈底栈底元素，元素，an为为栈顶栈顶元素元素栈也称为后进先出（栈也称为后进先出（Last In First Out）的线性表（简）的线性表（简称为称为LIFO表表）出栈出栈 a1 a2 a n-1 a n栈顶栈顶top栈底栈底base入栈入栈插入插入：入栈、进栈、压栈：入栈、进栈、压栈删除删除：出栈、退栈：出栈、退栈空栈：空栈：不含任何数据元素不含任何数据元素的栈。的栈。栈的操作特性：栈的操作特性：后进先出后进先出栈的示意图栈的示意图本讲稿第五页，共九十页3.1 栈的逻辑结构注意：注意：注意：注意：栈只是对表插入和删除操作的位置进行了限栈只是对表插入和删除

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

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

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

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

8、性表类似，栈也有两种存储结构：似，栈也有两种存储结构：Q顺序存储结构顺序存储结构Q链表存储结构链表存储结构本讲稿第十一页，共九十页3.2 栈的顺序存储结构及实现栈的顺序存储结构及实现顺序栈顺序栈栈的顺序存储结构栈的顺序存储结构如何改造数组实现栈的顺序存储？如何改造数组实现栈的顺序存储？确定用数组的哪一端表示栈底。确定用数组的哪一端表示栈底。附设指示器附设指示器top指示栈顶元素在数组中的位置。指示栈顶元素在数组中的位置。0 1 2 3 4 5 6 7 8a1top本讲稿第十二页，共九十页 （a）空栈）空栈(top=base或或top=-1)；（b）插入元素）插入元素A后；后；（c）插入元素）插

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

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

11、eelemmaxsize;/栈数组 int top;/栈顶指示器 SqStack;3.2 栈的顺序存储结构及实现栈的顺序存储结构及实现top(栈空栈空栈空栈空:top=-1:top=-1)elem顺序栈的顺序存储类型描述顺序栈的顺序存储类型描述本讲稿第十五页，共九十页顺序栈的顺序存储表示顺序栈的顺序存储表示-（完整版）（完整版）#define stack_Init_Size100#defineStackIncreament10typedef struct /顺序栈定义 ElemType*base;/栈底指示器ElemType*top;/栈顶示器 int StackSize;/当前已分配的存储空

12、间 SqStack;3.2 栈的顺序存储结构及实现栈的顺序存储结构及实现Top(栈空：栈空：top=base)base本讲稿第十六页，共九十页顺序栈的实现顺序栈的实现（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 栈的顺序存储结构及实现栈的顺序存储结构及实现本讲稿第十七页，共九十页int PushStack(SqStack&s,El

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

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

15、;free(p);return ok;链栈的实现链栈的实现-出栈出栈lsanan-1a1lsp ls+可以吗？可以吗？3.3 栈的链式存储结构及实现栈的链式存储结构及实现本讲稿第三十五页，共九十页3.3 栈的链式存储结构及实现栈的链式存储结构及实现顺序栈和链栈的比较顺序栈和链栈的比较时间性能：时间性能：相同，都是常数时间相同，都是常数时间O(1)。空间性能：空间性能：顺序栈：有元素个数的限制和空间浪费的问题。顺序栈：有元素个数的限制和空间浪费的问题。链栈：没有栈满的问题，只有当内存没有可用空间链栈：没有栈满的问题，只有当内存没有可用空间时才会出现满的情况，但是每个元素都需要一个指针时才会出现满

16、的情况，但是每个元素都需要一个指针域，从而产生了结构性开销。域，从而产生了结构性开销。总之，当栈的使用过程中元素总之，当栈的使用过程中元素个数变化个数变化较大时，用链栈较大时，用链栈是适宜的，反之，应该采用顺序栈。是适宜的，反之，应该采用顺序栈。本讲稿第三十六页，共九十页 由于栈结构具有后进先出的固有特性，致使由于栈结构具有后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈成为程序设计中常用的工具。以下是几个栈应用的例子。栈应用的例子。3.4 栈的应用栈的应用本讲稿第三十七页，共九十页3.4 栈的应用栈的应用1.借助栈来实现单链表逆置算法借助栈来实现单链表逆置算法【分析】【分析】

17、利用栈的特征，先沿着链表从头至尾扫利用栈的特征，先沿着链表从头至尾扫描一遍，将链表的每个结点的描一遍，将链表的每个结点的data域的值域的值依次进栈，然后再沿着链表从头至尾扫描依次进栈，然后再沿着链表从头至尾扫描一遍，同时栈中元素依次出栈，并填入到一遍，同时栈中元素依次出栈，并填入到链表的每个结点的链表的每个结点的data域中。域中。本讲稿第三十八页，共九十页算法算法Status reverse(LinkList&L)Lkstack ls;elemtype x;initstack(ls);/初始化栈初始化栈 p=L-next;while(p!=null)push(ls,p-data);p=p-

18、next;p=L-next;while(!emptystack(ls)pop(ls,x);p-data=x;p=p-next;本讲稿第三十九页，共九十页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 栈的应用栈的应用本讲稿第四十页，共九十页算法如下算法如下:void lineedit()/void lineedit()/利用字符栈利用字符栈S S，从终

20、端接收一行，从终端接收一行并传送至调用过程的数据区并传送至调用过程的数据区 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(s);break;/重置重置s为空栈为空栈 default

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

22、一端进行删除操作的线性表进行删除操作的线性表 允许插入（也称入队、进队）的一端叫做队尾允许插入（也称入队、进队）的一端叫做队尾(rear)，允许删除（也称出队）的一端叫做队，允许删除（也称出队）的一端叫做队头头(front)。空队列：空队列：不含任何数据元素的队列。不含任何数据元素的队列。3.5.1 队列的逻辑结构队列的逻辑结构（a1,a2,an）队尾队尾队头队头本讲稿第四十三页，共九十页3.5 队队 列列队列的操作特性：队列的操作特性：先进先出先进先出(FIFO,First In First Out)a1a2a3入队入队队尾队尾队头队头出队出队队头队头队列的逻辑结构队列的逻辑结构（a1,a2

23、,an）队尾队尾队头队头栈与队列有什么异同点？栈与队列有什么异同点？本讲稿第四十四页，共九十页3.5.1 队列的逻辑结构队列的逻辑结构队列的抽象数据类型定义队列的抽象数据类型定义 ADT Queue Data 队列中元素具有相同类型及先进先出特性，队列中元素具有相同类型及先进先出特性，相邻元素具有前驱和后继关系相邻元素具有前驱和后继关系Operation InitQueue(&Q)初始条件：队列初始条件：队列Q不存在不存在 输入：无输入：无 功能：初始化队列功能：初始化队列 输出：无输出：无 操作结果：创建一个空队列操作结果：创建一个空队列本讲稿第四十五页，共九十页3.5.1 队列的逻辑结构队

24、列的逻辑结构 DestroyQueue(&Q)初始条件：队列初始条件：队列Q已存在已存在 输入：无输入：无 功能：销毁队列功能：销毁队列 输出：无输出：无 操作结果：释放队列所占用的存储空间操作结果：释放队列所占用的存储空间 EnQueue(&Q,e)初始条件：队列初始条件：队列Q已存在已存在 输入：元素值输入：元素值e 功能：在队尾插入一个元素功能：在队尾插入一个元素 输出：如果插入不成功，抛出异常输出：如果插入不成功，抛出异常 操作结果：插入元素操作结果：插入元素e为新的队尾元素为新的队尾元素队列的抽象数据类型定义队列的抽象数据类型定义 本讲稿第四十六页，共九十页3.5.1 队列的逻辑结构

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

26、列的链式存储结构及实现队列的链式存储结构及实现 链队列：链队列：队列的链式存储结构队列的链式存储结构 队头指针即为链表的头指针队头指针即为链表的头指针如何改造单链表实现队列的链式存储？如何改造单链表实现队列的链式存储？rearfronthead1、队列的链队列、队列的链队列链队列是否需要附设头结点吗？链队列是否需要附设头结点吗？本讲稿第四十八页，共九十页3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 Q.frontQ.rear带头结点的链队列带头结点的链队列非空链队列非空链队列空链队列空链队列Q.frontQ.rear本讲稿第四十九页，共九十页3.5.2队列的链式存储结构及实现队列

27、的链式存储结构及实现 2、链队列的类型定义、链队列的类型定义typedef struct Qnode /*定义队列的结点结构定义队列的结点结构*/ElemTypedata;/队列结点数据队列结点数据struct Qnode*next;/结点链指针结点链指针QNode,*QueuePtr;typedefstruct /*链队列结构链队列结构*/QueuePtrfront;/*队头指针队头指针*/QueuePtrrear;/*队尾指针队尾指针*/LkQueue;定义一个指向链队列的指针：定义一个指向链队列的指针：LkQueue *q;本讲稿第五十页，共九十页int initLkqueue(Lkqu

28、eue&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、链队列的实现、链队列的实现-初始化队列初始化队列本讲稿第五十一页，共九十页3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 xs链队列的实现链队列的实现入队入队fronta

29、1anrearrearfront xsrearrear算法描述：算法描述：s-next=NULL;rear-next=s;rear=s;（一）带头结点的链队列（一）带头结点的链队列插入元素插入元素x为为Q的新的队尾元素的新的队尾元素本讲稿第五十二页，共九十页3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 xs链队列的实现链队列的实现入队入队fronta2anrearrear算法描述：算法描述：s-next=NULL;rear-next=s;rear=s;如何没有头结点会怎样？如何没有头结点会怎样？a1（二）无头结点的链队列（二）无头结点的链队列本讲稿第五十三页，共九十页3.5.2队

30、列的链式存储结构及实现队列的链式存储结构及实现 xs链队列的实现链队列的实现入队入队fronta2anrearrearfront=rear=NULL xsrear算法描述：算法描述：s-next=NULL;rear=s;front=s;如何没有头结点会怎样？如何没有头结点会怎样？a1front（二）无头结点的链队列（二）无头结点的链队列本讲稿第五十四页，共九十页void EnQueue(LkQueue&Q,Elemtype x)/*将元素将元素x插入到链队列插入到链队列Q中，作为中，作为Q的新队尾的新队尾*/if(s=(Queueptr)malloc(sizeof(Qnode)=NULL)re

31、turn FALSE;s-data=x;s-next=NULL;Q.rear-next=s;Q.rear=s;return OK;链队列的实现链队列的实现入队入队3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 本讲稿第五十五页，共九十页3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 链队列的实现链队列的实现出队出队fronta1a2anrearp算法描述：算法描述：p=front-next;front-next=p-next;本讲稿第五十六页，共九十页3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 链队列的实现链队列的实现出队出队fronta1a2anrea

32、rp考虑边界情况：队列中只有一个元素？考虑边界情况：队列中只有一个元素？fronta1prearrear算法描述：算法描述：if(p-next=NULL)rear=front;如何判断边界情况？如何判断边界情况？本讲稿第五十七页，共九十页Void DeQueue(LkQueue&Q,Elemtype x)/*若链队列若链队列q不为空，则删除队头元素，返回其元素值不为空，则删除队头元素，返回其元素值*/if(Q.front-next=NULL)return NULL;P=Q.front-next;x=p-data;Q.front-next=p-next;If(p-next=null)Q.rear

33、=Q.front;free(p);return x;链队列的实现链队列的实现出队出队3.5.2队列的链式存储结构及实现队列的链式存储结构及实现 也可用也可用Q.rear=p描述描述本讲稿第五十八页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 01234入队入队出队出队顺序队列：顺序队列：队列的顺序存储结构队列的顺序存储结构如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2a3a4依次入队依次入队a1a2a3a4rearrear rear rear入队操作时间性能为入队操作时间性能为O(1)本讲稿第五十九页，共九十页3.5.3队列的顺序存储结

34、构及实现队列的顺序存储结构及实现 如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2依次出队依次出队队列的顺序存储结构队列的顺序存储结构01234入队入队出队出队a1a2a3a4rear本讲稿第六十页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 如何改造数组实现队列的顺序存储？如何改造数组实现队列的顺序存储？例：例：a1a2依次出队依次出队队列的顺序存储结构队列的顺序存储结构01234入队入队出队出队a2a3a4rear本讲稿第六十一页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 如何改造数组实现队列的顺序存储？如何

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

36、个为指向队头元素位置的指示器frontfront，另一个为指向队尾的元素位置的指示器另一个为指向队尾的元素位置的指示器rearrear。a1 a2 an-1，anfrontrear本讲稿第六十三页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 队列的顺序存储结构队列的顺序存储结构01234入队入队出队出队例：例：a1a2a3a4依次入队依次入队a1a2a3a4rearrear rear rear入队操作时间性能仍为入队操作时间性能仍为O(1)front rear本讲稿第六十四页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 例：例：a1a2依次出队依

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

38、：假溢出：当元素被插入到数组中下标最大的位置上之后，队列当元素被插入到数组中下标最大的位置上之后，队列的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现的空间就用尽了，尽管此时数组的低端还有空闲空间，这种现象叫做象叫做假溢出假溢出。队列的顺序存储结构队列的顺序存储结构继续入队会出现什么情况？继续入队会出现什么情况？01234入队入队出队出队a3a4rearfronta5rear本讲稿第六十七页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 循环队列：循环队列：将存储队列的数组头尾相接。将存储队列的数组头尾相接。队列的顺序存储结构队列的顺序存储结构如何解决假溢出？如何解

39、决假溢出？01234入队入队出队出队a3a4fronta5rearreara6本讲稿第六十八页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 队列的顺序存储结构及实现队列的顺序存储结构及实现 如何解决假溢出？如何解决假溢出？循环队列循环队列本讲稿第六十九页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q第一种情况第一种情况用队头指针用队头指针Q.front指向队头元素所在的单指向队头元素所在的单元，用队尾指针元，用队尾指针Q.rear指向队尾元素所在指向队尾元素所在的单元的单元 本讲稿第七十页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存

40、储结构及实现 Q第二种情况第二种情况-队头指针队头指针Q.front指向队头指向队头元素所在单元的前一个单元元素所在单元的前一个单元，队尾指针，队尾指针Q.rear指向队尾元素所在的单元指向队尾元素所在的单元 本讲稿第七十一页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q第三种情况第三种情况-队尾指针队尾指针Q.rear指向队尾指向队尾元素所在单元的下一个单元元素所在单元的下一个单元，队头指针，队头指针Q.front指向队头元素所在的单元指向队头元素所在的单元本讲稿第七十二页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q在循环数组中，不论用哪

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

42、size注：循环队列的下标序号为注：循环队列的下标序号为0.maxsize-1队满、队空队满、队空本讲稿第七十三页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q2.如何表示满队列和空队列？如何表示满队列和空队列？如图设如图设MaxSize=6，队列中已有，队列中已有3个元素。我们用上述个元素。我们用上述3种方法来指示队头和队尾元素，分别如图种方法来指示队头和队尾元素，分别如图 所示所示(1)(2)(3)本讲稿第七十四页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q现在，另有现在，另有3个元素个元素a4,a5,a6相继入队，相继入队，使队列呈使

43、队列呈满满的状态的状态 队满：队满：Q.rear=Q.front本讲稿第七十五页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q如果如果3个元素个元素a1,a2,a3相继出队，使队列相继出队，使队列呈呈“空空”的状的状 态态队空：队空：Q.rear=Q.front本讲稿第七十六页，共九十页3.5.3队列的顺序存储结构及实现队列的顺序存储结构及实现 Q队满队满、队空的解决办法、队空的解决办法Q通常有两种处理方法来解决这个问题。通常有两种处理方法来解决这个问题。Q方法一方法一：另设一个标志位以区别队列是：另设一个标志位以区别队列是“空空”还是还是“满满”。比如设一个布尔量来

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

45、实现队列的顺序存储结构及实现 Q循环队列类型说明如下：循环队列类型说明如下：#define MAXSIZE 100 /最大队列长度最大队列长度typedef struct elemtype dataMAXSIZE;/队列元素队列元素 Int front;/头指示器，若队列不空，指向队列头元头指示器，若队列不空，指向队列头元素素 Int rear;/尾指示器，若队列不空，指向队列尾元素的下尾指示器，若队列不空，指向队列尾元素的下一个位置一个位置cirqueue;本讲稿第七十九页，共九十页status initqueue(cirqueue&Q)Q.front=Q.rear=0;return ok;

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

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

48、算法算法 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队列的顺序存储结构及实现队列的顺序存储结构及实现 本讲稿第八十四页，共九十页3.5 队列队列循环队列和链队列的比较循环队列和链队列的比较时间性能时间性能:循环队列和链队列的基本操作都需要常数时间循环队列和链队列的基本操作都需要常数时间O(1)。空间性能空间性能:循循环环队队列列：必必

49、须须预预先先确确定定一一个个固固定定的的长长度度，所所以以有有存存储储元元素个数的限制和空间浪费的问题。素个数的限制和空间浪费的问题。链链队队列列：没没有有队队列列满满的的问问题题，只只有有当当内内存存没没有有可可用用空空间间时时才才会会出出现现队队列列满满，但但是是每每个个元元素素都都需需要要一一个个指指针针域域，从从而而产生了结构性开销。产生了结构性开销。本讲稿第八十五页，共九十页 其它队列除除了了栈栈和和队队列列之之外外，还还有有一一种种限限定定性性数数据据结结构构，它它们们是双端队列（是双端队列（double-ended queue）。）。端1端2插入删除双端队列的示意图双端队列的示意

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