1、與線性表相同，仍為一對一關系與線性表相同，仍為一對一關系。順序隊或鏈隊，以循環順序隊更常見。順序隊或鏈隊，以循環順序隊更常見。只能在隊首和隊尾運算，且訪問結點時依照只能在隊首和隊尾運算，且訪問結點時依照先進先出（先進先出（FIFOFIFO）的原則。）的原則。關鍵是掌握入隊和出隊操作，具體實現依順關鍵是掌握入隊和出隊操作，具體實現依順序隊或鏈隊的不同而不同。序隊或鏈隊的不同而不同。存儲結構存儲結構運算規則運算規則實現方式實現方式 邏輯結構邏輯結構只能在表的一端進行插入運算，在表的另一只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。端進行刪除運算的線性表。基本操作基本操作：入隊或出隊

2、，建空隊列，判隊空或隊滿等操作。：入隊或出隊，建空隊列，判隊空或隊滿等操作。尾部插尾部插入入首部刪首部刪除除隊列定義隊列定義隊列隊列 （QueueQueue）是僅在表尾進行插入操作，在表頭進）是僅在表尾進行插入操作，在表頭進行刪除操作的線性表。它是一種先進先出（）行刪除操作的線性表。它是一種先進先出（）的線性表。的線性表。例如：隊列例如：隊列 Q= (a1 , a2 , a3 , .,an-1 , an )在隊尾插入元素稱為在隊尾插入元素稱為；在隊首刪除元素稱為；在隊首刪除元素稱為。隊首隊首隊尾隊尾問：為什么要設計隊列？它有什么獨特用途？問：為什么要設計隊列？它有什么獨特用途？1.1.離散事件

3、的模擬（模擬事件發生的先后順序離散事件的模擬（模擬事件發生的先后順序, ,例如例如 CPUCPU芯片中的指令譯碼隊列）；芯片中的指令譯碼隊列）；2.2.操作系統中的作業調度（一個操作系統中的作業調度（一個CPUCPU執行多個作業）；執行多個作業）；3. 3. 簡化程序設計。簡化程序設計。答：答：ADT QueueADT Queue DsetDset: :是一個從兩端分別進行插入和刪除限定性的線性表。是一個從兩端分別進行插入和刪除限定性的線性表。RsetRset: :隊列的一端稱為的隊頭（隊列的一端稱為的隊頭（frontfront），而另一端（），而另一端（rearrear）稱為）稱為隊尾。隊尾

4、。OPSetOPSet：CreatQueueCreatQueue ()/ ()/構造空隊列構造空隊列IsEmptyIsEmpty()/()/如果隊列為空，則返回如果隊列為空，則返回truetrue，否則返回，否則返回falsefalseIsFullIsFull () / () /如果隊列為滿，則返回如果隊列為滿，則返回truetrue，否則返回，否則返回falsefalseGetFrontGetFront() /() /返回隊頭元素返回隊頭元素EnQueue(xEnQueue(x) /) /向隊列添加元素（進隊）向隊列添加元素（進隊）DeQueue(xDeQueue(x) /) /從隊列取出元

5、素（出隊）從隊列取出元素（出隊） 3.7.1 3.7.1 隊列順序存儲隊列順序存儲 l概念概念: :是將隊列中的數據元素連續順序地存放于存儲是將隊列中的數據元素連續順序地存放于存儲器相鄰的單元器相鄰的單元, ,來保證隊列數據元素邏輯上的有序性。來保證隊列數據元素邏輯上的有序性。1.1.frontfront指針不動指針不動 圖圖3.7.1 3.7.1 隊列出隊前隊列出隊前1 1A2 2MaxSizMaxSize-1e-13 34 40 0frontfront rearrear BCDX0 0A1 1BMaxSize-1MaxSize-12 2C3 3D4 4front front rear re

6、ar 圖圖3.7.2 3.7.2 隊列出隊后（元素前移）隊列出隊后（元素前移）算法效率低算法效率低2。front或或rear后移一個位置后移一個位置：一維數組一維數組sqMfront=-1rear=-1123450隊空隊空123450frontJ1,J1,J3入隊入隊J1J2J3rearrear123450J4,J5,J6入隊入隊J4J5J6front設兩個指針設兩個指針front,rear,約定：約定：rear指示隊尾元素；指示隊尾元素；front指示隊頭元素前一位置指示隊頭元素前一位置初值初值front=rear=-1空隊列條件：空隊列條件：front=rearrearrearfrontr

