《数据结构》-第三章c队列

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）图形表示,543210,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被删除,J3J2J1,J3,J6J5,尾指针总是指向队列尾元素的下一 位置,头指针总是指向队列头元素,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返回其值。,顺序队列运算时的头、尾指针变化：,BA,DC,3 2 1 0,Sq-rSq-f,Sq-f,Sq-r,Sq-rSq-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,图3.8 循环队列满、空示意图,(a) 一般情况,(b)队列满时,(c)空队列,（4）循环队列类型的模块说明,/-循环队列队列的顺序存储结构-#defineMAXQSIZE100 /最大队列长度typedef struct QElemType *base; /初始化的动态分配存储空间int front; /头指针,若队列不空,指向队列头元素int rear; /尾指针,若队列不空,指向队列尾元素的下一个位置 SqQueue;,/-循环队列的基本操作的算法描述- Staus InitQueue (SqQueue ,int QueueLength (SqQueue Q) /返回Q的元素个数，即队列的长度 return (Q.rear Q.front + MAXQSIZE) % MAXQSIZE;,Staus EnQueue (SqQueue ,Staus DeQueue (SqQueue ,3.3.3 队列的链式存储结构,（1）定义 链队列：用链表表示的队列。,（2）图形表示,头结点（为了运算方便）,队头（删除运算从此处开始）,队尾（插入运算从此处开始）,data next,Q.rear,Q.front,图3.9 链队列示意图,（3）队列空的判决条件 Q.front = Q.rear; 即，头指针和尾指针都指向头结点。,（4）几种基本运算 链队列的操作即为单链表的插入和删除操作的特殊情况，只是尚需修改尾指针或头指针。图3.10展示了这两种操作进行时指针变化的情况。,(a) 空队列,(c) 元素y入队列,(b) 元素x入队列,Q.rear,Q.front,Q.rear,Q.front,Q.rear,Q.front,x,x,y,图3.10 队列运算指针变化情况,(d) 元素x出队列,Q.rear,Q.front,（5）ADT Quene的表示和实现 /-单链队列队列的链式存储结构-typedef struct QNode QElemTypedata;struct QNode*top; QNode, *QueuePtr;typedef struct QueuePtr front;/队头指针QueuePtr rear;/队尾指针 LinkQueue;,/-基本操作的函数原型说明- Status InitQueue (LinkQueue /若队列Q为空队列，则返回TRUE，否则返回FALSE,Status QueueLength (LinkQueue Q);/返回Q的元素个数，即为队列的长度 Status GetHead (LinkQueue Q, QElemType /从队头到队尾依次对队列Q中每个元素调用函数visit()。/一旦visit()失败，则操作失败,/-基本操作的算法描述（部分）- Status InitQueue (LinkQueue /InitQueue,Status DestroyQueue (LinkQueue / DestroyQueue,Status EnQueue (LinkQueue / EnQueue,Status DeQueue (LinkQueue