C语言《队列》--课件(PPT演示稿)

, 约定: rear 指示队尾元素; front 指示队头元素前一位置初值 front=rear=-1 空队列条件: front==rear 入队列: sq[++rear]=x; 出队列: x=sq[++front]; rear rear front rear 1 2 3 4 50 J1,J2,J3 出队 J1 J2 J3 front front front 队列的算法描述队列的算法描述?存在问题设数组维数为 M,则: –当 front=-1,rear=M-1 时,再有元素入队发生溢出——真溢出–当 front ?-1,rear=M-1 时,再有元素入队发生溢出——假溢出?解决方案–队首固定,每次出队剩余元素向下移动——浪费时间–循环队列?基本思想:把队列设想成环形,让 sq[0] 接在 sq[M-1] 之后,若 rear+1==M, 则令 rear=0; 0 M-1 1 front rear …...…... ?实现:利用“模”运算?入队: rear=(rear+1)%M; sq[rear]=x; ?出队: front=(front+1)%M; x=sq[front]; ?队满、队空判定条件队列的算法描述队列的算法描述 012 3 4 5 rear front J4 J5 J6 012 3 4 5 rear front J9 J8 J7 J4 J5 J6 012 3 4 5 rear front 初始状态 J4,J5,J6 出队 J7,J8,J9 入队队空: front==rear 队满: front==rear 解决方案: 1.另外设一个标志以区别队空、队满 2.少用一个元素空间: 队空: front==rear 队满: ( rear+1)%M==front 队列的算法描述队列的算法描述?入循环队算法出循环队算法: ?潘对空判对瞒队列的算法描述队列的算法描述