资源描述：
《《数据结构课件队列》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、栈栈的应用队列队列的应用第三章栈和队列3.4队列3.4.1抽象数据类型队列的定义队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。（a0,a1,...,ai-1,ai,ai+1,…,an-1）插入删除例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(FirstInFirstOut)的线性表，简称FIFO表。a0a1a2……an-1rear队头队尾front队
2、列的示意图队列的特点先进先出说明：第一个入队的元素在队头， 最后一个入队的元素在队尾，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素队列的抽象数据定义见书Ｐ59队列的基本运算队列可定义如下五种基本运算：1．初始化队列InitQueue(&Q)将队列Q设置成一个空队列。2．入队列EnQueue(&Q,X)将元素X插入到队尾中，也称“进队”，“插入”。3．出队列DeQueue(&Q,&e)将队列Q的队头元素删除，并用e返回其值，也称“退队”、“删除”。4．取队头元素GetHead(Q,&e)得到队列Q的队头元
3、素之值，并用e返回其值。5．判队空QueueEmpty(Q)判断队列Q是否为空，若为空返回1，否则返回0。3.4.2非循环队列和循环队列分配一块连续的存储区域来存放队列里的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置。它们的初始值在队列初始化时均应置为０。入队时将新元素插入所指的位置，然后尾指针加１。出队时，删去所指的元素，然后头指针加１并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。０
4、 １ ２ ３0123FrontrearabcFrontrear(a)队列初始为空 （b）A,B,C入队０ １ ２ ３ ０ １ ２ ３bcfrontrearfrontrear（c)a出队(d)b,c出队，队为空#defineMAXQSIZE100typedefstruct{ElemTypedata[MAXQSIZE];intfront;/*队头位置*/intrear;/*队尾位置*/}SqQueue;顺序队列的操作演示队列的顺序存储结构定义：SqQueueQQ->front存放即将要被删除的元素的下标。
5、Q->rear存放即将要被插入的元素（目前不在队列中）的下标。Q->data[Q->front]和Q->data[Q->rear]初始化：Q.front=Q.rear=0队空：Q.front=Q.rear队满：Q.rear=maxsize（假溢出）求队长：Q.rear-Q.front入队：新元素按rear指示位置加入，再将队尾指针加一，即rear=rear+1出队：将front指示的元素取出，再将队头指针加一，即front=front+1非循环队列注意：入队应考虑队满；出队应考虑队空。和栈类似，队列中亦有上溢和下溢
6、现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。为充分利用向量空间，克服上述假上溢现象，可以将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（CircularQueue)。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（Que
7、ueSize-1）时，其加1操作的结果是指向向量的下界0。显然，因为循环队列元素的空间可以被利用，除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列（环形队列）。入队和出队如何表示？由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过Q->f=Q->r来判断队列“空”还是“满”。front540312J6J7J8J4J5rear012345rearfrontJ5J6J7012345rearfrontJ4J9
8、J8J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front==rear队满：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：Q->front=Q->rear队满：(Q->rear+1)%M==Q->front队空：Q.front=Q.rear队满：Q.front
