栈和队列队列

第3章栈和队列-队列嘉应学院数学系数据结构讲义3.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;顺序队列的操作演示flash在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。3.4.3队列的顺序实现

为充分利用向量空间，克服上述假上溢现象，可以将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（CircularQueue)。循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。循环队列的操作演示flash012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：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）；循环队列的基本运算实现null*qq.frontq.rear非空队列q.frontq.rearnull空队列*q3.4.2链队列链队列示意图

和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型：

typedef

struct

queuenode{

ElemTypedata;

struct

queuenode*next;}QueueNode;

typedefstruct{

QueueNode*front;

QueueNode*rear;}LinkQueue;

链队列的基本实现CPU资源的竞争问题。主机与外部设备之间速度不匹配的问题。服务、排队问题队列的应用讨论（代本章小结）线性表、栈与队的异同点相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表