第三章 數(shù)據(jù)結構與算法_線性結構(三)

1、2.3 隊列及實現(xiàn)1. 定義（queue） 只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。 與一般線性表的區(qū)別：僅在于運算規(guī)則不同。2. 構成隊頭（front）：在表中只允許進行刪除的一端；隊尾(rear)：只允許進行插入另一端。舉例：舉例：注意： 空隊（無元素）隊頭與隊尾相遇邏輯結構（a1a2a3）a3a2a1隊隊頭頭隊隊尾尾3. 運算規(guī)則 只能在隊頭和隊尾運算，且訪問結點時按照先進先出（FIFO）的原則。4. 邏輯結構 與線性表相同，仍為一對一( 1:1)關系。5. 主要運算 （1）入隊在隊尾插入元素； （2）出隊在隊頭刪除元素。6. 基本操作 入隊或出隊，建空隊列，判隊空

2、或隊滿等操作。7. 存儲結構（兩種） 順序隊列，隊列的數(shù)組表示，使用時常被臆想為一個環(huán)狀空間，因此又稱為循環(huán)隊列。 鏈隊列，隊列的鏈式表示，適于用戶無法預估空間的情況。8.隊列的抽象數(shù)據(jù)類型描述類型名稱：隊列(Queue)數(shù)據(jù)對象集：一個有0個或多個元素的有窮線性表。操作集：長度為MaxSize的隊列Q，隊列元素item；1、Queue CreatQueue( int MaxSize )：生成長度為MaxSize的空隊列；2、int IsFullQ( Queue Q, int MaxSize )：判斷隊列Q是否已滿；3、void AddQ( Queue Q, ElementType item

3、)： 將數(shù)據(jù)元素item插入隊列Q中；4、ElementType DeleteQ( Queue Q )：將隊頭數(shù)據(jù)元素從隊列中刪除并返回。5、int IsEmptyQ( Queue Q )： 判斷隊列Q是否為空；9.隊列的順序存儲實現(xiàn)隊列的順序存儲結構通常由一個一維數(shù)組和一個記錄隊列頭元素位置的變量front以及一個記錄隊列尾元素位置的變量rear組成。將隊列頭放數(shù)組下標小的位置，而將隊列尾放在數(shù)組下標大的位置。一般front和rear先初始化-1。當有元素入隊，rear向右移動一格（加1），放在隊尾元素；當有元素出隊，front向右移動一格（加1），再刪除對頭元素。#define MaxSi

4、ze struct QNode ElementType Data MaxSize ;int rear;int front;typedef struct QNode *Queue;隨著入隊、出隊操作的進行，會使整個隊列整體向后移動，這樣就出現(xiàn)隊尾指針已經移到了最后，再有元素入隊就會出現(xiàn)溢出，而事實上此時隊中并未真的“滿員”，這種現(xiàn)象稱為“假溢出”。例 一個工作隊列Front0Job 1Rear1Job 2Front2Job 3Rear3Job 44Job 5Rear5Job 66Job 7RearAddQ Job 1AddQ Job 4AddQ Job 7AddQ Job 2AddQ Job 5

5、AddQ Job 8AddQ Job 3AddQ Job 6DeleteQ Job 1DeleteQ Job 2(a) 空隊列空隊列Q.frontQ.rear(b) 入隊入隊3個元素個元素a3a2a1Q.frontQ.rear(c) 出隊出隊3個元素個元素Q.frontQ.rear(d) 入隊入隊2個元素個元素a5a4Q.frontQ.rear為充分利用向量空間，克服上述“假溢出”現(xiàn)象的方法是：將為隊列分配的數(shù)組看成為一個首尾相接的圓環(huán)，并稱這種隊列為循環(huán)隊列(Circular Queue)。 在循環(huán)隊列中進行出隊、入隊操作時，隊首、隊尾指針仍要加1，朝前移動。只不過當隊首、隊尾指針指向數(shù)組(

6、MAX_QUEUE_SIZE-1)時，其加1操作的結果是指向數(shù)組的下界0。這種循環(huán)意義下的加1操作可以描述為：if (i+1=MAX_QUEUE_SIZE) i=0;else i+ ;其中： i代表隊首指針(front)或隊尾指針(rear)用模運算可簡化為：i=(i+1)%MAX_QUEUE_SIZE ; 顯然，為循環(huán)隊列所分配的空間可以被充分利用，除非向量空間真的被隊列元素全部占用，否則不會上溢。因此，真正實用的順序隊列是循環(huán)隊列。 例：設有循環(huán)隊列QU0，5，其初始狀態(tài)是front=rear=0，各種操作后隊列的頭、尾指針的狀態(tài)變化情況如下圖所示。 (a) 空隊列空隊列(b) d, e,

