Chapter6 队列(Queues) The Abstract Data Type Formula-Based Representation Linked Representation Applications 2/25/2019

本章重点 队列的实现 队列的应用 2/25/2019

队列(Queues) 定义 是一个线性表，其插入和删除操作分别在表的不同端进行。添加新元素的那一端被称为队尾(rear)，而删除元素的那一端被称为队首(front)。 队列是一个先进先出（ first-in-first-out, FIFO）的线性表。 2/25/2019

队列 2/25/2019

队列 2/25/2019

公式化描述 公式6-1 location (i)=i-1 2/25/2019

性质 front:0 rear:最后一个元素的位置 空队列:rear=-1 2/25/2019

公式化描述 公式6-2 location(i)=location(1)+ i-1 2/25/2019

性质 front:location(1) rear:location(最后一个元素) 空队列:rear<front 2/25/2019

插入操作 location(i)=location(1)+ i-1 2/25/2019

公式化描述 公式6-3 location(i)=(location(1)+i-1)% Maxsize 2/25/2019

性质 front:指向队列首元素的下一个位置(逆时针方向) rear:队列尾 空队列:front = rear 队列满? 2/25/2019

队列满? 2/25/2019

循环队列的进队和出队 2/25/2019

公式化类Queue template<class T> class Queue { // FIFO 对象 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<T>& Add(const T& x); Queue<T>& Delete(T& x); 2/25/2019

公式化类Queue private: int front; //与第一个元素在反时针方向上相差一个位置 int rear; // 指向最后一个元素 int MaxSize; // 队列数组的大小 T *queue; // 数组 } ; 2/25/2019

构造函数 template<class T> Queue<T>::Queue(int MaxQueueSize) MaxSize = MaxQueueSize + 1; queue = new T[MaxSize]; front = rear = 0; } 2/25/2019

