栈与队列的概念运用 3.4队列-链队列的表示与实现 ■问题2：设栈S和队列Q的初态均为空， ■链队列 将元素1,2,3,4,5,6依次入栈S,一元素 ,约定与类型定义：Q.front和Q.rear的含义 出栈后即进入队列Q,若这6个元素出队 typedef struct QNodef ElemType data: 次序是4,6,5,3,2,1，则栈S至少应能容纳多 struct QNode "next; 少个元素？ }QNode,*QueuePtr: 答案：5 typedef struct{ QueuePtr frot;P队头指针，指向头元素 QueuePtr rear;队思指针，指向队尾元素 654321 ·123564 }LinkQueue; 43/50 回 44/50 图 3.4队列-链队列的表示与实现 3.4队列-循环队列 ■链队列 ·循环队列 出队 入队 ,基本操作的实现 ·队列的顺序存储 Q.front 队尾 ·无队满问题（除非分影不出内存），空间可扩充 ,的定与类型定义：Q.ront和Q.rear的含义 Q.rear ,引入头结点（一定需要吗？） #define MAXQSIZE100P量大队列长度/ typedef struct ElemType base;P存情空间 4a□ int front:;”头指针，指向队列的头元素y int rear;P尾指针， 指向队见元案的下一个位量 Q.front }SqQueue;P非增量式的空间分配1 Q.rear 。副除：遵免大量的移动争头指针增1 45/50 图 46/50 图 3.4队列-循环队列 3.4队列-循环队列 ,队列的顺序存储出队 循环队列 入队 Q.front 队尾 ·假上滋的解决办法 ,盖本操作的实现 Q.rear 把顺序队列看成首尾相接的环（钟表）一循环队列 .初始化空队：Q.front=Q.rear=0; 基本操作的实现 :入队：判断是否队满：非队满时，Q.rear位置放新插 入的元素，Q.rear++ 入队：，Q.rear=(Q.rear+1%MAXQSIZE 出队：判断是否队空，非队空时，Q.ront位量为特测 出队：，Q.front=(Q.front+-1)%MAXQSIZE 除的元廉，Q.front-++ 队空条件，Q.front==Q.rear ,队空条件，Q.front==Q.rear 由于出队Q.ront道上了Q.rear ,队满条件，Q.rear==MAXQSIZE 队满条件：Q.front==Q.rear 问题：假上滋 由于入队Q.rear遭上了Q.front 47/50 图 问惠：队空和队清的质条件一样 图 88 43/50 栈与队列的概念运用 „ 问题2：设栈S和队列Q的初态均为空， 将元素1, 2, 3, 4, 5, 6依次入栈S，一元素 出栈后即进入队列Q，若这6个元素出队 次序是4,6,5,3,2,1，则栈S至少应能容纳多 少个元素？ 6 5 4 3 2 1 1 2 3 5 6 4 1 2 3 45 6 答案：5 44/50 3.4 队列–链队列的表示与实现 „ 链队列 „ 约定与类型定义：Q.front和Q.rear的含义 typedef struct QNode{ ElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct { QueuePtr front; /* 队头指针，指向头元素*/ QueuePtr rear; /* 队尾指针，指向队尾元素*/ }LinkQueue; 45/50 3.4 队列–链队列的表示与实现 „ 链队列 „ 基本操作的实现 „ 无队满问题(除非分配不出内存), 空间可扩充 „ 引入头结点(一定需要吗？) topa1 a2 an ^ Q.front Q.rear 46/50 3.4 队列–循环队列 „ 循环队列 „ 队列的顺序存储 „ 约定与类型定义：Q.front和Q.rear的含义 #define MAXQSIZE 100 /* 最大队列长度 */ typedef struct{ ElemType *base; /* 存储空间 */ int front; /* 头指针，指向队列的头元素 */ int rear; /* 尾指针， 指向队尾元素的下一个位置 */ }SqQueue; /* 非增量式的空间分配 */ „ 删除：避免大量的移动Î头指针增1 Q.front 出队 入队 a1 a2 a3 … … an Q.rear 队尾 47/50 3.4 队列–循环队列 „ 队列的顺序存储 „ 基本操作的实现 „ 初始化空队：Q.front=Q.rear=0; „ 入队：判断是否队满；非队满时，Q.rear位置放新插 入的元素，Q.rear++ „ 出队：判断是否队空，非队空时，Q.front位置为待删 除的元素，Q.front++ „ 队空条件：Q.front == Q.rear „ 队满条件：Q.rear == MAXQSIZE 问题：假上溢 Q.front 出队 入队 a1 a2 a3 … … an Q.rear 队尾 48/50 3.4 队列–循环队列 „ 循环队列 „ 假上溢的解决办法 把顺序队列看成首尾相接的环(钟表)-循环队列 „ 基本操作的实现 „ 入队：……，Q.rear = ( Q.rear+1)%MAXQSIZE „ 出队：……，Q.front = ( Q.front+1)%MAXQSIZE „ 队空条件：Q.front == Q.rear 由于出队Q.front追上了Q.rear „ 队满条件：Q.front == Q.rear 由于入队Q.rear追上了Q.front 问题：队空和队满的判断条件一样