西安电子科技大学计算机学院数据结构课件 第3章（3） .pptxVIP

第3章限定性线性表——栈和队列3.4 队列1. 队列的定义：一种先进先出的线性表。q=(a1,a2,…,an)队尾(rear)：允许插入的一端。队头(front)：允许删除的一端。空队列：不含元素的空表。队头元素：a1；队尾元素：an

第3章限定性线性表——栈和队列队列的特点先进先出(FirstInFirstOut)，简称FIFO结构。一种限定性数据结构。队列的基本运算队列初始化InitQueue(Q)。设置一个空队列入队列EnQueue(Q,e)。队列Q存在，插入e为新的队尾元素出队列DeQueue(Q,e)。Q存在且非空，删除队头元素读队头元素GetHead(Q,e)。Q存在且非空，用e返回队头元素判队列空QueueEmpty(S)。Q存在,若为空队列,返回真，（假）

第3章限定性线性表——栈和队列4.双端队列（Deque）限定插入和删除操作在表的两端进行的线性表。输出受限的双端队列：一端允许插入和删除，另一端只允许插入；输入受限的双端队列：一端允许插入和删除，另一端只允许删除。

第3章限定性线性表——栈和队列5.队列的表示和实现链队列：队列的链式表示和实现队列循环队列：队列的顺序表示和实现

第3章限定性线性表——栈和队列链队列LinkQueueQ;链队列的类型定义typedefstructQNode{QElemType data;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtr front; //队头指针QueuePtr rear; //队尾指针}LinkQueue;队空的条件：Q.front=Q.rear;(有头结点）Q.front=NULL;(无头结点)

第3章限定性线性表——栈和队列初始化InitQueue(LinkQueue Q){Q.front=Q.rear=(QueuePtr)malloc(…);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;returnOK;}

第3章限定性线性表——栈和队列入队列EnQueue(LinkQueue Q,QElemTypee){p=newQNode;if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;①Q.rear-next=p;②Q.rear=p;returnOK;}

第3章限定性线性表——栈和队列出队列DeQueue(LinkQueue Q,QElemTypee){if(Q.front==Q.rear) returnERROR;p=Q.front-next;e=p-data;①Q.front-next=p-next;(Q.front-next-next)②if(Q.reat==p) Q.rear=Q.front;deletep;returnOK;}

第3章限定性线性表——栈和队列循环队列typedefstruct{QElemType *base;front;rear;intint}SqQueue;约定：空队列Q.front=Q.rear;入队列（插入元素）Q.rear++;出队列（删除元素）Q.front++;非空队列，front指针始终指向队头元素，rear指针始终指向队尾元素的下一位置。

第3章限定性线性表——栈和队列“假溢出”

第3章限定性线性表——栈和队列将顺序队列臆造为一个环状的空间，称为循环队列

第3章限定性线性表——栈和队列①尾指针增1:Q.rear=(Q.rear+1)%MAXQSIZE;②头指针增1:Q.front=(Q.front+1)%MAXQSIZE;③队列空：Q.rear=Q.front;④队列满：a)设置一个标志位tag;b)计数器count,初值count=0;c)少占用一个元素空间，(Q.rear+1)%MAXQSIZE=Q.front;

第3章限定性线性表——栈和队列⑤循环队列中元素的个数元素个数=0; 若Q.front=Q.rear队列空Q.rear–Q.front; 若Q.rearQ.frontQ.rear–Q.front+MAXQSIZE;若Q.rearQ.frontMAXQSIZE-1. 若队满元素个数=(Q.rear–Q.front+MAXQSIZE)%MAXQSIZE

第3章限定性线性表——栈和队列初始化InitQueue(SqQueueQ){Q.base=(QElem