第三章C队列80501.ppt

* * 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列 第三章 栈和队列 ￡3.3.1 队列的定义 ￡3.3 队列 队列（queue）：是一种先进先出（first in first out，缩写为FIFO）的线性表。 它只允许在表的一端进行插入，而在另一端删除元素。 队头（front）：在队列中允许删除元素的一端。 队尾（rear）：在队列中允许插入元素的一端。 出队列 入队列 队头 队尾 … 图3.5 队列示意图 队列在程序设计中也经常出现。 一个最典型的例子就是操作系统中的作业排队。 在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就是按请求输出的先后次序排队。每当通道传输，那就要按请求输出的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出作输出操作。凡是申请输出的作业都从队尾进入队列。 ￡3.3.2 队列的顺序存储结构 （1）定义 队列的顺序存储结构：是利用一组地址连续的存储单元 依次存放从队列头到队列尾的数据元素，同时附设指针front 和rear分别指示队列头元素及队列尾元素的位置。 （2）图形表示 5 4 3 2 1 0 Q.rear Q.front Q.rear Q.front Q.rear Q.front Q.rear Q.front (a) (b) (c) (d) 图3.6 队列的顺序存储结构示意图 (a)空队列 (b) J1、J2和J3相继入队列 (c) J1和J2相继被删除 (d) J4、J5和J6相继插入队列之后J3和J4被删除 J3 J2 J1 J3 J6 J5 尾指针总是指向队列尾元素的下一 位置 头指针总是指向队列头元素 a1 a2 an … … GetHead(Q, e) 初始条件：Q为非空队列。 操作结果：用e返回Q的队头元素。 a1 a2 an e … … EnQueue(Q, e) 初始条件：队列Q已存在。 操作结果：插入元素e为Q的新的队尾元素。 a1 a2 an … … DeQueue(Q, e) 初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。 ?顺序队列运算时的头、尾指针变化： B A D C 3 2 1 0 Sq-r Sq-f Sq-f Sq-r Sq-r Sq-f Sq-f Sq-r 空队列 A、B相继入队 A、B相继出队 C、D相继入队 图3.7 循环队列示意图 Q.rear Q.front 队列 maxsize-1 1 0 （3）循环队列满和空的判断： Q.rear Q.front Q.rear Q.front Q.rear Q.front 4 2 0 1 3 5 4 2 0 1 3 5 4 2 0 1 3 5 图3.8 循环队列满、空示意图 (a) 一般情况 (b)队列满时 (c)空队列 （4）循环队列类型的模块说明 //------------------循环队列——队列的顺序存储结构-------------------- #define MAXQSIZE 100 //最大队列长度 typedef struct { QElemType *base; //初始化的动态分配存储空间 int front; //头指针,若队列不空,指向队列头元素 int rear; //尾指针,若队列不空,指向队列尾元素的下一个位置 } SqQueue; //------------------循环队列的基本操作的算法描述-------------------- Staus InitQueue (SqQueue Q) { //构造一个空队列Q Q.base = (QElemType*) malloc (MAXQSIZE * sizeof(QElemType)); if (!Q.base) exit (OVERFLOW); //存储分配失败 Q.front = Q