7、ear123450J1,J2,J3出隊出隊J1J2J3frontfrontfronto 存在問題：存在問題：n 當當front=-1,rear=M-1front=-1,rear=M-1時，再有元素入隊發生溢出時，再有元素入隊發生溢出真溢出真溢出n 當當frontfront -1,rear=M-1-1,rear=M-1時，再有元素入隊發生溢出時，再有元素入隊發生溢出假溢出假溢出o 解決方案：解決方案：循環隊列循環隊列基本思想：把隊列基本思想：把隊列設想成環形設想成環形，讓，讓sq0sq0接在接在sqM-1sqM-1之后，若之后，若rear+1=M,rear+1=M,則令則令rear=0;rear

8、=0;0M-11frontrear.實現：利用實現：利用“模模”運算運算入隊：入隊：rear=(rear+1)%M;rear=(rear+1)%M;sqrear=x;sqrear=x;出隊：出隊： front=(front+1)%M; front=(front+1)%M; x=sqfront;x=sqfront;隊滿、隊空判定條件隊滿、隊空判定條件012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態初始狀態J4,J5,J6出隊出隊J7,J8,J9入隊隊空：隊空：front=rear隊滿：隊滿：front=rear

9、解決方案：解決方案：1.另外另外設一個標志設一個標志以區別隊空、以區別隊空、隊滿隊滿2.少用一個元素空間少用一個元素空間： 隊空：隊空：front=rear 隊滿：隊滿：(rear+1)%M=frontreartypedef structEType *element;/一維數組一維數組 intfront;intrear;intMaxSize; Queue；QueueQ，Q1，Q2；viod CreatQueue (Queue &Q , int &MaxQueueSize)/ 構造一個最大容量為構造一個最大容量為MaxQueueSize 的隊列的隊列Q Q.MaxSize = M

