Chapter 6 队列(QUEUES)

contents 6.1 The abstract data type 6.2 formula-based representation 6.3 linked representation 6.4 applications

Bird’s eye view A queue is a special kind of linear list, i.e., insertion and deletions take place from different end, which is a first-in-first-out (FIFO) list. Although queue classes may be easily derived from the linear list class, for the run time efficiency, we only discuss it as a new linear list class.

6.1 抽象数据类型 定义: e1, e2, e3, …, ei, …, en-1, en 队列（queue）是一个线性表，其插入和删除操作分别在表的不同端进行。 添加新元素的那一端被称为队尾（rear）. 删除元素的那一端被成为队首（front）. e1, e2, e3, …, ei, …, en-1, en ↑ ↑ front rear

Dynamically change ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ C D E front rear A B C D front rear ↑ ↑ front rear A B C D ↑ ↑ front rear A B C D E ↑ ↑ front rear B C D E ↑ ↑ front rear insert delete 队列是一个先进先出（ first-in-first-out, FIFO）的线性表。

Abstract data type abstractDataType Queue { instance ordered list of elements，one end is called front，the another is the rear； operations; Create (): 创建一个空的队列； IsEmpty (): 如果队列为空，则返回true，否则返回false； IsFull ( ) :如果队列满，则返回true；否则返回false； First (): 返回队列的第一个元素； Last ( ) :返回队列的最后一个元素； Add (x): 向队列中添加元素x； // enqueue Delete (x): 删除队首元素，并送入x ; // dequeue }

6.2 Formula-based representation e1 e2 e3 …… en queue 0 1 2 MaxSize-1 front rear formula: (using one dimension array) location(i) = i – 1 第一个元素: queue[0], 第二个元素 : queue[1] …… front总是为0 , rear始终是最后一个元素的位置

公式化描述 queue[0..rear-1]← queue[1..rear]; rear=rear-1; e1 e2 e3 …… en queue 0 1 2 MaxSize-1 front rear 队列的长度: rear + 1 空队列 : rear=-1 Add(x): rear=rear+1;queue[rear]=x; O(1) Delete(x): x=queue[0]; queue[0..rear-1]← queue[1..rear]; rear=rear-1; Q(n)

Front point is moving 公式: location(i) = location(1) + i – 1 front = location(1), rear = location(last element) 空队列 : rear < front Delete(x): x=queue(front) ;front++; Q(1) Add(x): when rear < Maxsize –1: rear=rear+1;queue[rear]=x; Q(1) when rear = Maxsize-1 and front > 0 ？

Shifting a queue when rear meet end when rear = Maxsize-1 and front > 0 Add(x)？ 队列的移位之前 队列的移位之后 平移队列 queue[0..rear-front+1]← queue[front..rear]; rear=rear+1;queue[rear]=x; 时间复杂性 : Q(n)

Circular queue (循环存放） a b c d queue 0 1 2 MaxSize-1 front rear the worst case add and delete time become O(1) when following formula is used location(i) = (location(1) + i – 1) % Maxsize

Circular queue 描述队列的数组 描述队列的数组被视为一个环

循环队列（重要约定） front: 指向队列首元素前一个位置（逆时针方向）。 rear: 最后queue最后元素的位置。 rear

Circular queue Question: when front=rear the queue is full or empty? Solution: consider the queue is full when front=(rear+1) % MaxSize and empty if front == rear

template<class T> // 一维数组实现 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<T>& Add(const T& x); Queue<T>& Delete(T& x); private: int front; //与第一个元素在反时针方向上相差一个位置 int rear; // 指向最后一个元素 int MaxSize; // 队列数组的大小 T *queue; // 数组 } ;

Constructor function template<class T> Queue<T>::Queue(int MaxQueueSize) {// 创建一个容量为MaxQueueSize的空队列 MaxSize = MaxQueueSize + 1; queue = new T[MaxSize]; front = rear = 0; }

‘First’ and ‘Last’ template<class T> T Queue<T>::First() const {// 返回队列的第一个元素 if (IsEmpty()) throw OutOfBounds(); return queue[(front + 1) % MaxSize]; } T Queue<T>::Last() const {// 返回队列的最后一个元素 return queue[rear];

操作 ‘Add’ template<class T> Queue<T>& Queue<T>::Add(const T& x) {// 把x 添加到队列的尾部 if (IsFull()) throw NoMem(); rear = (rear + 1) % MaxSize; queue[rear] = x; return *this; }

操作 ‘Delete’ template<class T> Queue<T>& Queue<T>::Delete(T& x) {// 删除第一个元素，并将其送入x if (IsEmpty()) throw OutOfBounds(); front = (front + 1) % MaxSize; x = queue[front]; return *this; }

6.4 linked representation A Queue is represented as a chain …… Using front and rear to track two ends of queue 表头为 front ，表尾为 rear 表头为 rear ，表尾为 front

链表描述 图6-7 链接队列 Head Tail Head Tail

向链表队列中添加元素 图 6-8 (a)的时间复杂性 O(1) 图 6-8 (b) 的时间复杂性 O(1) 图 6-8 (a) 向图 6-7 (a)中插入元素 图 6-8 (b) 向图 6-7 (b)中插入元素 图 6-8 (a)的时间复杂性 O(1) 图 6-8 (b) 的时间复杂性 O(1)

 从链表队列中删除元素 图 6-9 (a)的时间复杂性 O(1) 图 6-9 (b) 的时间复杂性O(n) 图 6-9 (a) 从图 6-7 (a)中删除元素  图 6-9 (b) 从图 6-7 (b)中删除元素 图 6-9 (a)的时间复杂性 O(1) 图 6-9 (b) 的时间复杂性O(n)

Using presentation front-to-rear  implementation Define LinkedQueue as base class Front = rear = 0 at beginning Front = 0 iff the queue is empty. queue is full iff there is no memory storage

template<class T> class LinkedQueue { //基类 public: 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; } ;

template<class T> LinkedQueue<T>::~LinkedQueue( ) {Node<T> *next; while (front) { next = front->link; delete front; front = next; } bool LinkedQueue<T>::IsFull( ) const // 是否有可利用空间 {Node<T> *p; try {p = new Node<T>; delete p; return false;} catch (NoMem) {return true;}

template<class T> T LinkedQueue<T>::First() const { // 返回队列的第一个元素 if (IsEmpty()) throw OutOfBounds(); return front->data; } T LinkedQueue<T>::Last() const {// 返回队列的最后一个元素 return rear->data;

template<class T> LinkedQueue<T>& LinkedQueue<T>::Add(const T& x) {// 把x 添加到队列的尾部 // 不捕获可能由new引发的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; }

template<class T> LinkedQueue<T>& LinkedQueue<T>::Delete(T& x) {// 删除第一个元素，并将其放入x If (IsEmpty( )) throw OutOfBounds(); x = front->data; //保存第一个节点中的元素 Node<T> *p = front; front = front->link; // 删除第一个节点 delete p; return *this; }

6.4 应用 6.4.1 火车车厢重排 6.4.2 电路布线 6.4.3 图元识别 6.4.4 工厂仿真

6.4.1 火车车厢重排 缓冲铁轨位于入轨和出轨之间 禁止 : 铁轨Hk 为可直接将车厢从入轨移动到出轨的通道 将车厢从缓冲铁轨移动至入轨 从出轨移动车厢至缓冲铁轨 铁轨Hk 为可直接将车厢从入轨移动到出轨的通道

Track selection When a car to be moved to a holding track: Move car c to a holding track that contains only cars with a smaller label; if there are more than two such track, select the one with largest label at its left end; otherwise select an empty track (if one remains)

火车车厢重排 int NowOut=1； // NowOut:下一次要输出的车厢号 for （int i=1;i<=n;i++）//从前至后依次检查的所有车厢 {1. 车厢 p[i] 从入轨上移出 2. If (p[i] == NowOut)// NowOut:下一次要输出的车厢号 ①使用缓冲铁轨Hk把p[i]放到出轨上去; NowOut++; ② while (minH(当前缓冲铁轨中编号最小的车厢)== NowOut ） {把minH放到出轨上去; 更新 minH,minQ（minH所在的缓冲铁轨）; NowOut++;} else 按照分配规则将车厢p[i]送入某个缓冲铁轨 } 读程序 6-7 6-8

作业 P193-194：1(1)，4，P197：7，P217：17