chapt9隊(duì)列(QUEUES

1、1Chapter 9隊(duì)列(QUEUES)2contents9.1 抽象的數(shù)據(jù)類型9.2 基于arrayList的表示9.3 基于鏈接的表示9.4 應(yīng)用特性一個(gè)隊(duì)列是特殊的線性列表，從一頭執(zhí)行插入，而在另一頭執(zhí)行刪除。是 first-in-first-out (FIFO) 的數(shù)據(jù)流動(dòng)方式.49.1 抽象數(shù)據(jù)類型定義:隊(duì)列（queue）是一個(gè)線性表，其插入和刪除操作分別在表的不同端進(jìn)行。添加新元素的那一端被稱為隊(duì)尾（rear）.刪除元素的那一端被成為隊(duì)首（front）. e1, e2, e3, , ei, , en-1, en front rear5A B C D front rearA B C

2、D E front rear B C D E front rear C D E front rear隊(duì)列是一個(gè)先進(jìn)先出（ first-in-first-out, FIFO）的線性表。動(dòng)態(tài)的變化 insertdelete6抽象的數(shù)據(jù)類型實(shí)例按進(jìn)入順序的元素列表，進(jìn)入段叫隊(duì)尾，出去段叫隊(duì)首。操作： empty (): 如果隊(duì)列為空，則返回true，否則返回false；size ( ) :返回隊(duì)列中元素個(gè)數(shù)front (): 返回隊(duì)列的第一個(gè)元素；back ( ) :返回隊(duì)列的最后一個(gè)元素；pop (): 刪除隊(duì)首元素; / dequeuerpush (x): 向隊(duì)列中添加元素x； / enqueu

3、e7TemplateClass queuepublic: virtual queue() virtual bool empry() const = 0; virtual int size() const = 0; virtual T& front() = 0; virtual T&back() =0; virtual pop(); virtual void push(const T& theElement) =0;8 6.2 Formula-based representation formula: (using one dimension array) location(i) = i 1第一

4、個(gè)元素: queue0, 第二個(gè)元素 : queue1 queueFront總是為0 , queueBack始終是最后一個(gè)元素的位置 e1 e2 e3 en queue 0 1 2 MaxSize-1queueFront queueBack 9公式化描述隊(duì)列的長度: rear + 1空隊(duì)列 : queueBack=-1push(x): queueBack+;queuequeueBack=x; O(1)pop: x=queue0; queue0.queueBack-1 queue1.quequeBack; queueBack -; Q(n)e1 e2 e3 en queue 0 1 2 arra

5、yLength-1queueFront queueBack 10Front point is moving 公式: location(i) = location(1) + i 1queueFront = location(1), queueBack = location(last element)空隊(duì)列 : queueBack queueFront / = 0pop: x=queue(queueFront) ;queueFront+; Q(1) push(x): when queueBack 0 ？11Shifting a queue when rear meet end平移隊(duì)列queue0.

6、queueBack-queueFront+1 queuequeueFront.queueBack; queueBack+;queuequeueBack=x; 時(shí)間復(fù)雜性 : Q(n)when queueBack= Maxsize-1 and front 0 push(x)？隊(duì)列的移位之前 隊(duì)列的移位之后12Circular queue (循環(huán)存放） 使得最壞情況下的push,pop時(shí)間復(fù)雜性為O(1)，為了方便區(qū)分隊(duì)列滿和空，約定queueFront指向隊(duì)列前面空白單元的下標(biāo)，queueBack指向最后元素的下標(biāo)。（若front指向第一個(gè)。初始化相等=0，剩最后一個(gè)也相等；若front不指向空

7、，還會(huì)發(fā)生front=back） location(i) = (location(1) + i 1) % arrayLengtha b c d queue 0 1 2 arrayLength-1queneFront queneBack 13Circular queue 描述隊(duì)列的數(shù)組描述隊(duì)列的數(shù)組被視為一個(gè)環(huán)14循環(huán)隊(duì)列（重要約定）queueFront: 指向隊(duì)列首元素前一個(gè)位置（逆時(shí)針方向）。queueBack: 最后queue最后元素的位置。rear front15循環(huán)隊(duì)列隊(duì)列滿 queueFront=(queueBack+1) % arrayLength 隊(duì)列空 queueFront =

8、 queueBack 初始 queueFront=queueBack = 0 下面程序 theFront, theBack16templateclass arrayQueue : public queue public: arrayQueue(int initialCapacity = 10); arrayQueue() delete queue; bool empty() const return theFront = theBack; int size() const return (theBack - theFront + arrayLength) % arrayLength; T& f

9、ront() / return front element if (theFront = theBack) throw queueEmpty(); return queue(theFront + 1) % arrayLength; 17 void push(const T& theElement); private: int theFront; / 1 counterclockwise from theFront element int theBack; / position of theBack element int arrayLength; / queue capacity T *que

10、ue; / element array;T& back() / return theBack element if (theFront = theBack) throw queueEmpty(); return queuetheBack; void pop() / remove theFront element if (theFront = theBack) throw queueEmpty(); theFront = (theFront + 1) % arrayLength; queuetheFront.T(); / destructor for T 18 void push(const T

11、& theElement);private: int theFront; / 首節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)位置 int theBack; / position of theBack element int arrayLength; / queue capacity T *queue; / element array;19templatearrayQueue:arrayQueue(int initialCapacity)/ Constructor. if (initialCapacity 1) ostringstream s; s Initial capacity = initialCapacity 0;

12、throw illegalParameterValue(s.str(); arrayLength = initialCapacity; queue = new TarrayLength; theFront = 0; theBack = 0; 20操作 push21templateVoid arrayQueue: push(const T& theElement)/ 把theElement 添加到隊(duì)列的尾部if (queueBack+1) % arrayLength = queueFront) /調(diào)用后面的長度加倍代碼,而不是簡單地/changeLength1D(queue,arrayLengt

13、h,2*arrayLength); arrayLength*=2;/queueBack = (queueBack + 1) % arrayLength;queuequeueBack = theElement;2223A B C D E F G queuefrontqueueback24templatevoid arrayQueue:push(const T& theElement)/ Add theElement to queue. / increase array length if necessary if (theBack + 1) % arrayLength = theFront) /