10、axQueueSize; Q.element = EType Q.MaxSize+1; Q.front = 0; Q.rear = 0;圖圖3.7.12 循環隊列的順序存儲循環隊列的順序存儲*elementfront=0rear=001MaxSizen-1MaxSizebool IsEmpty(Queue &Q)/ 判斷隊列判斷隊列Q是否為空是否為空if (Q.front = Q.rear) return true;return false;bool IsFull(Queue &Q)/ 判斷隊列判斷隊列Q是否為滿是否為滿if (Q.front = (Q.rear+1) % (Q

11、.MaxSize+1) return true;return false; Status GetFront(Queue &Q , EType &x)/ 返回隊列返回隊列Q中隊頭元素中隊頭元素if (IsEmpty (Q) return ERROR;x = Q.element(Q.front+1) % (Q.MaxSize+1); return OK;Status Enqueue(Queue &Q , EType &x)/ x進進Q隊列，返回進隊列后的狀態值隊列，返回進隊列后的狀態值if (IsFull(Q) return ERROR;Q.rear = (Q.re

12、ar+1) % (Q.MaxSize+1);Q.elementQ.rear = x; return OK;Status DeQueue(Queue &Q , EType &x)if (IsEmpty(Q) return ERROR;Q.front=(Q.front+1)% (Q.MaxSize+1);x = Q.elementQ.front; return OK; 隊空條件隊空條件 : front = rear (初始化時：初始化時：front = rear )隊滿條件隊滿條件： front = (rear) % N (N=maxsize)隊列長度隊列長度（即數據元素個數）（即

13、數據元素個數）：L=（Nrearfront）% N J2 J3J1 J4 J5frontrear循環隊列循環隊列總結（總結（人為浪費一個單元）人為浪費一個單元）：即即front和和rear二者之一指向實元素，另一個指向空閑元素。二者之一指向實元素，另一個指向空閑元素。 問問3： 在具有在具有n個單元的循個單元的循環隊列中，隊滿時共有多少環隊列中，隊滿時共有多少個元素？個元素？ 問問1：左圖中隊列：左圖中隊列maxsize N=？問問2：左圖中隊列長度：左圖中隊列長度L=？n-1個個6 5（）（） rf （）（）（nfr）% n （）（）nrf （）（） （nrf）% n要分析要分析4 4種公式

14、哪種最合理？種公式哪種最合理？當當 r f 時（時（A）合理；）合理；當當 r front = NULL;Q-rear = NULL; return Q;bool IsEmpty(ChainQueue *Q)/ 判斷隊列判斷隊列Q是否為空是否為空if (!Q-front) return true;return false; Status GetFront(ChainQueue *Q , EType &x)/ 返回隊列返回隊列Q中隊列頂元素至中隊列頂元素至xif (IsEmpty(Q) return ERROR;ChainNode *p= Q-front;x = p-data; retu

15、rn OK;a1pQ.frontQ.rearxq4）鏈式隊列進隊運算）鏈式隊列進隊運算 Status EnQueue(ChainQueue *Q , EType &x)/ x進進Q隊列，返回進隊列后的狀態值隊列，返回進隊列后的狀態值QueueNode *q = new QueueNode;q -data=x;q -link=NULL;QueueNode *p = Q-rearp-link=q;Q-rear = q; return OK;a1a2anQ.frontQ.rearanQ.frontQ.rearpp5）鏈式隊列出隊運算）鏈式隊列出隊運算 當隊列中只有一個元素時當隊列中只有一個元

16、素時:Q.rearStatus DeQueue (ChainQueue *Q , EType &x)/ 將將Q隊列頂的值取至隊列頂的值取至x中，返回出隊列后中，返回出隊列后的狀態值的狀態值if (IsEmpty(Q) return ERROR;QueueNode *p = Q.front;x = Q.front -data;Q.front = Q.front -link;delete p; return OK;程序設計程序設計l1 1。順序隊列構建、進隊、出隊運算。順序隊列構建、進隊、出隊運算。l2 2。鏈式隊列構建、進隊、出隊運算。鏈式隊列構建、進隊、出隊運算。l要求：從鍵盤輸入數據

17、元素要求：從鍵盤輸入數據元素5 5個個student(student(定定義如下義如下), ), 給出結果。給出結果。typedef structintnum; /學號學號 char name10; /姓名姓名 student；typedef student EType;調度道（中間多條車道）調度道（中間多條車道） 列車重排列車重排 進車道：進車道：3 4 2 5 1 7 6出車道：出車道： 7， 6， 5， 4， 3， 2， 1調度道（中間多條車道）調度道（中間多條車道） 7 6 51 432進車道：進車道：出車道：出車道：p對于每個車皮的進入，采用同一運算方法進入對于每個車皮的進入，采用同

18、一運算方法進入備用車道。數據的備用車道。數據的“隊列隊列”結構結構: :從一頭進入，從一頭進入，從另一頭出去。從另一頭出去。隊列9,8,7 9,8,7 6,5,4 6,5,4 入軌入軌出軌出軌緩沖鐵軌緩沖鐵軌3,6,1,9,8,5,2,4,73,6,1,9,8,5,2,4,73,2,1 3,2,1 圖圖3.9.1 3.9.1 車廂調度轉軌車廂調度轉軌 l該緩沖鐵軌中現有各車廂的編號均小于該緩沖鐵軌中現有各車廂的編號均小于currentcurrent車廂的編號；車廂的編號；如果有多個緩沖鐵軌都滿足這一條件，則選擇一如果有多個緩沖鐵軌都滿足這一條件，則選擇一個緩沖鐵軌隊尾（左端）車廂編號最大的緩沖

19、鐵個緩沖鐵軌隊尾（左端）車廂編號最大的緩沖鐵軌；軌；如果已有車廂的緩沖鐵軌中，隊尾車廂編號都大如果已有車廂的緩沖鐵軌中，隊尾車廂編號都大于于currentcurrent，則，則currentcurrent選擇一個空的緩沖鐵軌選擇一個空的緩沖鐵軌（如果存在）進入。（如果存在）進入。如果也無空緩沖鐵軌，則無法調度。如果也無空緩沖鐵軌，則無法調度。開始時創建一個指向開始時創建一個指向k k個隊列的表頭數組個隊列的表頭數組QkQk ，其中，其中，QiQi （i=1,2,i=1,2,k,k）表示第）表示第i i個緩沖鐵軌（隊列）。個緩沖鐵軌（隊列）。NowOutNowOut是下一個要輸出至出軌的車廂號。

20、是下一個要輸出至出軌的車廂號。minHminH是已進入各緩沖鐵軌中最小的車廂號是已進入各緩沖鐵軌中最小的車廂號; ;minQminQ是是minHminH號車廂所在的緩沖鐵軌（即隊號車廂所在的緩沖鐵軌（即隊列編號）。列編號）。#include #include #include #include #include iostream.h#include intint r10=0,7,4,2,5,8,9,1,6,3; r10=0,7,4,2,5,8,9,1,6,3;#define #define MaxQueueSizeMaxQueueSize 9 9typedef structtypedef st

21、ruct Queue;Queue;bool IsEmpty(Queuebool IsEmpty(Queue &Q) &Q)bool IsFull(Queuebool IsFull(Queue &Q) &Q)void CreatQueuevoid CreatQueue (Queue &Q) (Queue &Q)bool Enqueue(Queue &Q , intbool Enqueue(Queue &Q , int &x) &x)bool GetFront(Queue &Q , int &x)boo

22、l GetFront(Queue &Q , int &x)bool GetRear(Queue &Q , intbool GetRear(Queue &Q , int &x) &x)bool DeQueue(Queue &Q , int &x)bool DeQueue(Queue &Q , int &x)bool RearrangementTrack (int r, int n, intbool RearrangementTrack (int r, int n, int k) k) Queue Queue * *Q

23、 = new Queuek+1;Q = new Queuek+1;/ / 創建創建k k個緩沖鐵軌隊列個緩沖鐵軌隊列H Hint NowOutint NowOut = 1; / = 1; / 當前應該輸出的車廂編號當前應該輸出的車廂編號int minHint minH = n+1; / = n+1; / 緩沖鐵軌中編號最小的車廂編號，緩沖鐵軌中編號最小的車廂編號，目前假設為目前假設為n+1(9+1=10)n+1(9+1=10)int minQ,i; / minHint minQ,i; / minH車廂對應的緩沖鐵軌編號車廂對應的緩沖鐵軌編號for ( i= 0; i5; i+) for ( i

24、= 0; i5; i+) CreatQueue(QiCreatQueue(Qi););Queue *Q ;Q=new Queue2;for ( i= 0; i2; i+) CreatQueue(Qi); typedef structEType *element;/一維數組一維數組 intfront;int rear;intMaxSize; Queue；for ( i = 1; i=n; i+) / 重排車廂重排車廂if (ri = NowOut) / 當前到站的車廂編號是剛剛出站的車廂編號后一個，直接輸出當前到站的車廂編號是剛剛出站的車廂編號后一個，直接輸出cout 從入軌輸出車廂從入軌輸出車

25、廂 ri 到出軌到出軌 endl;NowOut+;while (minH = NowOut)Output(minH, minQ, Q, k, n);NowOut+;else 將將ri送入某個緩沖鐵軌送入某個緩沖鐵軌if (!Hold(ri, minH, minQ, Q, k)return false;return true;void Output(int & minH, int &minQ, Queue Q, int k, int n)bool Hold(int current, int& minH, int &minQ, Queue Q, int k)對于不能

26、同時選擇的投資項目稱為沖突項目。對于不能同時選擇的投資項目稱為沖突項目。核算各種項目組合的資金需求總量，如某種核算各種項目組合的資金需求總量，如某種項目組合的資金需求總量超過已擁有的定量項目組合的資金需求總量超過已擁有的定量資金，則認為該種組合不可行；資金，則認為該種組合不可行；如存在多個組合方案的資金需求總量都不超如存在多個組合方案的資金需求總量都不超過已擁有的資金總量，則企業經營者再從中過已擁有的資金總量，則企業經營者再從中選擇投資回報率最大化的投資組合。選擇投資回報率最大化的投資組合。圖3.9.2 沖突關系矩陣r =000001100001000101011011010100101100

27、100000100011012345673456712010000080101100900000018000110001900集合集合A=1,2,3,4,5,6,7,8,9A=1,2,3,4,5,6,7,8,9該沖突關系矩陣將用于劃分子集處理算法，該沖突關系矩陣將用于劃分子集處理算法，判斷哪些項目可組合在同一個子集中。判斷哪些項目可組合在同一個子集中。1.1. 將隊列中的所有元素逐個出隊一次，每次第將隊列中的所有元素逐個出隊一次，每次第一個出隊的項目編號作為進入新子集的第一一個出隊的項目編號作為進入新子集的第一個項目個項目; ;2.2. 以后出隊的元素與已進入當前子集的項目進以后出隊的元素與已進入當前子集的項目進行比較，如不與進入當前子集的任何項目發行比較，如不與進入當前子集的任何項目發生沖突，則作為進入當前子集的項目生沖突，則作為進入當前子集的項目; ;3.3. 凡是屬于當前子集的項目不再進隊，不屬于凡是屬于當前子集的項目不再進隊，不屬于當前子集的就再次進入隊列當前子集的就再次進入隊列Q;Q;4.4. Q Q中的元素全部出隊一次，就篩選出一個子集，中的元素全部出隊一次，就篩選出一個子集，重