栈和队列 程序设计—数据结构 基本概念及应用 }LinkQueue: 1)引入队头指针、队尾指针：在O(1)时间内找到操作结点 2)引入头结点：队尾插入时，使队空和队不空的结点表示一致 3)队空的判断：头、尾指针均指向头结点 4)队满的判断转变成对申请空间是否成功的判断。 2、类型说明 操作实现：初始化、入队、出队 注意：队空的判断、入队、出队依赖于队列的表示及其约定。进一步考虑： 若无头结点，此时队列的初始化、入队、队空的条件、出队等如何表示与实现？ 3.4.3循环队列 1、循环队列的定义 采用顺序表存储，约定front指向队列头元素，rear指向队尾元素的下一位置。 #define MAXQSIZE 100 /体最大队列长度*/ typedef struct ElemType *base; 体存储空间 *八 int front: 体头指针，指向队列的头元素/ int rear: 体尾指针，指向队尾元素的下一个位置/ }SqQueue; /体非增量式的空间分配*/ 2、操作实现 1)空队：Q.front==Q.rear=0 2)入队：判断是否队满，非队满时，Q.rear位置放新插入的元素，Q.rear+ 3)出队：判断是否队空，非队空时，Q.front位置为待删除的元素，Q.front+-+ 4)队空条件：Q.front=Q.rear 5)队满条件：Q.rear=MAXQSIZE-1 问题：存在假上溢（由于出队操作，队列空间的上部可能存在空闲空间） 3、假上溢的解决 将队列假想为首尾相接的环，即循环队列。 1)入队：…，Q.rear=(Q.rear+l)%MAXQSIZE 2)出队：…，Q.front=(Q.front+-1)%MAXQSIZE 3)队空条件：Q.front=Q.rear,由于出队Q.front追上了Q.rear 4)队满条件：Q.front=Q.rear,由于入队Q.rear追上了Q.font 问题：队空和队满的判断条件一样 4、如何区分队空和队满 1)设标志位：不足在于需要额外对标志位的判断及维护 2)在队列的结构中引入长度成员，在初始化队列、入队、出队操作中维护这个成员。 3)少用一个元素空间，即队满的条件如下 (Q.rear+1)%MAXQSIZE ==Q.front 进一步思考： 1)对比4中所列的3种方法在队列操作中处理的不同。 2)若循环队列数组的下标起始为-3,1或3时，如何判断队空、队满，如何实现入队、出 队？ 文档编号 完成时间 完成人 张昱 修改时间 第8页程序设计——数据结构 栈和队列 基本概念及应用 文档编号 完 成 人 张 昱 完成时间 修改时间 第 8 页 }LinkQueue; 1）引入队头指针、队尾指针：在 O(1)时间内找到操作结点 2）引入头结点：队尾插入时，使队空和队不空的结点表示一致 3）队空的判断：头、尾指针均指向头结点 4）队满的判断转变成对申请空间是否成功的判断。 2、类型说明 操作实现：初始化、入队、出队 注意：队空的判断、入队、出队依赖于队列的表示及其约定。进一步考虑： 若无头结点，此时队列的初始化、入队、队空的条件、出队等如何表示与实现？ 3.4.3 循环队列 1、循环队列的定义 采用顺序表存储，约定 front 指向队列头元素，rear 指向队尾元素的下一位置。 #define MAXQSIZE 100 /* 最大队列长度 */ typedef struct{ ElemType *base; /* 存储空间 */ int front; /* 头指针，指向队列的头元素 */ int rear; /* 尾指针，指向队尾元素的下一个位置 */ }SqQueue; /* 非增量式的空间分配 */ 2、操作实现 1）空队：Q.front=Q.rear=0; 2）入队：判断是否队满，非队满时，Q.rear 位置放新插入的元素，Q.rear++ 3）出队：判断是否队空，非队空时，Q.front 位置为待删除的元素，Q.front++ 4）队空条件：Q.front == Q.rear 5）队满条件：Q.rear == MAXQSIZE-1 问题：存在假上溢(由于出队操作，队列空间的上部可能存在空闲空间) 3、假上溢的解决 将队列假想为首尾相接的环，即循环队列。 1）入队：……，Q.rear = ( Q.rear+1)%MAXQSIZE 2）出队：……，Q.front = ( Q.front+1)%MAXQSIZE 3）队空条件：Q.front == Q.rear，由于出队 Q.front 追上了 Q.rear 4）队满条件：Q.front == Q.rear，由于入队 Q.rear 追上了 Q.front 问题：队空和队满的判断条件一样 4、如何区分队空和队满 1）设标志位：不足在于需要额外对标志位的判断及维护 2）在队列的结构中引入长度成员，在初始化队列、入队、出队操作中维护这个成员。 3）少用一个元素空间，即队满的条件如下 (Q.rear+1)% MAXQSIZE == Q.front 进一步思考： 1）对比 4 中所列的 3 种方法在队列操作中处理的不同。 2）若循环队列数组的下标起始为-3, 1 或 3 时，如何判断队空、队满，如何实现入队、出 队？