第三章數(shù)據(jù)結(jié)構(gòu)隊列

1、也是一種運算受限的線性表。它只允許在表的一端進行插入，而在另一端進行刪除。允許刪除的一端稱為，允許插入的一端稱為。例如：排隊購物。操作系統(tǒng)中的作業(yè)排隊。先進入隊列的成員總是先離開隊列。因此隊列亦稱作先進先出(First In First Out)的線性表，簡稱。當隊列中沒有元素時稱為。在空隊列中依次加入元素a1,a2,an之后，a1是，an是。顯然退出隊列的次序也只能是a1,a2,an ，也就是說隊列的修改是依先進先出的原則進行的。3.4 隊列的類型定義隊列的類型定義 ADT Queue 數(shù)據(jù)對象：數(shù)據(jù)對象： Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系：

2、R1 | ai-1, ai D, i=2,.,n 約定其中a1 端為隊列頭隊列頭， an 端為隊列尾隊列尾基本操作：基本操作：隊列的抽象數(shù)據(jù)類型定義隊列的抽象數(shù)據(jù)類型定義 ADT Queue隊列的基本操作：隊列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTraverse(Q, visit()InitQueue(&Q) 操作結(jié)果：

3、操作結(jié)果：構(gòu)造一個空隊列Q。DestroyQueue(&Q)初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：隊列Q被銷毀， 不再存在。 QueueEmpty(Q)初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：若Q為空隊列，則返回TRUE，否則返回FALSE。 QueueLength(Q) 初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：返回Q的元素個數(shù)，即隊列的長度。 GetHead(Q, &e) 初始條件：初始條件：Q為非空隊列。 操作結(jié)果：操作結(jié)果：用e返回Q的隊頭元素。a1a2an ClearQueue(&Q)初始條件：初始條件：隊列Q已

4、存在。 操作結(jié)果：操作結(jié)果：將Q清為空隊列。 EnQueue(&Q, e) 初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：插入元素e為Q的新的隊尾元素。a1a2ane DeQueue(&Q, &e) 初始條件：初始條件：Q為非空隊列。 操作結(jié)果：操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。a1a2an 3.5 隊列類型的實現(xiàn)隊列類型的實現(xiàn)鏈隊列鏈隊列鏈式映象循環(huán)隊列循環(huán)隊列順序映象 typedef struct QNode / 結(jié)點類型結(jié)點類型 QElemType data; struct QNode *next; QNode, *QueuePtr;鏈隊列鏈隊

5、列鏈式映象typedef struct / 鏈隊列類型鏈隊列類型 QueuePtr front; / 隊頭指針隊頭指針 QueuePtr rear; / 隊尾指針隊尾指針 LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空隊列空隊列非空隊列非空隊列 Status InitQueue (LinkQueue &Q) / 構(gòu)造一個空隊列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存儲分配失敗 Q.front-next = NULL; r

6、eturn OK; Status DestroyQueue (LinkQueue &Q) / 銷毀隊列Q while(Q.front) Q.rear=Q.front-next; free(Q.front); Q.front = Q.rear; return OK; Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e為Q的新的隊尾元素(尾插法） p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存儲分配失敗 p-data = e; p-next = N

7、ULL; Q.rear-next = p; Q.rear = p; return OK; Status DeQueue (LinkQueue &Q, QElemType &e) / 若隊列不空，則刪除Q的隊頭元素，（頭刪法） /用 e 返回其值，并返回OK；否則返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; /第一個結(jié)點也是最后一個結(jié)點 free (p); retur

8、n OK;非循環(huán)隊列（順序隊列）非循環(huán)隊列（順序隊列）隊列的順序存儲結(jié)構(gòu)稱為順序隊列，順序隊隊列的順序存儲結(jié)構(gòu)稱為順序隊列，順序隊列實際上是運算受限的順序表，和順序表一樣，列實際上是運算受限的順序表，和順序表一樣，順序隊列也是必須用一個地址連續(xù)的空間來存放順序隊列也是必須用一個地址連續(xù)的空間來存放當前隊列中的元素。由于隊列的隊頭和隊尾的位當前隊列中的元素。由于隊列的隊頭和隊尾的位置是變化的，因而要設兩個指針和分別指示隊頭置是變化的，因而要設兩個指針和分別指示隊頭和隊尾元素在隊列中的位置，它們的初始值在隊和隊尾元素在隊列中的位置，它們的初始值在隊列初始化時均應置為。入隊時列初始化時均應置為。入隊

9、時先將新元素插入先將新元素插入所指的位置，然后加所指的位置，然后加。出隊時，。出隊時，先刪去所指的先刪去所指的元素，然后加元素，然后加并返回被刪元素。由此可見，當并返回被刪元素。由此可見，當頭尾指針相等時隊列為空。頭尾指針相等時隊列為空。 0 1 2 3frontrearabcfront rear (a)隊列初始為空（b）A,B,C入隊 b c front rear front rear（c) a出隊 (d) b,c出隊，隊為空 n隊空：隊空：Q.front=Q.rearn隊滿：隊滿：Q.rear-Q.front=maxsize（求隊（求隊長）長）n 入隊：新元素按入隊：新元素按 rear 指

10、示位置加入，指示位置加入，再將隊尾指針加一再將隊尾指針加一 ，即，即 Q.rear = Q.rear + 1n 出隊：將出隊：將front指示的元素取出，再將隊指示的元素取出，再將隊頭指針加一，即頭指針加一，即 Q.front = Q.front + 1非循環(huán)隊列（順序隊列）非循環(huán)隊列（順序隊列） 012345Q.rearQ.frontJ4J5J6012345Q.rearQ.frontJ3J8J7J3J4J5012345Q.rearQ.front初始狀態(tài)J3,J4,J5出隊J6,J7,J8入隊如何判斷隊空隊滿現(xiàn)象？如何判斷隊空隊滿現(xiàn)象？隊空：Q.front=Q.rear隊滿：Q.front=Q

11、.rear解決方案解決方案：1.另外設一個標志以區(qū)別隊空、隊滿2.少用一個元素空間： 隊空：Q.front=Q.rear 隊滿：(Q.rear+1)%M=Q.front即隊列頭指針在隊列尾指針的下一位置（指環(huán)狀的下一位置）上012345Q.rearQ.frontJ4J5J6012345Q.rearQ.frontJ3J7J3J4J5012345Q.rearQ.front當前狀態(tài)J3,J4,J5出隊J6,J7入隊隊空：Q.front=Q.rear隊滿：(Q.rear+1)%M=Q.front解決方案：解決方案：少用一個元素空間：012345Q.rearQ.front初始狀態(tài)J0,J1,J2,J3,

12、J4,J5入隊入隊J0,J1,J2出隊出隊隊空：Q.front =Q. rear隊滿： Q.front =(Q.rear + 1) % MAXQSIZE入隊: 1)隊列不滿 2)Q.rear = (Q.rear + 1) % MAXQSIZE出隊: 1)隊列不空 2)Q.front = (Q.front + 1) % MAXQSIZE求隊長求隊長:(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE循環(huán)隊列循環(huán)隊列#define MAXQSIZE 100 /最大隊列長度 typedef struct QElemType *base; / 動態(tài)分配存儲空間 int front;

13、/ 頭指針，若隊列不空， / 指向隊列頭元素 int rear; / 尾指針，若隊列不空，指向 / 隊列尾元素 的下一個位置 SqQueue;循環(huán)隊列循環(huán)隊列順序映象 Status InitQueue (SqQueue &Q) / 構(gòu)造一個空隊列Q Q.base = (QElemType *) malloc (MAXQSIZE *sizeof (QElemType); if (!Q.base) exit (OVERFLOW); / 存儲分配失敗 Q.front = Q.rear = 0; return OK; Status EnQueue (SqQueue &Q, ElemTy

14、pe e) / 插入元素e為Q的新的隊尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /隊列滿 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; Status DeQueue (SqQueue &Q, ElemType &e) / 若隊列不空，則刪除Q的隊頭元素， / 用e返回其值，并返回OK; 否則返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q

15、.front+1) % MAXQSIZE; return OK;第 1 行 1 1第 2 行 1 2 1 第 3 行 1 3 3 1第 4 行 1 4 6 4 1二項式系數(shù)值（楊輝三角）設第 i-1行的值：(a0=0) a1.ai (ai+1=0)則第 i 行的值：bj = aj-1+aj, j=1,2,i+1利用循環(huán)隊列計算二項式的過程：假設只計算四行，則隊列的最大容量為 5。1 1 00q.frontq.rear1 1 001q.frontq.rear1 1 021q.frontq.rear1 1 021q.frontq.rear1 0 021q.frontq.rear1 0 121q.f

16、rontq.rear1 0 121q.frontq.rear1 0 123q.frontq.rear1 0 133q.frontq.rear1 0 131q.frontq.reardo DeQueue(Q, s); GetHead(Q, e); if (e!=0) printf (“%d”, e); EnQueue(Q, s+e); while (e!=0); 1. 掌握棧和隊列類型的特點，并能在相應掌握棧和隊列類型的特點，并能在相應的應用問題中正確選用它們。的應用問題中正確選用它們。2. 熟練掌握棧類型的兩種實現(xiàn)方法，特別應熟練掌握棧類型的兩種實現(xiàn)方法，特別應注意棧滿和?？盏臈l件以及它們的描述方法。注意棧滿和?？盏臈l件以及它們的描述方法。3. 熟練掌握循環(huán)隊列和鏈隊列的基本操作實熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法，