14、 double array length / allocate a new array T* newQueue = new T2 * arrayLength; / copy elements into new array int start = (theFront + 1) % arrayLength; if (start 2) /沒有出現(xiàn)backfront的情況 / no wrap around copy(queue + start, queue + start + arrayLength - 1, newQueue); A B C D E F G 25 else / queue wraps

15、 around copy(queue + start, queue + arrayLength, newQueue); copy(queue, queue + theBack + 1, newQueue + arrayLength - start); /這里只有一個(gè)空格（front） / switch to newQueue and set theFront and theBack theFront = 2 * arrayLength - 1; /新數(shù)組的最后元素 theBack = arrayLength - 2; / queue size arrayLength - 1 arrayLeng

16、th *= 2; queue = newQueue; 26 / put theElement at the theBack of the queue theBack = (theBack + 1) % arrayLength; queuetheBack = theElement;空表的情況，第一個(gè)元素放入queue1279.4 linked representationA Queue is represented as a chain Using front and rear to track two ends of queue表頭為 thefront ，表尾為 theback 表頭為 the

17、Back ，表尾為 theFront 028鏈表描述HeadTailHeadTail圖6-7 鏈接隊(duì)列29向鏈表隊(duì)列中添加元素 圖 6-8 (a)的時(shí)間復(fù)雜性 O(1)圖 6-8 (b) 的時(shí)間復(fù)雜性 O(1)圖 6-8 (a) 向圖 6-7 (a)中插入元素 圖 6-8 (b) 向圖 6-7 (b)中插入元素 30從鏈表隊(duì)列中刪除元素 圖 6-9 (a)的時(shí)間復(fù)雜性 O(1)圖 6-9 (b) 的時(shí)間復(fù)雜性O(shè)(n)圖 6-9 (a) 從圖 6-7 (a)中刪除元素圖 6-9 (b) 從圖 6-7 (b)中刪除元素31鏈?zhǔn)?queue front-to-rear實(shí)現(xiàn)Define LinkedQ

