【10】Chapter6 队列-循环队列

【10】Chapter6 队列-循环队列null数据结构与算法数据结构与算法2009年秋季授课教师：张剑波方芳授课班级：111081-4班 115081-2班Chapter6 队列（Queue）Chapter6 队列（Queue）本章教学内容本章教学内容 6.1 队列结构特性 6.2 抽象数据类型 6.3 公式化描述（顺序队列） 6.4 链表描述（链队列） 6.5 应用 1. 火车车厢重排6.1 队列结构特性6.1 队列结构特性2、几个相关的概念1、定义队列是一种特殊的线性表，是一种只允许在表的一端进行插入操作，而在另...

null数据结构与算法数据结构与算法2009年秋季授课教师：张剑波方芳授课班级：111081-4班 115081-2班Chapter6 队列（Queue）Chapter6 队列（Queue）本章教学内容本章教学内容 6.1 队列结构特性 6.2 抽象数据类型 6.3 公式化描述（顺序队列） 6.4 链表描述（链队列） 6.5 应用 1. 火车车厢重排6.1 队列结构特性6.1 队列结构特性2、几个相关的概念1、定义队列是一种特殊的线性表，是一种只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表。a1 a2 a3 … an入队列出队列队头（front）队尾（rear）null3、重要特征每次进队列的元素都放在原队列队尾之后而成为新的队尾元素；每次出队列的数据元素都是原队头元素；先入队列的元素先出队列，后入队列的元素后出队列。队列是一个先进先出的线性表（First In First Out，FIFO）。如：（1）日常生活中的排队；（2）操作系统中的作业队列。课堂练习课堂练习C3、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是。 A、6 B、5 C、3 D、26.2 队列的抽象数据类型描述6.2 队列的抽象数据类型描述ADT Queue { 实例有序线性表，一端称为front，一端称为rear 操作 Create( ); //创建一个空的队列 IsEmpty( ); //如果队列为空，返回true,否则返回false IsFull( ); //如果队列满，返回true,否则返回false First( ); //返回队列中的第一个元素 Last( ); //返回队列中的最后一个元素 Add(x); //向队列添加元素x Delete(x); //删除队首元素，并将它传递给x }队列的两种描述形式队列的两种描述形式队列的物理存储可以用：顺序存储结构链式存储结构6.3 队列的公式化描述（顺序存储结构）6.3 队列的公式化描述（顺序存储结构）队列的顺序存储结构，简称顺序队列；顺序队列可用一个一维数组queue[MaxSize]来存储，其中MaxSize是队列能存放的最大元素个数；为了指示队头和队尾，需要设立一个队头指示器和一个队尾指示器，或称队头指针、队尾指针，为了算法设计上的方便，约定： front（头指针）：指向实际队头元素的前一个位置； rear（尾指针）：指向实际队尾元素所在的位置。1、顺序队列的基本操作1、顺序队列的基本操作（1）初始化（2）入队列（插入）建立一个空队列，即队头指针front=-1，队尾指针rear=-1。当队满时（队满条件：rear==MaxSize-1），产生溢出；当队不满时，尾指针加1（rear = rear + 1），然后把待插元素x送入尾指针所指数组分量。（3）出队列（删除）当队不空时（队空条件：front==rear），队头指针加1（front = front + 1），返回原队头元素，即头指针所指数组分量的值。公式化描述-1公式化描述-1location( i ) = i – 1; front=0，rear为最后一个元素的位置 length = rear+1; 插入耗时Θ(1)，删除耗时Θ(n) ，移动元素!公式化描述-2公式化描述-2location( i ) = location(1) +i– 1; front = location(1)，rear = location(最后一个元素) length = rear-front+1; 插入耗时O(n)，删除耗时Θ(1)最坏情况下插入2、“假溢出”问题 2、“假溢出”问题front =rear =-1front =-1队列空A，B，C入队列D，E入队列rear =2rear =front =2A，B，C出队列队空front =2rear =4 解决“假溢出”的方法解决“假溢出”的方法【方法一】按最大可能的进队列操作次数，设置顺序队列的最大元素个数，这种方法很浪费空间，而且有时会因为估计不准而出错；【方法二】修改出队列算法，设每次出队列后，都把队列中剩余数据元素向队头方向移用一个位置，时间复杂度为O(n)，浪费了时间。【方法三】修改入队列算法，当为真溢出时，返回false；当为假溢出时，则把队列中的数据元素向队头方向移动front+1个位置，使队头元素位于队列的最前端后再完成新数据元素的入队操作；当为其它情况时，进队列操作算法同前。此算法的时间复杂度也为O(n)。3、循环队列3、循环队列【方法四】将数组的存储区0～MaxSize-1看成是一个首尾相接的环形区域 location( i ) = ( location(1) + i- 1) % MaxSize;循环队列的特点循环队列的特点循环队列头、尾指针的特点: 头指针front：队列中第一个元素的下一个位置（逆时针方向）；尾指针rear：指向队列中最后一个元素。初始化：front=rear=0;4、循环队列的操作4、循环队列的操作（1）插入或删除一个元素的实现插入：在队尾进行，尾指针向顺时针方向移动一个位置动态描述：rear=rear+1; if(rear==MaxSize-1) rear=0; 可利用数学上的“模（％）运算”来实现上述过程：rear=(rear+1)%MaxSize;null 删除：在队头进行，头指针向顺时针方向移动一个位置front=(front+1)%MaxSize;（3）入队列、出队列如何判断队满、队空采用循环队列，不易区别队空和队满，都为 front==rear; ——此条件用来判断队空。null 队满的判断：把“尾指针加1后等于头指针”作为队列满的条件。(rear+1)%MaxSize==front 用以上方法判队空、队满时，队列中因留有一个空额而损失了一个空间，所以还可以用另一种方法：设立标志位来区别队空、队满，例如：bool IsFull;循环队列类Queue（程序6-1）循环队列类Queue（程序6-1）template class Queue { public: Queue (int MaxQueueSize = 10) ; ~ Queue( ) { delete [ ] queue; } bool IsEmpty( ) const { return front == rear; } bool IsFull( ) const { return ((rear+1)%MaxSize == front) ? 1: 0; } T First( ) const; //返回队首元素 T Last( ) const; //返回队尾元素 Queue & Add(const T& x); Queue & Delete(const T& x); private: int front; //与第一个元素在反时针方向上相差一个位置 int rear; //指向最后一个元素 int MaxSize; //队列数组的大小 T * queue; //数组 };-操作1-创建空队列-操作1-创建空队列template Queue::Queue(int MaxQueueSize) { //创建一个容量为MaxQueueSize的空队列 MaxSize ＝ MaxQueueSize + 1; queue = new T[MaxSize]; front = rear= 0; } 循环队列容量比数组容量少1！-操作2-返回队列中的第一个元素-操作2-返回队列中的第一个元素template T Queue::First( ) const { //返回队列中的第一个元素 if (IsEmpty()) throw OutOfBounds()); return queue[ (front + 1)%MaxSize ]; }-操作3-返回队列中的最后一个元素-操作3-返回队列中的最后一个元素template T Queue::Last( ) const { //返回队列中的最后一个元素 if (IsFull()) throw OutOfBounds()); return queue[ rear ]; }-操作4-入队列（插入）-操作4-入队列（插入）template Queue & Queue::Add(const T & x) const { //向队列添加元素x if (IsFull()) throw NoMem( ); rear = (rear +1)%MaxSize; queue[rear] = x; return * this; }操作5-出队列（删除）操作5-出队列（删除）template Queue & Queue::Delete(const T & x) const { //删除第一个元素 if (IsEmpty( )) throw OutOfBounds( )); front= (front +1)%MaxSize; x = queue[front] ; return * this; }课堂练习课堂练习若循环队列以数组 Q[0..m-1] 作为其存储结构变量 rear 表示循环队列中队尾元素的实际位置，其移动按 rear=(rear+1) mod m 进行，变量 length 表示当前循环队列中的元素个数，则循环队列的队首元素的实际位置是。　　A．rear-length　　　　　　　　 B．(rear-length+m) mod m 　 C．(1+rear+m-length) mod m　　 D．m-length 2004年软件设计师试题(C)6.4 队列的链表描述（链队列）6.4 队列的链表描述（链队列）队头在链头，队尾在链尾。队空条件为 front == NULL这种链接方向更便于删除！两种链表队列的比较两种链表队列的比较Θ(1)Θ(1)Θ(1)O(n)链队列：操作示例链队列：操作示例链式队列类的定义链式队列类的定义template class LinkedQueue { public: LinkedQueue( ) : rear ( NULL ), front ( NULL ) { } ~ LinkedQueue( ); bool IsEmpty( ) const { return front ? false : true; } bool IsFull( ) const; T First( ) const; //返回队首元素 T Last( ) const; //返回队尾元素 Queue & Add(const T& x); Queue & Delete(const T& x); private: Node * front; //指向第一个节点 Node * rear; //指向最后一个元素 };-操作1-析构函数-操作1-析构函数template LinkedQueue::~LinkedQueue ( ) { //析构函数，删除全部节点 Node * next; while(front) { next = front->next; delete front; front = next; } }O(n)-操作2-判断队列是否已满-操作2-判断队列是否已满template bool LinkedQueue::IsFull( ) const { //判断队列是否已满 Node * p; try { p = new Node; delete p; return false; } catch(NoMem) { return true; } }-操作3-返回队列中的第一个元素-操作3-返回队列中的第一个元素template T LinkedQueue::First( ) const { //返回队列中的第一个元素 if (IsEmpty( )) throw OutOfBounds( )); return front->data; }-操作4-返回队列中的最后一个元素-操作4-返回队列中的最后一个元素template T LinkedQueue::Last( ) const { //返回队列中的第一个元素 if (IsFull( )) throw OutOfBounds()); return rear->data; }-操作5-向队列添加元素x-操作5-向队列添加元素xtemplate 向队列添加元素x LinkedQueue & LinkedQueue::Add(const T & x) { Node * p = new Node; p->data = x; p->link = null; if (front) rear->link = p; 后插元素 else front = p; rear = p; return * this; }-操作6-删除第一个元素x-操作6-删除第一个元素xtemplate 删除第一个元素x LinkedQueue & LinkedQueue::Delete(const T & x) { if (IsEmpty( )) throw OutOfBounds( )); //保存第一个元素到x x = front->data; //删除第一个元素 Node * p = front; 前删元素 front = front->next; delete p; return * this; }6.5 队列应用-火车车厢重排6.5 队列应用-火车车厢重排缓冲铁轨按照FIFO的方式运作：队列入轨出轨5,8,1,7,4,2,9,6,39,8,7,6,5,4,3,2,1H1H2H3铁轨Hk作为直接将车厢从入轨移动到出轨的通道，因此实际可作为缓冲轨道的数目为k-1。null5,8,1,7,4,2,9,6,35,8,1,7,4,2,9,65,8,1,7,4,2,95,8,1,7,4,2null5,8,1,7,4,25,8,1,7,45,8,1,75,8,1null5,8,11 Step 7：2,13,2,14,3,2,15,8null5,84,3,2,15 Step 12：5,4,3,2,1Empty6,5,4,3,2,19,8,7,6,5,4,3,2,1车厢分配到缓冲轨道的规则车厢分配到缓冲轨道的规则车厢C应该移动到这样的铁轨：该缓冲铁轨中现有的各车厢的编号均小于C；如果有多个缓冲铁轨满足这样的条件，则选择一个尾部车厢编号最大的缓冲铁轨，否则选择一个空的缓冲铁轨【如果有的话】算法1：使用队列，程序6-7算法1：使用队列，程序6-7bool Railroad(int p[], int n, int k) { LinkedQueue *H; H = new LinkedQueue [k]; k--; //keep track k open for direct moves int NowOut = 1; // next car to output int minH = n+1; // smallest car in a track int minQ; // track with car minH null for (int i = 1; i <= n; i++) if (p[i] == NowOut) { cout << "Move car " << p[i] << " from input to output" ; NowOut++; while (minH == NowOut) { Output(minH, minQ, H, k, n); 车厢从缓冲轨道移动出轨 NowOut++; } } else { 将车厢C移动到合适的缓冲轨道 if (!Hold(p[i], minH, minQ, H, k)) return false; } return true; }O(kn)nullnull算法2：不使用队列，程序6-8算法2：不使用队列，程序6-8简化版：如果只需简单输出车厢重排移动顺序只需了解：每个缓冲铁轨的最后一个成员是谁？以及每节车厢当前位于那个缓冲铁轨？引入两个数组： last[1..k]，表示每个缓冲铁轨中最后一个车厢的编号 track[1..n]，表示每个车厢所在的缓冲铁轨编号nullO(kn)简化：车厢从缓冲轨道移出轨简化：车厢从缓冲轨道移出轨下一个出轨的车厢编号，与当前缓冲轨道中最后一个车厢编号相同？null课后练习：键盘缓冲区课后练习：键盘缓冲区当程序正在执行其它任务时，用户可以从键盘上不断键入所要输入的内容。系统在利用这种分时处理方法时，用户键入的内容不能在屏幕上立刻显示出来，直到当前正在工作的那个进程结束为止。但在这个进程执行时，系统是在不断地检查键盘状态，如果检测到用户键入了一个新的字符，就立刻把它存到系统缓冲区中，然后继续运行原来的进程。当当前工作的进程结束后，系统就从缓冲区中取出键入的字符，并按要求进行处理。键盘缓冲区的简单模拟键盘缓冲区的简单模拟要求：使用循环队列定义一个类：实现两个基本函数 Input：接受一个输入键，不显示，直接送入键盘缓冲区 Output：从缓冲区中取出一个键，显示在屏幕上测试：轮流调用两个接口使用_getch ()函数不显示输入！null

                    本文档为【【10】Chapter6 队列-循环队列】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

【10】Chapter6 队列-循环队列

你可能还喜欢