数据结构栈和队列.ppt

循环队列：将存储队列的数组头尾相接。 如何解决假溢出？ 0 1 2 3 4 入队 出队 a3 a4 front a5 rear rear a6 3.3 队列 3.3.2 循环队列 rear 不存在物理的循环结构，用软件方法实现。 求模：（4＋1）mod 5＝0 如何实现循环队列？ 0 1 2 3 4 入队 出队 a3 a4 front rear a6 3.3 队列 3.3.2 循环队列 如何判断循环队列队空？ 队空的临界状态 0 1 2 3 4 入队 出队 a3 rear front 3.3 队列 3.3.2 循环队列 如何判断循环队列队空？ 执行出队操作 队空：front=rear 0 1 2 3 4 入队 出队 a3 front rear front 3.3 队列 3.3.2 循环队列 如何判断循环队列队满？ 队满的临界状态 0 1 2 3 4 入队 出队 a3 a4 front a5 rear a6 3.3 队列 3.3.2 循环队列 如何判断循环队列队满？ 执行入队操作 队满：front=rear 0 1 2 3 4 入队 出队 a3 a4 front a5 rear a6 rear a7 3.3 队列 3.3.2 循环队列 方法一：附设一个存储队列中元素个数的变量num，当num=0时队空，当num=QueueSize时为队满； 方法二：修改队满条件，浪费一个元素空间，队满时数组中只有一个空闲单元； 方法三：设置标志tag，当front=rear且tag=0时为队空，当front=rear且tag=1时为队满。 如何确定不同的队空、队满的判定条件？ 为什么要将队空和队满的判定条件分开？ 3.3 队列 3.3.2 循环队列 队满的条件：(rear+1) mod QueueSize=front 0 1 2 3 4 入队 rearfront a3 a4 front a5 rear a6 出队 0 1 2 3 4 入队 rearfront a3 a4 front a5 rear a6 出队 3.3 队列 3.3.2 循环队列 Status InitQueue (SqQueue Q) { // 构造一个空队列Q Q.base = (ElemType *) malloc (MAXQSIZE *sizeof (ElemType)); if (!Q.base) exit (OVERFLOW); // 存储分配失败 Q.front = Q.rear = 0; return OK; } Status EnQueue (SqQueue Q, ElemType e) { // 插入元素e为Q的新的队尾元素 if ((Q.rear+1) % MAXQSIZE == Q.front) return ERROR; //队列满 Q.base[Q.rear] = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; } Status DeQueue (SqQueue Q, ElemType e) { // 若队列不空，则删除Q的队头元素， // 用e返回其值，并返回OK; 否则返回ERROR if (Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1) % MAXQSIZE; return OK; } CPU资源的竞争问题。 主机与外部设备之间速度不匹配的问题（例如主机和打印机） 打印杨辉三角 划分子集问题 3.6 队列应用举例 第 1 行 1 1 第 2 行 1 2 1 第 3 行 1 3 3 1 第 4 行 1 4