第3章 堆栈和队列幻灯片.pptVIP

3.3 队列一、队列的基本概念 * １、队列定义 ３、存储结构 ４、运算规则 ５、实现方式 ２、逻辑结构 只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。 队尾插入 队头删除 与线性表相同，仍为一对一关系。 顺序队列或链队列，以循环顺序队列更常见。 只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。 关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。 基本操作：入队或出队，建空队列，判队空或队满等操作。 * 队列 （Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。它是一种先进先出（ＦＩＦＯ）的线性表。 例如：队列 Q= (a1 , a2 , a3 , ……….,an-1 , an ) 在队尾插入元素称为入队；在队首删除元素称为出队。 当队列中没有数据元素时称为空队列。 队首 队尾 注：队列的实现方式是本节重点，关键是掌握入队和出队操作。具体实现依存储结构（链队列或顺序队列）的不同而不同。 * 离散事件的模拟（模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列）； 操作系统中的作业调度（一个CPU执行多个作业）； 3. 简化程序设计。 答： 问：为什么要设计队列？它有什么独特用途？ 二、队列抽象数据类型 数据集合：{a0,a1,…,ai ,…,an-1｝ ai的数据类型为 DataType 操作集合：(1)QueueInitiate(Q) 初始化队列Q (2)QueueNotEmpty(Q) 队列Q非空否 (3)QueueAppend(Q,x) 入队列 (4)QueueDelete(Q,d) 出队列 (5)QueueGet(Q,d) 取队头数据元素 等 * 三、顺序队列 1、顺序队列　　　采用顺序存储结构的队列。 2、顺序队列的存储结构 　　它利用一个一维数组来 存储数据元素，另再设立一 个队头指示器和一个队尾指 示器分别指向当前队头元素 和当前队尾元素。用C语言 定义为： typedef struct { DataType queue[MaxQueueSize]; int rear; int front; }SeqCQueue; * a1 a2 a3 data a4 ８ ７ ６ ５ ４ ３ ２ １ ０ front rear (队尾) (队头) 2、顺序队列的“假溢出”问题 (1)假溢出 　　顺序队列因多次入队和出队操作后出现的有存储空间但不能进行入队操作的溢出。 (2)如何解决顺序队列的假溢出问题？ 　　可采取四种方法： 　1)采用循环队列； 2)按最大可能的进队操作次数设置顺序队列的最大元素个数； 3)修改出队算法，使每次出队列后都把队列中剩余数据元素向队头方向移动一个位置； 　４)修改入队算法，增加判断条件，当假溢出时，把队列中的数据元素向对头移动，然后方完成入队操作。 * 四、顺序循环队列的表示和实现 １、顺序循环队列的基本原理 把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。当rear和front达到MaxQueueSize-1后，再前进一个位置就自动到０。 　　　 * 顺序队列 a3 a2 a1 front rear 0 1 2 3 . . N-1 a3 a2 a1 0 1 2 3 N-1 rear front 循环队列 * 2、顺序循环队列的队空和队满判断问题 新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！解决方案有三： ①使用一个计数器记录队列中元素个数（即队列长度）； 　　判队满：count0 rear==front 判队空：count==0 ②加设标志位，出队时置０,入队时置１,则可识别当前front=rear属于何种情况 　　判队满：tag==1 rear==front 判队空：tag==0 rear==front ③ 少用一个存储单元 　　判队满： front=＝(rear+1)%MaxQueueSize 判队空： rear==front * 例： 一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置? J2 J3 J1 J4 J5 front=1