Chapter 6 队列(QUEUES).

Presentation on theme: "Chapter 6 队列(QUEUES)."— Presentation transcript:

1 Chapter 6 队列(QUEUES)

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

3 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.

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

5 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）的线性表。

6 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 }

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

8 公式化描述 queue[0..rear-1]← queue[1..rear]; rear=rear-1;
e1 e2 e3 …… en queue 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)

9 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 > ？

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

11 Circular queue (循环存放） a b c d queue 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

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

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

14 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

15 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; // 数组 } ;

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

17 ‘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];

18 操作 ‘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; }

19 操作 ‘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; }

20 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

21 链表描述 图 链接队列 Head Tail Head Tail

22 向链表队列中添加元素 图 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)

23  从链表队列中删除元素 图 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)

24 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

25 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; } ;

26 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;}

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

28 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; }

29 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; }

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

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

32 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)

33 火车车厢重排 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]送入某个缓冲铁轨 } 读程序

34 作业 P ：1(1)，4，P197：7，P217：17