数据结构课件第三章4讲

2023/9/27计算机科学与技术教研室1/10第三章栈和队列第4讲3.4

队列

1、队列的定义及特点

2、链队列问题

3、队列的顺序表示和实现

4、循环队列

2023/9/27计算机科学与技术教研室2/103.2队列队列的定义及特点队列的定义队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)——允许插入的一端队头(front)——允许删除的一端队列的特点先进先出(FIFO)

2023/9/27计算机科学与技术教研室3/10a1a2a3…….an入队出队frontrear队列Q=(a1,a2,……,an)双端队列a1a2a3…….an端1端2入队出队出队入队2023/9/27计算机科学与技术教研室4/10链队列结点定义typedefstructQnode{QElemTypedata;structQnode*next;}Qnode,*QueuePtr;Typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;头结点^…...front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾2023/9/27计算机科学与技术教研室5/10frontrearx入队^xfrontreary入队x^yfrontrearx出队x^yfrontrear空队^frontreary出队^2023/9/27计算机科学与技术教研室6/10链队列入队算法链队列出队算法入队出队2023/9/27计算机科学与技术教研室7/10队列的顺序表示和实现实现：用一维数组实现sq[M]front=0rear=0123450队空123450frontJ1,J2,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素位置初值front=rear=0空队列条件：front==rear入队列：sq[++rear]=x;出队列：x=sq[++front];rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront2023/9/27计算机科学与技术教研室8/10存在问题设数组维数为M，则：当front=0,rear=M-1时，再有元素入队发生溢出——真溢出当front0,rear=M-1时，再有元素入队发生溢出——假溢出解决方案队首固定，每次出队剩余元素向下移动——浪费时间循环队列基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;0M-11frontrear…...…...实现：利用“模”运算入队：rear=(rear+1)%M;sq[rear]=x;出队：front=(front+1)%M;x=sq[front];队满、队空判定条件2023/9/27计算机科学与技术教研室9/10012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front==rear队满：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空