第三章 栈和队列 第二部分 队列(Queue) 2019/4/8

3.2 队列 逻辑结构：先进先出(FIFO) 只能在一端插入、另一端删除的线性表 队尾(rear)：允许插入的一端 队头(front)：允许删除的一端 a1 a2 a3…………………….an 入队 出队 front rear 队列Q=(a1, a2, ……, an) 2019/4/8

队列实现 链队列：单链表 结点定义 typedef struct QNode { QElemType data; 队首指针 front：指向头结点 队尾指针 rear：指向队尾元素 头结点 ^ …... front 队头 队尾 rear 结点定义 typedef struct QNode { QElemType data; struct QNode *next ; } QNode , *QueuePtr ; 队列定义 typedef struct { QueuePtr front , rear ; } *LinkQueue ; 2019/4/8

空队 ^ q.front q.rear x x入队 ^ q.front q.rear y入队 x y q.front q.rear ^ 2019/4/8

******队列基本操作算法****** 单链队列的基本操作--------建立空队列 Status InitQueue(LinkQueue &Q){ //构造一个空队列Q Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front) exit(OVERFLOW); //存储分配失败 return OK; } Q.front->next=NULL; 2019/4/8

单链队列的基本操作--------销毁队列 Status DestroyQueue(LinkQueue &Q){ //销毁队列Q while(Q.front){ Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; } return OK; 2019/4/8

Status EnQueue ( LinkQueue Q , QElemType e) { QueuePtr p ; 入队算法 Status EnQueue ( LinkQueue Q , QElemType e) { QueuePtr p ; p=(QueuePtr) malloc ( sizeof ( QNode ) ); p->data = e ; p->next = NULL ; Q->rear->next = p; Q->rear = p ; return OK ; } 2019/4/8

Status DeQueue (LinkQueue Q , QElemType &e) { QueuePtr p ; 出队算法 Status DeQueue (LinkQueue Q , QElemType &e) { QueuePtr p ; if( Q->front = = Q->rear ) return ERROR ;//队空判断 p = Q->front->next ; //取出队头元素值 e = p->data; Q->front->next = p->next ; if ( p->next = = NULL) Q->rear = Q->front ; free(p); return OK ; } 当队列尾元素被删除后，队尾指针也丢失 因此需要给队尾指针重新赋值：指向头结点 2019/4/8

队列的顺序存储结构 一维数组：base [MAXQSIZE] 5 4 3 2 1 front = 0 rear = 0 队空 约定： 队空 (动态分配数组空间)： typedef struct { QElemType *base ; //数组 int front , rear ; //队首，队尾(元素下标) int queuesize; //最大元素个数 } SqQueue , *SeqQueue ; 约定： rear：队尾元素后一位置 front：队头元素 初值 front = rear = 0 2019/4/8

队列的顺序存储结构 一维数组：base [MAXQSIZE] 5 5 4 4 rear 3 3 rear J3 2 2 rear J2 1 front = 0 rear = 0 1 2 3 4 5 队空 J1,J2,J3入队 1 2 3 4 5 front rear rear J3 rear J2 rear J1 入队列：base [ rear++] = e ; 2019/4/8

出队列：e= base[front++]; 队列的顺序存储结构 一维数组：base [MAXQSIZE] 1 2 3 4 5 J1,J2,J3入队 1 2 3 4 5 front J1 J2 J3 rear rear front J3 front J2 front J1 front J1,J2,J3出队 出队列：e= base[front++]; 2019/4/8

存在问题 设数组尺寸 M (＝6) 当front = 0 , rear = M 时，再有元素入队发生溢出——真溢出 rear 1 2 3 4 5 J1,J2,J3,J4,J5,J6入队 J4 J5 J6 front J1 J2 J3 J7入队？ 如何解决？ 扩充空间 2019/4/8

存在问题 设数组尺寸为 M，则： 当front  0 , rear = M 时，再有元素入队发生溢出——假溢出 rear 1 2 3 4 5 J1,J2,J3出队 J4 J5 J6 front J7入队？ 如何解决？ 扩充空间？ front 以前的空闲空间被浪费！ 2019/4/8

“假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 J1出队? 5 4 rear 3 J3 2 J2 1 front J1,J2,J3入队 1 2 3 4 5 front J1 J2 J3 rear J1出队? 2019/4/8

“假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 5 5 4 4 rear rear 3 3 J3 J3 2 2 J2 1 2 3 4 5 front J1 J2 J3 rear 1 2 3 4 5 rear J3 J2 front front＋＋？ J1出队 2019/4/8

“假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 5 5 4 4 rear rear 3 3 J3 J3 2 2 J2 1 2 3 4 5 front J1 J2 J3 rear 1 2 3 4 5 rear J3 J2 元素下移 front front 不动！ J1出队 2019/4/8

“假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 5 5 4 4 rear rear 3 3 J3 J3 2 2 J2 1 2 3 4 5 front J1 J2 J3 rear 1 2 3 4 5 rear J3 front J2 front 不动！ J1出队 2019/4/8

“假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 5 5 4 4 rear rear 3 3 J3 J3 2 2 J1,J2,J3入队 1 2 3 4 5 front J1 J2 J3 rear 1 2 3 4 5 rear J3 元素下移 front J2 front 不动！ J1出队 2019/4/8

“假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 5 5 4 4 rear rear rear -- 3 3 J3 2 J1,J2,J3入队 1 2 3 4 5 front J1 J2 J3 rear 1 2 3 4 5 rear rear -- J3 front J2 front 不动！ J1出队 2019/4/8

“假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 5 5 4 4 rear rear -- 3 3 rear J3 2 J1,J2,J3入队 1 2 3 4 5 front J1 J2 J3 rear 1 2 3 4 5 rear -- rear J3 front J2 front 不动！ J1出队 2019/4/8

“假溢出”的解决方案 I 移动元素 队首固定，每次出队剩余元素向下移动 元素移动费时！ 能否不移动元素？ 5 5 4 4 rear 3 3 J1,J2,J3入队 1 2 3 4 5 front J1 J2 J3 rear 1 2 3 4 5 rear J3 front J2 J1出队 元素移动费时！ 能否不移动元素？ 2019/4/8

“假溢出”的解决方案 II 新元素如何利用队头前的空闲数组空间？ base [ rear] = ‘J6’; rear 1 2 3 4 5 J4 J5 front J6入队 J6 base [ rear] = ‘J6’; 2019/4/8

“假溢出”的解决方案 II 新元素如何利用队头前的空闲数组空间？ base [ rear] = ‘J6’; rear ++; 1 2 3 4 5 J6 base [ rear] = ‘J6’; J5 rear ++; (rear = 6) front J4 下标将越界！(队尾将超出数组) 令其返回数组前面空闲单元 0 (rear = 0;) 2019/4/8

“假溢出”的解决方案 II 新元素如何利用队头前的空闲数组空间？ 若队尾将超出数组，令其返回数组前面空闲部分 若 rear + 1 = M，令 rear =0 1 2 3 4 5 J6 J5 front J4 rear J7入队？ J1,J2,J3出队 2019/4/8

“假溢出”的解决方案 II 新元素如何利用队头前的空闲数组空间？ 若队尾将超出数组，令其返回数组前面空闲部分 若 rear + 1 = M，令 rear =0 1 2 3 4 5 J6 J5 front J4 rear J7 J1,J2,J3出队 2019/4/8

“假溢出”的解决方案 II 新元素如何利用队头前的空闲数组空间？ 若队尾将超出数组，令其返回数组前面空闲部分 在 J6 入队时： 若 rear + 1 = M，令 rear =0 1 2 3 4 5 J6 在 J6 入队时： if ( rear ++ > M ) rear = 0; else rear ++ ; J5 front J4 rear J7 J1,J2,J3出队 2019/4/8

“假溢出”的解决方案 II 循环队列 设想队列成环形，让base[0]接在base[M-1]之后 入队： if ( rear ++ > M ) rear = 0; else rear ++ ; M-1 1 front rear …... 求模(求余)运算 入队： base[rear]=e; rear=(rear+1)%M; 出队： e=base[front]; front=(front+1)%M; 队满、队空判定条件? 2019/4/8

队空：front==rear 队满：front==rear 1 2 3 4 5 rear front J4 J5 J6 1 2 3 4 5 front J4,J5,J6出队 J4 J5 J6 1 2 3 4 5 rear front J9 J8 J7 J7,J8,J9入队 rear 一般情况 如何区分队空、队满？ 2019/4/8

J5 front J4,J5,J6出队 front J6 J4 rear front rear J7,J8,J9入队 J5 J6 J4 1 2 3 4 5 rear front J4 J5 J6 1 2 3 4 5 J4,J5,J6出队 front J4 J5 J6 1 2 3 4 5 rear front J9 J8 J7 J7,J8,J9入队 rear 一般情况 解决方案： 1、另外设一个标志以区别队空、队满 2019/4/8

J5 front J4,J5,J6出队 front J6 J4 rear front J7,J8,J9入队 J5 J6 J4 rear 1 2 3 4 5 rear front J4 J5 J6 1 2 3 4 5 J4,J5,J6出队 front front J7,J8,J9入队 J5 J6 J4 5 rear 一般情况 4 3 1 解决方案： 1、另外设一个标志以区别队空、队满 2、少用一个元素空间： 队空：front == rear 队满：(rear+1) % M == front 2 J7 J8 rear J9 入队时，已满！ 2019/4/8

优先队列 (Priority Queue) 优先队列：每次从队列中取出的是具有最高优先权的元素 例：任务的优先权及执行顺序的关系 数字越小，优先权越高 2019/4/8

小 结 队列的插入运算在表的一端进行，而删除运算却在表的另一端进行。 小 结 队列的插入运算在表的一端进行，而删除运算却在表的另一端进行。 根据队列的这一特点，在使用顺序存储结构时，用了环形队列，这样可解决假溢出问题，但要特别注意队列满和队列空的条件及描述。 2019/4/8