第三章-栈与队列.ppt

1 第三章栈与队列 栈 Stack 队列 Queue 2 3 4队列 Queue 定义队列是只允许在一端删除 在另一端插入的线性结构允许删除的一端叫做队头 front 允许插入的一端叫做队尾 rear 特性先进先出 FIFO FirstInFirstOut 3 队列的抽象数据类型 ADTQueue D ai aiElemSet i 1 2 n R ai 1 aiD i 2 n 约定a1端为队首 an端为队尾P InitQueue Q DestroyQueue Q ClearQueue Q QueueEmpty Q QueueLength Q GetHead Q e EnQueue Q e DeQueue Q e QueueTraverse Q visit ADTQueue 4 队列的表示和实现 队列的顺序表示 顺序队列用一组连续的存储单元依次存放从队首到队尾的元素 附设两个指针front和rear分别指向队首元素和队尾元素的位置 defineMAXQSIZE100typedefstruct QElemType base intfront intrear SqQueue SqQueueQ 5 顺序队列的实现 当front rear 0时表示空队列当插入新元素到队尾时 rear加1当删除队首元素时 front加1这种顺序队列空间利用率低 每个位置只能使用一次 6 循环队列及其实现 循环队列为了提高队列的空间利用率 提出循环队列结构与顺序队列相同 只是界线处理稍有不同 7 循环队列的进队和出队 队头指针进1 front front 1 maxSize 队尾指针进1 rear rear 1 maxSize 8 存储队列的数组被当作首尾相接的表处理 队头 队尾指针加1时从maxSize 1直接进到0 可用语言的取模 余数 运算实现 队头指针进1 front front 1 maxSize 队尾指针进1 rear rear 1 maxSize 队列初始化 front rear 0 队空条件 front rear 队满条件 rear 1 maxSize frontfront rear可能表示队空 也可能表示队满应另设标志以便区别队空状态或少用一个位置 循环队列 CircularQueue 9 循环队列及其实现 循环队列为了提高队列的空间利用率 提出循环队列结构与顺序队列相同 只是界线处理稍有不同 StatusInitQueue SqQueue 10 循环队列及其实现 intQueueLength SqQueueQ return Q rear Q front MAXQSIZE MAXQSIZE StatusEnQueue SqQueue StatusDeQueue SqQueue 第三种方法 使用一个计数器记录队列中元素的总数 实际上是队列长度 下面是实现循环队列上的六种基本操作 为此先给出循环队列的类型定义 defineQueueSize100typedefcharDataType typedefStruct intfront intrear intcount datatypedata queuesize cirqueue 1 置空队voidinitqueue cirqueue q q front q rear 0 q count 0 2 判断队空intqueueempty cirqueue q returnq count 0 3 判断队满intqueuefull cirqueue q returnq count queuesize 4 入队voidenqueue cirqueue q datatypex if queuefull q error queueoverflow q count q data q rear x q rear q rear 1 queuesize 5 出队datatypedequeue cirqueue q datatypetemp if queueempty q error queueunderflow temp q data q front q count q front q front 1 queuesize returntemp 6 取队首元素datatypequeuefront cirqueue q if queueempty q error queueisempty returnq data q front 1 循环队列的优点是什么 如何判断它的空和满 2 设长度为n的链队列用单循环链表表示 若只设头指针 则怎样进行入队和出队操作 若只设尾指针呢 3 用第一种 第二种方法 即设状态标识 少用一个元素空间的方法来区别循环队列的队空和队满 试设计置空队 判队空 判队满 出队 入队及取队头元素等六个基本操作 4 如果头指针 尾指针 队列长度中只能选两个来实现队列 你使用哪两个 思考 练习题 假设循环队列只设rear和quelen来分别指示队尾元素的位置和队中元素的个数 试给出判断此循环队列的队满条件 并写出相应的入队算法 作业 习题 18 队列的链接表示 链式队列 队头在链头 队尾在链尾 链式队列在进队时无队满问题 但有队空问题 队空条件为front NULL 3 4 3链队列和顺序队列类似 我们也是将这两个指针封装在一起 将链队列的类型LinkQueue定义为一个结构类型 typedefstructqueuenode datatypedata structqueuenode next queuenode typedefstruct queuenode front queuenode rear linkqueue 下面给出链队列上实现的基本运算 voidinitqueue linkqueue q q front q rear null intqueueempty linkqueue q returnq front null else q rear next p q rear p Datatypedequeue linkqueue q datatypex queuenode p if queueempty q error queueunderflow p q front x p data q front p next if q rear p q rear null free p returnx datatypequeuefront linkqueue q if queueempty q error queueisempty returnq front data 注意 在出队算法中 一般只需修改队头指针 但当原队中只有一个结点时 该结点既是队头也是队尾 故删去此结点时亦需修改尾指针 且删去此结点后队列变空 25 队列的表示和实现 带头结点 队首指针front和队尾指针rear typedefstruct QElemTypedata structQNode next QNode QueuePtr typedefstruct QueuePtrfront QueuePtrrear LinkQueue LinkQueueQ Q front Q rear data next 队首 队尾 头结点 26 链队列的实现 x 空队 元素x入队 27 队列应用 1 解决计算机主机与外设不匹配的问题 2 解决由于多用户引起的资源竞争问题 3 离散事件的模拟 模拟实际应用中的各种排队现象 4 用于处理程序中具有先进先出特征的过程 在操作系统课程中会讲到 28 优先级队列 P