7、 b, g入入隊隊(c) d, e出隊出隊 入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。因此，無法通過front=rear來判斷隊列“空”還是“滿”。解決此問題的方法是：約定入隊前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認為隊滿。即： front所指的單元始終為空。(d) i, j, k入入隊隊(e) b, g出隊出隊(f) r, p, s, t入隊入隊 循環(huán)隊列為空：front=rear 。 循環(huán)隊列滿：(rear+1)%MAX_QUEUE_SIZE =front。（1）循環(huán)隊列的插入（Front和rear指針的移動采用“加1取余”法，

8、體現(xiàn)了順序存儲的“循環(huán)使用”。）void AddQ( Queue PtrQ, ElementType item)if ( (PtrQ-rear+1) % MaxSize = PtrQ-front ) printf(“隊列滿”);return;PtrQ-rear = (PtrQ-rear+1)% MaxSize;PtrQ-DataPtrQ-rear = item;（2）循環(huán)隊列的刪除（Front和rear指針的移動采用“加1取余”法，體現(xiàn)了順序存儲的“循環(huán)使用”。）ElementType DeleteQ ( Queue PtrQ )if ( PtrQ-front = PtrQ-rear ) pr

9、intf(“隊列空”);return ERROR; else PtrQ-front = (PtrQ-front+1)% MaxSize;return PtrQ-DataPtrQ-front;10.隊列的鏈式存儲實現(xiàn)隊列的鏈式存儲結構也可以用一個單鏈表實現(xiàn)。插入和刪除操作分別在鏈表的兩頭進行； 需要兩類不同的結點：數(shù)據(jù)元素結點，隊列的隊首指針和隊尾指針的結點。struct NodeElementType Data;struct Node *Next;struct QNode/* 鏈隊列結構 */struct Node *rear; /* 指向隊尾結點 */struct Node *front;

10、/* 指向隊頭結點 */;typedef struct QNode *Queue;Queue PtrQ;PtrQfrontrear 鏈隊運算及指針變化 鏈隊的操作實際上是單鏈表的操作，只不過是刪除在表頭進行，插入在表尾進行。插入、刪除時分別修改不同的指針。鏈隊運算及指針變化如圖所示。(a) 空隊列空隊列front rear(b) x入隊入隊 x front rear(c) y再入隊再入隊 y front rear x(d) x出隊出隊 y xfront rear不帶頭結點的鏈式隊列出隊操作的一個示例：ElementType DeleteQ ( Queue PtrQ ) struct Node

11、*FrontCell;ElementType FrontElem;if ( PtrQ-front = NULL) printf(“隊列空隊列空”); return ERROR;FrontCell = PtrQ-front;if ( PtrQ-front = PtrQ-rear) /* 若隊列只有一個元素 */ PtrQ-front = NULL; /* 刪除后隊列置為空 */ PtrQ-rear = NULL; elsePtrQ-front = PtrQ-front-Next;FrontElem = FrontCell-Data;free( FrontCell );return FrontElem;/* 釋放被刪除結點空間 */作業(yè)1 循環(huán)隊列的優(yōu)點是什么?如何判斷它的空和滿?2 設有一個靜態(tài)順序隊列，向量大小為MAX，判斷隊列為空的條件是什么？隊列滿的條件是什么？3 設有一個靜態(tài)循環(huán)隊列，向量大小為MAX，判斷隊列為空的條件是什么？隊列滿的條件是什么？4.設Q0,6是一個靜態(tài)順序隊列，初始狀態(tài)為front=rear=0，請畫出做完下列操作后隊列的頭尾指針的狀態(tài)變化情況，若不能入對，請指出其元素，并說明理由。a, b, c, d入隊