18、ueue as base classFront = rear = 0 at beginning Front = 0 iff the queue is empty.queue is full iff there is no memory storage32templateclass linkedQueue : public queue public: linkedQueue(int initialCapacity = 10) queueFront = NULL; queueSize = 0; linkedQueue(); bool empty() const return queueSize =

19、 0; int size() const return queueSize; T& front() if (queueSize = 0) throw queueEmpty(); return queueFront-element; 33 T& back() if (queueSize = 0) throw queueEmpty(); return queueBack-element; void pop(); void push(const T&); private: chainNode* queueFront; / pointer to queue front chainNode* queue

20、Back; / pointer to queue back int queueSize; / number of elements in queue; 34templatevoid linkedQueue:push(const T& theElement)/ 把theElement 添加到隊(duì)列的尾部 chainNode * newNode = new chainNode(theElement,NULL); / 為新元素創(chuàng)建鏈表節(jié)點(diǎn)/ 在隊(duì)列尾部添加新節(jié)點(diǎn) if (queueSize =0) / 隊(duì)列為空 queueFront = newNode; else queueBack-next = n

21、ewNode; / 隊(duì)列非空 queueBack = newNode; queueSize+; 35templateVoid LinkedQueue:pop()/ 刪除第一個(gè)元素If (queueBack =NULL) throw queueEmpty();chainNode* nextNode = queueFront-next;delete queueFront;queueFront = nextNode;queueSize-;366.4 應(yīng)用6.4.1 火車車廂重排6.4.2 電路布線6.4.3 圖元識(shí)別6.4.4 工廠仿真376.4.1 火車車廂重排緩沖鐵軌位于入軌和出軌之間 禁止 :

22、將車廂從緩沖鐵軌移動(dòng)至入軌從出軌移動(dòng)車廂至緩沖鐵軌鐵軌Hk 為可直接將車廂從入軌移動(dòng)到出軌的通道38軌道的分配規(guī)則當(dāng)一個(gè)車c 不能立即出站時(shí)，從目前隊(duì)列中選著那些隊(duì)尾車編號(hào)小于c編號(hào)的軌道，若存在多于2的軌道，從中選最大標(biāo)號(hào)的軌道，把c排入該軌道隊(duì)列；若上面不成功，但又空置的軌道，則把c放入該軌道；上面都不成功時(shí)，宣布不能分配。39火車車廂重排int NowOut=1； / NowOut:下一次要輸出的車廂號(hào)for （int i=1;i=n;i+）/從前至后依次檢查的所有車廂 1. 車廂 pi 從入軌上移出 2. If (pi = NowOut)/ NowOut:下一次要輸出的車廂號(hào) 使用緩沖

23、鐵軌Hk把pi放到出軌上去; NowOut+; while (minH(當(dāng)前緩沖鐵軌中編號(hào)最小的車廂)= NowOut ） 把minH放到出軌上去; 更新 minH,minQ（minH所在的緩沖鐵軌）; NowOut+; else 按照分配規(guī)則將車廂pi送入某個(gè)緩沖鐵軌 讀程序 6-7 6-840void outputFromHoldingTrack()/ output the smallest car from the holding tracks / 從目前保有最小標(biāo)號(hào)的車廂輸出 trackitsTrack.pop(); cout Move car smallestCar from holding track itsTrack to output track endl;/ 修改smallestCar 和 itsTrack by checking all queue fronts smallestCar = numberOfCars + 2; /修改最小車廂所在軌道 for (int i = 1; i = numberOfTracks; i+) if (!tracki.empty() & tracki.front() smallestCar) smallestCar = track