文档介绍：第4章堆栈和队列---,也称为FIFO(FirstInFirstOut)表。a1a2an•••队首指示器队尾指示器出队列进队列第4章堆栈和队列---队列的定义根据定义可见队列特点:①.它是一个线性表;②.它的操作是受限的,操作在表的两端进行,一端称为队首,另一端称为队尾;③.随着入队和出队的进行队首和队尾的位置是要变化的,所以要设置二个指示器(分为称为队首指示器front和队尾指示器rear),表示队列的变化。a1a2an•••frontrear出队列进队列第4章堆栈和队列---:QueueType;//队列数据类型Operation:voidInitQueue(QueueType&q);//初始化voidEnQueue(QueueType&q,ElemTypeitem);//入队ElemTypeOutQueue(QueueType&q);//出队ElemTypePeekQueue(QueueTypeq);//取队首元素boolEmptyQueue(QueueTypeq);//判空voidClearQueue(QueueType&q);//撤消队列EndQueue第4章堆栈和队列---①.结构定义---与单链表的结构定义类似节点结构的C语言定义structLNode{ElemTypedata;structLNode*next;};第4章堆栈和队列---队列的链式表示和实现根据队列的性质可见队列链式表示的两个要素:队首指针队尾指针a1a2an∧a3…..不带头结点的单链表frontrearq第4章堆栈和队列---队列的链式表示和实现根据队列的性质可见队列链式表示的两个要素:队首指针队尾指针链式队列的C语言定义:structQueueType{LNode*front;//队首指针LNode*reat;//队尾指针};第4章堆栈和队列---队列的链式表示和实现根据队列的性质,要定义队首和队尾指针,用结构表示:structQueueType{LNode*front;//队首指针LNode*reat;//队尾指针};用不带表头的单链表来表示当front和rear均指向NULL是为空队列a1a2an∧a3…..不带头结点的单链表frontrearq第4章堆栈和队列---队列的链式表示和实现②.基本操作的实现初始化//将front和rear置为NULLvoidInitQueue(QueueType&q){==NULL;}第4章堆栈和队列---队列的链式表示和实现判空//队列空返回true,否则返回falseboolEmptyQueue(QueueTypeq){if(==NULL)returntrue;elsereturnfalse;}==NULL;第4章堆栈和队列---队列的链式表示和实现入队boolEnQueue(QueueType&q,ElemTypex){……}a0a1an-1…..FrontrearxP②③④⑤frontrearxP②③⑤⑥队列为空的情况队列不空的情况:1)p=newLNode;2)p->data=x;3)p->next=NULL;if(!=NULL)4)->next=p;5)=p;if(==NULL)6)=p;①①