数据结构(C语言版)3 栈及队列.ppt

循环队列 EMPTY QUEUE How to test when queue is empty? [2] [3] [2] [3] [1] [4] [1] [4] [0] [5] [0] [5] front = 0 front = 0 rear = 0 rear = 3 J2 J1 J3 循环队列 How to test when queue is full? [2] [3] [2] [3] [1] [4][1] [4] [0] [5] [0] [5] front =0 rear = 5 front =4 rear =3 J2 J3 J1 J4 J5 J6 J5 J7 J8 J9 FULL QUEUE 循环队列--区分队列的空和满 损失一个空间的方法 队列“满”的条件为 (rear+1) mod MAXSIZE=front 队列“空”的条件为 rear=front 设置标志位的方法 初始化操作即产生一个空的循环队列，此时Q-front = Q-rear=0，tag=0； 当空的循环队列中有第一个元素入队时，则tag=1，表示循环队列非空； 当tag=1且Q-front=Q-rear时，表示队满。 循环队列演示 用C语言定义的循环队列 #define? TRUE 1 #define? FALSE 0 #define MAXSIZE 50? /*队列的最大长度*/ typedef struct { ?/*?队列的元素空间*/ QueueElementType? element[MAXSIZE];? ?????? int? front;? /*头指针指示器*/ int? rear ;? /*尾指针指示器*/ }SeqQueue; 循环队列基本操作的实现 void InitQueue(SeqQueue *Q) {/* 将*Q初始化为一个空的循环队列 */ Q-front=Q-rear=0; } InitQueue Enqueue Dequeue 循环队列基本操作的实现 int Enqueue(SeqQueue *Q, QueueElementType x) {? /*将元素x入队*/ /*队列已经满了*/ if((Q-rear+1)%MAXSIZE==Q-front)? return(FALSE); Q-element[Q-rear]=x; Q-rear=(Q-rear+1)%MAXSIZE;? /* 重新设置队尾指针 */ return(TRUE);? /*操作成功*/ } InitQueue Enqueue Dequeue 循环队列基本操作的实现 int Dequeue(SeqQueue *Q, QueueElementType *x) {/*删除队头元素，用x返回其值*/ /*队列为空*/ if（Q-front==Q-rear）?return(FALSE); *x=Q-element[Q-front]; Q-front=(Q-front+1)%MAXSIZE;? /*重新设置队头指针*/ return(TRUE);? /*操作成功*/ } InitQueue Enqueue Dequeue 第三章　栈和队列 栈 队列 队列的定义 队列的表示和实现 队列的应用举例 要点小结 键盘缓冲区 缓冲区: 接收设备或应用程序使用数据之前，为暂时保存此数据而保留的内存区域。缓冲可防止数据流中断。 键