公式化类Queue template<class T> T Queue<T>::First() const {// 返回队列的第一个元素 // 如果队列为空，则引发异常OutOfBounds if (IsEmpty()) throw OutOfBounds(); return queue[(front + 1) % MaxSize]; } 2/25/2019

公式化类Queue template<class T> T Queue<T>::Last() const {// 返回队列的最后一个元素 // 如果队列为空，则引发异常OutOfBounds if (IsEmpty()) throw OutOfBounds(); return queue[rear]; } 2/25/2019

公式化类Queue template<class T> Queue<T>& Queue<T>::Add(const T& x) {// 把x 添加到队列的尾部 // 如果队列满，则引发异常NoMem if (IsFull()) throw NoMem(); rear = (rear + 1) % MaxSize; queue[rear] = x; return *this; } 2/25/2019

公式化类Queue template<class T> Queue<T>& Queue<T>::Delete(T& x) {// 删除第一个元素，并将其送入x // 如果队列为空，则引发异常OutOfBounds if (IsEmpty()) throw OutOfBounds(); front = (front + 1) % MaxSize; x = queue[front]; return *this; } 2/25/2019

链表描述 可以使用单向链表来实现一个队列。 思考：链表中使用几个指针？ 2/25/2019

链表描述 需要两个变量front和rear来分别跟踪队列的两端。。 2/25/2019

链表描述的两种方式 思考：性能相同吗？ 2/25/2019

链表插入 2/25/2019

链表删除 2/25/2019

链表队列的类定义 template<class T> class LinkedQueue { // FIFO对象 p u b l i c : LinkedQueue() {front = rear = 0;} // 构造函数 ~LinkedQueue(); // 析构函数 bool IsEmpty() const {return ((front) ? false : true);} bool IsFull() const; T First() const; // 返回第一个元素 T Last() const; // 返回最后一个元素 LinkedQueue<T>& Add(const T& x); LinkedQueue<T>& Delete(T& x); private: Node<T> *front; // 指向第一个节点 Node<T> *rear; //指向最后一个节点 } ; 2/25/2019

删除所有节点 template<class T> LinkedQueue<T>:: ~LinkedQueue( ) {// 队列析构函数，删除所有节点 Node<T> *next; while (front) { next = front->link; delete front; front = next; } 2/25/2019

判断队列是否已满 template<class T> bool LinkedQueue<T>::IsFull() const {// 判断队列是否已满 Node<T> *p; try {p = new Node<T>; delete p; return false;} catch (NoMem) {return true;} } 2/25/2019

返回队列的第一个元素 template<class T> T LinkedQueue<T>::First() const {// 返回队列的第一个元素 // 如果队列为空，则引发异常O u t O f B o u n d s if (IsEmpty()) throw OutOfBounds(); return front->data; } 2/25/2019

返回队列的最后一个元素 template<class T> T LinkedQueue<T>::Last() const {// 返回队列的最后一个元素 // 如果队列为空，则引发异常O u t O f B o u n d s if (IsEmpty()) throw OutOfBounds(); return rear->data; } 2/25/2019

把x 添加到队列的尾部 template<class T> LinkedQueue<T>& LinkedQueue<T>::Add(const T& x) {// 把x 添加到队列的尾部 // 不捕获可能由n e w引发的NoMem 异常 // 为新元素创建链表节点 Node<T> *p = new Node<T>; p->data = x; p->link = 0; if (front) rear->link = p; //队列不为空 else front = p; // 队列为空 rear = p; return *this; } 2/25/2019

删除第一个元素 template<class T> LinkedQueue<T>& LinkedQueue<T>::Delete(T& x) {{// 删除第一个元素，并将其放入x // 如果队列为空，则引发异常O u t O f B o u n d s if (IsEmpty()) throw OutOfBounds(); / /保存第一个节点中的元素 x = front->data; // 删除第一个节点 Node<T> *p = front; front = front->link; delete p; return *this; } 2/25/2019

应用 火车车厢重排(Railroad Car Rearrangement) 电路布线(Wire Routing) 工厂仿真(Machine Shop Simulation) 2/25/2019

火车车厢重排问题 缓冲铁轨运作方式？ 缓冲铁轨个数？(Hk作为从入轨道出轨的通道) 2/25/2019

火车车厢重排-约束 仅允许以下移动： 入轨右端->缓冲铁轨 入轨右端->出轨 缓冲铁轨右端->出轨 2/25/2019

火车车厢重排方案 从前至后依次检查入轨上的所有车厢。 如果正在检查的车厢就是下一个满足排列要求的车厢，可以直接把它放到出轨上去。如果不是，则把它移动到缓冲铁轨上，直到按输出次序要求轮到它时才将它放到出轨上。 重排演示。 2/25/2019

火车车厢重排程序-队列 bool Railroad(int p[], int n, int k) {// k 个缓冲铁轨，车厢初始排序为p [ 1 : n ] // 如果重排成功，返回true，否则返回false // 如果内存不足，则引发异常NoMem 。 //创建与缓冲铁轨对应的堆栈 LinkedQueue<int> *H; H = new LinkedQueue<int> [k]; k--; int NowOut = 1; //下一次要输出的车厢 int minH = n+l; //缓冲铁轨中编号最小的车厢 int minQ; //minH号车厢对应的缓冲铁轨 2/25/2019

火车车厢重排程序 //车厢重排 for(int i = 1; i <= n; i++) if (p[i] == NowOut) {// 直接输出t cout<<“将车厢”<<p[i]<<“从入轨移至出轨"<<endl; NowOut++ ; //从缓冲铁轨中输出 while (minH == NowOut) { Output(minH, minQ, H, k, n); NowOut++ ; } } else {// 将p[i] 送入某个缓冲铁轨 if (!Hold(p[i], minH, minQ, H, k)) return false; } return true; } 2/25/2019

Output 函数 void Output(int& minH, int& minQ, LinkedQueue<int> H[], int k, int n) { / /从缓冲铁轨移动到出轨，并修改minH 和minQ . int c; // 车厢编号 // 从队列minQ 中删除编号最小的车厢minH H[minQ].Delete(c) ; cout << "Move car " << minH << " from holding track " << minQ << " to output" << endl; // 通过检查所有队列的首部，寻找新的minH和minQ minH = n + 2; for (int i = 1; i <= k; i++) if (!H[i].IsEmpty() && c = H[i].First()) < minH) { minH = c; minQ = i;} } 2/25/2019

Hold函数 bool Hold(int c, int& minH, int &minQ, LinkedQueue<int> H[], int k) {//把车厢c 移动到缓冲铁轨中 // 如果没有可用的缓冲铁轨，则返回false，否则返回true // 为车厢c 寻找最优的缓冲铁轨 // 初始化 int BestTrack = 0, // 目前最优的铁轨 BestLast = 0, // BestTrack 中最后一节车厢 x; // 车厢编号 2/25/2019

Hold函数 // 扫描缓冲铁轨 for (int i = 1; i <= k; i++) if (!H[i].IsEmpty()) {// 铁轨i 不为空 x = H[i].Last(); if (c > x && x > BestLast) { // 铁轨i 尾部的车厢编号较大 BestLast = x; BestTrack = i;} } else // 铁轨i 为空 if (!BestTrack) BestTrack = i; 2/25/2019

Hold函数 if (!BestTrack) return false; //没有可用的铁轨 // 把c移动到最优铁轨 H[BestTrack].Add(c) ; cout << "Move car " << c << " from input " << "to holding track " << BestTrack << endl; // 如果有必要，则修改minH和minQ if (c < minH) {minH = c; minQ = BestTrack ; } return true; } 复杂性？ 2/25/2019

迷宫最短路径问题扩展 在迷宫中寻找最短路径的问题也存在于其他许多领域。 例如，在解决电路布线问题时，一种很常用的方法就是在布线区域叠上一个网格，该网格把布线区域划分成n×m个方格，就像迷宫一样。 从一个方格a的中心点连接到另一个方格b的中心点时，转弯处必须采用直角。如果已经有某条线路经过一个方格，则封锁该方格。我们希望使用a和b之间的最短路径来作为布线的路径，以便减少信号的延迟。 2/25/2019

电路布线 2/25/2019

方案 为了找到网格中位置a和b之间的最短路径，先从位置a 开始搜索，把a 可到达的相邻方格都标记为1(表示与a 相距为1)，然后把标号为1的方格可到达的相邻方格都标记为2(表示与a相距为2)，继续进行下去，直到到达b或者找不到可到达的相邻方格为止。 2/25/2019

方案演示 2/25/2019

输出方案 为了得到a与b之间的最短路径，从b开始，首先移动到一个比b 的编号小的相邻位置上。一定存在这样的相邻位置，因为任一个方格上的标号与它相邻方格上的标号都至少相差1。 接下来，从当前位置开始，继续移动到比当前标号小1的相邻位置上。 重复这个过程，直至到达a为止。 2/25/2019

寻找电路布线最短路径 bool FindPath(Position start, Position finish, int& PathLen, Position * &path) { / /寻找从start到finish的路径 // 如果成功，则返回true，否则返回false // 如果空间不足，则引发异常NoMem if((start.row==finish.row)&&(start.col == finish.col)) {PathLen = 0; return true;} // start = finish // 初始化包围网格的“围墙” for (int i = 0; i <= m+1; i++) { grid[0][i] = grid[m+1][i] = 1; // 底和顶 grid[i][0] = grid[i][m+1] = 1; // 左和右 } 2/25/2019

寻找电路布线最短路径 // 初始化offset Position offset[ 4 ] ; offset[0].row = 0; offset[0].col = 1; // 右 offset[1].row = 1; offset[1].col = 0; // 下 offset[2].row = 0; offset[2].col = -1; // 左 offset[3].row = -1; offset[3].col = 0; // 上 int NumOfNbrs = 4; // 一个网格位置的相邻位置数 Position here, nbr; here.row = start.row; here.col = start.col; grid[start.row][start.col] = 2; // 封锁 2/25/2019

寻找电路布线最短路径 // 标记可到达的网格位置 LinkedQueue<Position> Q; do { // 标记相邻位置 for (int i = 0; i < NumOfNbrs; i++) { nbr.row = here.row + offset[i].row; nbr.col = here.col + offset[i].col; if (grid[nbr.row][nbr.col] == 0) {//新位置 grid[nbr.row][nbr.col]=grid[here.row][here.col]+1; if((nbr.row==finish.row)&&(nbr.col==finish.col)) break; // 完成 Q.Add(nbr);} // if 结束 } // for 结束 2/25/2019

寻找电路布线最短路径 //已到达finish吗? if((nbr.row==finish.row)&& (nbr.col==finish.col)) break; // 完成 // 未到达finish，可移动到nbr吗? if (Q.IsEmpty()) return false; // 没有路径 Q.Delete(here); // 到下一位置 } while(true); 2/25/2019

寻找电路布线最短路径 // 构造路径 PathLen = grid[finish.row][finish.col] - 2; path = new Position [PathLen]; here = finish; // 回溯至finish for (int j = PathLen-1; j >= 0; j--) { path[j] = here; // 寻找前一个位置 for (int i = 0; i < NumOfNbrs; i++) { nbr.row = here.row + offset[i].row; nbr.col = here.col + offset[i].col; if (grid[nbr.row] [ nbr.col] == j+2) break; } here = nbr; // 移动到前一个位置 } return true; } 2/25/2019

工厂仿真 一间工厂由m台机器组成。 工厂中所执行的每项任务都由若干道工序构成，一台机器用来完成一道工序，不同的机器完成不同的工序。 一旦一台机器开始处理一道工序，它会连续不断地进行处理，直到该工序被完成为止。 2/25/2019

工序属性 对于一项任务中的每道工序来说，都有两个属性：一是工时（即完成该道工序需要多长时间），一是执行该工序的机器。 一项任务中的各道工序必须按照一定的次序来执行。一项任务的执行是从处理第一道工序的机器开始的，当第一道工序完成后，任务转至处理第二道工序的机器，依此进行下去，直到最后一道工序完成为止。 当一项任务到达一台机器时，若机器正忙，则该任务将不得不等待。 2/25/2019

机器状态 在工厂中每台机器都可以有如下三种状态：活动、空闲和转换。 在活动状态，机器正在处理一道工序。 在空闲状态机器无事可做。 在转换状态，机器刚刚完成一道工序，并在为一项新任务的执行做准备，比如机器操作员可能需要清理机器并稍作休息等。每台机器在转换状态期间所花费的时间可能各不相同。 2/25/2019

任务队列 当一台机器可以处理一项新任务时，它可能需要从各个等待者中挑选一项任务来执行。 在这里，每台机器都按照FIFO的方式来处理等待者，因此每台机器旁的等待者构成了一个FIFO队列。 在其他类型的工厂中，可以为每项任务指定不同的优先权，当机器变成空闲时，从等待者中首先选择具有最高优先权的任务来执行。 2/25/2019

目标 为了让顾客满意，希望尽量减少任务在机器队列中的等待时间。如果能够知道每项任务所花费的等待时间是多少，并且知道哪些机器所导致的等待时间最多，就可以据此来改进和提高工厂的效能。 2/25/2019

工厂仿真实现 在对工厂进行仿真时，采用一个模拟时钟来进行仿真计时，每当一道工序完成或一项新任务到达工厂时，模拟时钟就推进一个单位。在完成老任务时，将产生新的任务。每当一道工序完成或一项新任务到达工厂时，称发生了一个事件(event)。 另外，还存在一个启动事件(start event)，用来启动仿真过程。 2/25/2019

示例 三台机器M1、M2和M3的转换状态所花费的时间分别为2、0和1。 2/25/2019

四项任务的特征 每道工序用形如(machine，time)的值对来描述。 各项任务的长度分别为7，6，8和4。 2/25/2019

仿真 2/25/2019

结果 2号和4号任务在第12时刻完成，1号任务在第15时刻完成，3号任务在第19时刻完成。 由于2号任务的长度为6，而它的完成时刻为12，所以2号任务在队列中所花费的等待时间为12 - 6 = 6个时间单元。 类似地，4号任务在队列中的等待时间为12 -4 = 8个时间单元，1号和3号任务的等待时间分别为8和11个时间单元。 总的等待时间为33个时间单元。 2/25/2019

第六章 总结 队列的逻辑结构和实现方式 火车车厢重排 电路布线 工厂仿真 2/25/2019