搜索
第3章栈和队列-队列数据结构讲义信息工程学院魏洪涛Email:greattide@163.com3.4.1队列的定义队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。队列的修改是依先进先出的原则进行的。队列的基本运算1．初始化队列InitQueue(&Q)将队列Q设置成一个空队列。2．入队列EnQueue(&Q,X)将元素X插入到队尾中，也称“进队”，“插入”。3．出队列DeQueue(&Q,&e)将队列Q的队头元素删除，并用e返回其值，也称“退队”、“删除”。4．取队头元素GetHead(Q,&e)得到队列Q的队头元素之值，并用e返回其值。5．判队空QueueEmpty(Q)判断队列Q是否为空，若为空返回1，否则返回0.#defineMAXSIZE100typedefstruct{ElemTypedata[MAXSIZE];intfront;intrear;}SqQueue;顺序队列的操作演示在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。3.4.3队列的顺序实现为充分利用向量空间，克服上述假上溢现象，可以将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（CircularQueue)。循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。循环队列的操作演示012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4J5J6012345rearfront初始状态队空：front==rear队满：front==rear队空、队满无法判断：1.另外设一个标志以区别2.少用一个元素空间：队空：front==rear队满：(rear+1)%M==front队空：Q.front=Q.rear队满：Q.front=(Q.rear+1)%maxSize入队:Q.rear=(Q.rear+1)%maxSize出队:Q.front=(front+1)%maxSize;求队长:(Q.rear-Q.front+maxSize)%maxSize循环队列1）进队列算法（1）检查队列是否已满，若队满，则溢出错误；（2）将新元素赋给队尾指针所指单元；（3）将队尾指针后移一个位置（即加1）。2)出队列算法（1）检查队列是否为空，若队空，则下溢错误；（2）取队首元素的值。（3）将队首指针后移一个位置（即加1）；循环队列的基本运算实现ch3_squeue.cnull*qq.frontq.rear非空队列q.frontq.rearnull空队列*q3.4.2链队列链队列示意图链队列形式和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型：typedefstructqueuenode{ElemTypedata;structqueuenode*next;}QueueNode;typedefstruct{QueueNode*front;QueueNode*rear;}LinkQueue;链队列的实现ch3_lqueue.c链队列—元素入队链队列—元素出队CPU资源的竞争问题。主机与外部设备之间速度不匹配的问题。服务、排队问题队列的应用讨论（代本章小结）线性表、栈与队的异同点相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。②用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。