【正文】 QueuePtr front。 ? 棧滿條件： = MAXQSIZE ? 棧空條件： = 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 43/51 順序存儲方式 ? 順序存儲方式的缺點 Job 1 Job 2 Job 3 Job 4 Job 5 Job 6 Job 7 ?1 0 1 2 3 4 5 6 ? append Job 1 ? append Job 2 ? append Job 3 ? serve Job 1 ? append Job 4 ? append Job 5 ? append Job 6 ? serve Job 2 ? append Job 7 ? append Job 8 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 44/51 順序存儲方式 解決的方法 (循環(huán)隊列 ) [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] Job 1 Job 2 Job 3 Job 4 Job 5 Job 6 ? append Job 1 ? append Job 2 ? append Job 3 ? serve Job 1 ? append Job 4 ? append Job 5 ? append Job 6 ? serve Job 2 ? append Job 7 7 ? append Job 8 Job 8 = 3 =3 加入新元素： rear++ 加入 job 移去隊列頭的元素 ，然后 front “++” empty or full ? 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 45/51 順序存儲方式 ? 隊列空還是滿的判斷 ? 在隊列中預(yù)留一個空位 ? 設(shè)定一個標志 ? 設(shè)置一個數(shù)字計數(shù)器 [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 46/51 順序存儲方式 ? 在隊列中預(yù)留一個空位 ? 犧牲一個元素空間，來區(qū)別隊空或隊滿。e) 刪除隊列頭的元素，用 e返回其值 ? QueueEmpty( Q ) 判定隊列是否為空 (TRUE/FALSE) ? GetHead( Q , amp。 Push( S , temp )。 //起始塔編號 char y。 while( !empty( S ) ) { Pop( S , i )。 if( n = 1 ) return 1。 } 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 20/51 鏈式存儲結(jié)構(gòu)上棧操作的實現(xiàn) ? 出棧操作 Pop(amp。 struct LNode *next。 else { pSelem[ pStop ] = e； ++(pStop)； return OK。 } void main() { PSeqStack *pS pS = NULL。 相當于線性表的 DELET(L, n) ? GetTop(S,amp。e) 取棧頂元素函數(shù) ， 與 POP(S)的差別在不刪除棧頂元素 ， 相當于線性表的 GET(L, n) 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 7/51 第三章 棧和隊列 ? 棧的基本概念和特性 ? 棧的基本操作 ? 棧的順序存儲方式和鏈式存儲方式及其上的操作 ? 棧的應(yīng)用 ? 隊列的基本概念和特性 ? 隊列的基本操作 ? 隊列的順序存儲方式和鏈式存儲方式及其上的操作 ? 隊列的應(yīng)用 ? 本章小結(jié) 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 8/51 順序存儲方式實現(xiàn)－使用數(shù)組 define ARRMAX = N。 InitStack( amp。 } } 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 14/51 順序存儲結(jié)構(gòu)上棧操作的實現(xiàn) ? 出棧操作 Pop(amp。 }LNode,*LinkList。S , amp。 return ( res*Fact( n1 ) )。 if( i = 1 ) { i = 1。 //輔助塔編號 char z。 = 1。e ) 用 e返回隊列的隊頭元素 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 38/51 第三章 棧和隊列 ? 棧的基本概念和特性 ? 棧的基本操作 ? 棧的順序存儲方式和鏈式存儲方式及其上的操作 ? 棧的應(yīng)用 ? 隊列的基本概念和特性 ? 隊列的基本操作 ? 隊列的順序存儲方式和鏈式存儲方式及其上的操作 ? 隊列的應(yīng)用 ? 本章小結(jié) 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 39/51 鏈式存儲方式 typedef struct QNode { QElemType data。 ? 入隊前，先判 +1是否等于 ?+1 == ,若是則為隊滿 ? == ，為隊空 ? 設(shè)一個標志位用來區(qū)別隊列是空還是滿 ? 初始化隊列時： =，標志位為 FALSE ? 入隊后，使 =+1，則置標志位為 TRUE ? 出隊后，將標志位置為 FALSE ? 當 =, 且標志位為 TRUE時，隊列滿 ? 當 =, 但標志位為 FALSE時，隊列空 ? 其他為非空非滿 電子科大科 園 培訓中心 數(shù)據(jù)結(jié)構(gòu) 2022年 10月 23日星期日 47/51 順序存儲方式 ? 計數(shù)變量 ? 初始化隊列時 c := 0。 }QNode , *QueuePtr。 =,=。 InitStack(S)。 Pop( S , i