深圳大學(xué)-數(shù)據(jù)結(jié)構(gòu)-2017棧和隊(duì)列演示文檔

.,第三章棧和隊(duì)列,數(shù)據(jù)結(jié)構(gòu),.,一、棧,2,第一節(jié)棧,棧是限定僅在表尾(top)進(jìn)行插入或刪除操作的線性表。允許插入和刪除的一端稱為棧頂(top，表尾)，另一端稱為棧底(bottom，表頭)特點(diǎn)：后進(jìn)先出 (LIFO),.,二、棧的實(shí)現(xiàn),3,第一節(jié)棧,棧的存儲(chǔ)結(jié)構(gòu)主要有兩種：1. 順序棧2. 鏈?zhǔn)綏?.,一、順序棧,4,第二節(jié)順序棧,順序棧是棧的順序存儲(chǔ)結(jié)構(gòu)利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素指針top指向棧頂元素在順序棧中的下一個(gè)位置，base為棧底指針，指向棧底的位置。,.,二、順序棧的定義,5,第二節(jié)順表?xiàng)?采用C語(yǔ)言中動(dòng)態(tài)分配的一維數(shù)組表示順序表,#define STACK_INIT_SIZE 100 /棧存儲(chǔ)空間的初始分配量#define STACKINCREMENT 10 /棧存儲(chǔ)空間的分配增量typedef struct SElemType*base /存儲(chǔ)空間基址SElemType*top; /棧頂指針int stacksize; /當(dāng)前分配的存儲(chǔ)容量(元素?cái)?shù)) SqStack;,.,三、順序棧的特性,6,第二節(jié)順序棧,top=0 或top=base 表示空棧base=NULL表示棧不存在當(dāng)插入新的棧頂元素時(shí),指針top+1刪除棧頂元素時(shí)，指針top-1當(dāng)top>stacksize時(shí)，棧滿，溢出,.,四、順序棧的主要操作,7,第二節(jié)順序棧,ADT Stack 數(shù)據(jù)對(duì)象：D = ai | aiElemSet, i=1,2,3,n 數(shù)據(jù)關(guān)系：R = | ai-1,aiD 基本操作： Status InitStack(SqStack &S) / 構(gòu)造空棧 Status Push(SqStack &S, e) / 進(jìn)棧 Status Pop(SqStack &S, &e) / 出棧 Status GetTop(SqStack S, &e)/ 取棧頂元素值 Status StackEmpty(SqStack S) / 棧是否為空 ADT Stack,.,五、創(chuàng)建順序棧,8,第二節(jié)順序棧,Status InitStack(SqStack / InitStack,.,六、進(jìn)棧（插入新元素）,9,第二節(jié)順序棧,Status Push(SqStack / Push,.,七、出棧（刪除元素）,10,第二節(jié)順序棧,Status Pop(SqStack / Pop,.,八、取棧頂元素,11,第二節(jié)順序棧,Status GetTop(SqStack S, SElemType / GetTop,.,1.創(chuàng)建堆棧節(jié)點(diǎn)類template class LinStack;/前視定義,否則友元無(wú)法定義template /模板類型為Tclass StackNode friend class LinStack; /定義類LinStack為友元private: T data; /數(shù)據(jù)元素 StackNode *next; /指針public: StackNode(StackNode *ptrNext = NULL) /構(gòu)造頭結(jié)點(diǎn) next = ptrNext; StackNode(const T,第三節(jié)鏈棧,.,第三節(jié)鏈棧,2.創(chuàng)建鏈?zhǔn)蕉褩ｎ?template class LinStackprivate:StackNode *head;/頭指針int size;/數(shù)據(jù)元素個(gè)數(shù)public:LinStack(void);/構(gòu)造函數(shù)LinStack(void);/析構(gòu)函數(shù)void Push(const T,.,第三節(jié)鏈棧,3.鏈?zhǔn)蕉褩５膶?shí)現(xiàn) template LinStack:LinStack()/構(gòu)造函數(shù) head = new StackNode;/頭指針指向頭結(jié)點(diǎn) size = 0; /size的初值為0template LinStack:LinStack(void)/析構(gòu)函數(shù) StackNode *p, *q; /釋放所有動(dòng)態(tài)申請(qǐng)的結(jié)點(diǎn)空間 p = head;/p指向頭結(jié)點(diǎn) while(p != NULL) /循環(huán)釋放結(jié)點(diǎn)空間 q = p; p = p->next; delete q; template int LinStack:NotEmpty(void) const/堆棧非空否if(size != 0) return 1;else return 0;,.,第三節(jié)鏈棧,template void LinStack:Push(const T/元素個(gè)數(shù)加1,.,第三節(jié)鏈棧,template T LinStack:Pop(void)/出棧 if(size = 0) cout *p = head->next;/p指向棧頂元素結(jié)點(diǎn) T data = p->data;head->next = head->next->next;/原棧頂元素結(jié)點(diǎn)脫鏈delete p;/釋放原棧頂結(jié)點(diǎn)空間size-;/結(jié)點(diǎn)個(gè)數(shù)減1return data;/返回原棧頂結(jié)點(diǎn)的data域值,.,第三節(jié)鏈棧,template T LinStack:GetTop(void)const /取棧頂元素return head->next->data;,.,一、數(shù)值轉(zhuǎn)換,18,第四節(jié)棧的應(yīng)用舉例,將十進(jìn)制轉(zhuǎn)換為其它進(jìn)制(d)，其原理為： N = (N/d)*d + N mod d例1：（1348)10=(2504)8 ，其運(yùn)算過(guò)程如下： N N /8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2,.,一、數(shù)值轉(zhuǎn)換,19,第四節(jié)棧的應(yīng)用舉例,void conversion () InitStack(S); / 創(chuàng)建新棧S scanf (“%d”,N); / 輸入一個(gè)十進(jìn)制數(shù)N while (N) Push(S, N % 8); / 將余數(shù)送入棧中 N = N/8; / 求整除數(shù) while (!StackEmpty(S) / 如果棧不空 Pop(S,e); / 將棧中數(shù)出棧 printf ( "%d", e ); / conversion,.,二、行編輯程序,20,第四節(jié)棧的應(yīng)用舉例,用戶輸入一行字符允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)，可以用退格符“#”及時(shí)更正假設(shè)從終端接受兩行字符： whli#ilr#e（s#*s) 實(shí)際有效行為： while (*s),.,二、行編輯程序,21,第四節(jié)棧的應(yīng)用舉例,例2:對(duì)用戶輸入的一行字符進(jìn)行處理,直到行結(jié)束(“n”)void LineEdit() InitStack(s); ch = getchar(); /從終端接受一個(gè)字符 while (ch != n) switch(ch) case # : Pop(S, c);break; / 僅當(dāng)棧非空時(shí)退棧 case : ClearStack(S); break; default: Push(S, ch); break; / 有效字符進(jìn)棧 ch = getchar(); / 從終端接受一個(gè)字符 /將從棧底到棧頂?shù)臈?nèi)字符傳送到調(diào)用過(guò)程的數(shù)據(jù)區(qū); ,.,第四節(jié)棧的應(yīng)用舉例,三.括號(hào)匹配 假設(shè)一個(gè)算術(shù)表達(dá)式中包括( )、 和 三種形式的括號(hào)，設(shè)計(jì)一個(gè)判別表達(dá)式中括號(hào)是否正確匹對(duì)的程序。1.算法思想： 算術(shù)表達(dá)式中右括號(hào)和左括號(hào)匹配的次序:后到括號(hào)要最先被匹配的“后進(jìn)先出”堆棧操作特點(diǎn)，因此可用一個(gè)堆棧來(lái)進(jìn)行判斷。順序掃描算術(shù)表達(dá)式（表現(xiàn)為一個(gè)字符串）；當(dāng)遇到三種類型的左括號(hào)時(shí)，該括號(hào)進(jìn)棧；當(dāng)遇到某一種類型的右括號(hào)時(shí)，比較當(dāng)前棧頂括號(hào)是否與之匹配，若匹配則退棧，繼續(xù)進(jìn)行判斷；若不匹配，則左右括號(hào)配對(duì)次序不正確，結(jié)束。若字符串當(dāng)前為某一類型的右括號(hào)而堆棧為空，則右括號(hào)多于左括號(hào)，結(jié)束。若字符串掃描結(jié)束而堆棧非空，則左括號(hào)多于右括號(hào)，結(jié)束。若字符串掃描結(jié)束而堆棧為空，則左右括號(hào)匹配正確，結(jié)束。,.,第四節(jié)棧的應(yīng)用舉例,#include #include #include using namespace std;bool brackMatch(string str) /括號(hào)匹配 int i = 0;stack stk; / 使用C+的stack類while(i<str.size() if(stri='('|stri=''|stri='') /出現(xiàn)三種左括號(hào)之一壓棧；否則進(jìn)行匹配判斷 stk.push(stri); else if(stri=')'|stri=''|stri='') /遇到右括號(hào),判斷棧頂元素是否為左括號(hào)，如不為匹配的左括號(hào)，括號(hào)不匹配；否則出棧 if(stri=')' / 左括號(hào)多于右括號(hào),.,四、迷宮求解,24,第四節(jié)棧的應(yīng)用舉例,迷宮求解一般采用“窮舉法”逐一沿順時(shí)針?lè)较虿檎蚁噜弶K（一共四塊東(右)、南(下)，西(左)、北(上)）是否可通，即該相鄰塊既是通道塊，且不在當(dāng)前路徑上用一個(gè)棧來(lái)記錄已走過(guò)的路徑,.,四、迷宮求解,25,第四節(jié)棧的應(yīng)用舉例,.,四、迷宮求解（算法）,第四節(jié)棧的應(yīng)用舉例,設(shè)定當(dāng)前位置為入口位置do 若當(dāng)前位置可通，則 將該位置插入棧頂(Push)； 若該位置是出口，則結(jié)束 否則切換當(dāng)前位置的相鄰方塊為當(dāng)前位置； 否則 若棧不空則 如棧頂位置四周均不可通,則刪除棧頂位置(Pop),并重 新測(cè)試新的棧頂位置 如找到棧頂位置的下一方向未經(jīng)探索，則將該方向方 塊設(shè)為當(dāng)前位置 while(棧不空)；找不到路徑；,.,第四節(jié)棧的應(yīng)用舉例,四、迷宮求解(舉例） 入口int mgm+1n+1= 1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1; 出口,.,第四節(jié)棧的應(yīng)用舉例,求解結(jié)果：迷宮路徑： (1,1) (1,2) (2,2) (3,2) (3,1) (4,1)(5,1) (5,2) (5,3) (6,3) (6,4) (6,5) (5,5) (4,5) (4,6) (4,7) (3,7) (3,8)(4,8) (5,8) (6,8) (7,8) (8,8),.,五、表達(dá)式求值,29,第四節(jié)棧的應(yīng)用舉例,表達(dá)式由操作數(shù)、運(yùn)算符和界限符組成，它們皆稱為單詞操作數(shù)：常數(shù)或變量運(yùn)算符：+, -, *, / 等界限符：(, ), #(表達(dá)式開(kāi)始及結(jié)束符),.,五、表達(dá)式求值,30,第四節(jié)棧的應(yīng)用舉例,設(shè)置兩個(gè)棧：操作數(shù)棧（OPND）運(yùn)算符棧（OPTR）,.,五、表達(dá)式求值,31,第四節(jié)棧的應(yīng)用舉例,運(yùn)算符的優(yōu)先級(jí)關(guān)系,新運(yùn)算符,運(yùn)算符棧頂元素,.,五、表達(dá)式求值（算法）,第四節(jié)棧的應(yīng)用舉例,置運(yùn)算符棧(OPTR)和操作數(shù)棧(OPND)為空#插入OPTR棧；取表達(dá)式第一個(gè)單詞；while(單詞 或 OPTR棧頂元素不為#) 若單詞是操作數(shù)，則插入OPND棧頂，取下一個(gè)單詞否則 OPTR棧頂元素優(yōu)先級(jí)與新運(yùn)算符優(yōu)先級(jí)關(guān)系為：小于,則插入OPTR棧頂，取下一單詞等于,則刪除OPTR棧頂元素，取下一單詞大于,則從OPND棧頂依次取出兩個(gè)操作數(shù)，用從OPTR棧頂取出的元素進(jìn)行計(jì)算，結(jié)果插入OPND棧頂 ,從棧頂取出元素，包括取值及刪除棧頂元素兩個(gè)過(guò)程,.,第四節(jié)棧的應(yīng)用舉例,舉例1:求算術(shù)表達(dá)式1+2*3-4/2的值 計(jì)算順序（1）2*3 （2）1+6 （3）4/2 （4）7-2,.,第四節(jié)棧的應(yīng)用舉例,步驟 OPTR OPND 輸入字符 棧操作 # 1+2*3-4/2# PUSH（OPND,1 ） # 1 +2*3-4/2# PUSH（OPTR,+ ） #+ 1 2*3-4/2# PUSH（OPND,2 ） #+ 1 2 *3-4/2# PUSH（OPTR,*） #+* 1 2 3-4/2# PUSH（OPND,3 ） #+* 1 2 3 -4/2# operate（2,*,3） #+ 1 6 -4/2# operate（1,+,6） # 7 -4/2# PUSH（OPTR,- ） # - 7 4/2# PUSH（OPND,4 ） #- 7 4 /2# PUSH（OPTR,/ ） #-/ 7 4 2# PUSH（OPND,2 ） #-/ 7 4 2 # operate（4,/,2） #- 7 2 # operate（7,-,2） # 5 # return(TOP(OPND),.,舉例2:寫(xiě)出表達(dá)式5+(6-4/2)*3的計(jì)算過(guò)程,最后的結(jié)果T4,置于OPRD的棧頂。,.,第四節(jié)棧的應(yīng)用舉例,表達(dá)式求值算法： cout<<"input an expression (Ending with #)”<<endl; ch=getchar(); strGetTop(,.,第四節(jié)棧的應(yīng)用舉例,else switch(Compare(y,ch) case '': strPop( ,.,一、隊(duì)列,38,第五節(jié)隊(duì)列,隊(duì)列是只允許在表的一端進(jìn)行插入，而在另一端刪除元素的線性表。在隊(duì)列中，允許插入的一端叫隊(duì)尾（rear），允許刪除的一端稱為對(duì)頭(front)。特點(diǎn)：先進(jìn)先出 (FIFO),.,二、順序隊(duì)列,39,第五節(jié)隊(duì)列,順序隊(duì)列：采用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)從隊(duì)列頭到隊(duì)列尾的元素順序隊(duì)列有兩個(gè)指針：隊(duì)頭指針front和隊(duì)尾指針rear,.,三、順序隊(duì)列的進(jìn)隊(duì)和出隊(duì)原則,40,第五節(jié)隊(duì)列,進(jìn)隊(duì)時(shí)，新元素按rear指針位置插入，然后隊(duì)尾指針增一，即 rear = rear + 1出隊(duì)時(shí)，將隊(duì)頭指針位置的元素取出，然后隊(duì)頭指針增一，即 front = front + 1隊(duì)頭指針始終指向隊(duì)列頭元素隊(duì)尾指針始終指向隊(duì)列尾元素的下一個(gè)位置,.,四、順序隊(duì)列的進(jìn)隊(duì)和出隊(duì)舉例,41,第五節(jié)隊(duì)列,front,rear,空隊(duì)列,front,rear,A,B,C,D進(jìn)隊(duì),front,rear,A退隊(duì),front,rear,B退隊(duì),front,rear,E,F,G進(jìn)隊(duì),front,rear,H進(jìn)隊(duì),溢出,.,五、順序隊(duì)列存在的問(wèn)題,42,第五節(jié)隊(duì)列,當(dāng)隊(duì)尾指針指向隊(duì)列存儲(chǔ)結(jié)構(gòu)中的最后單元時(shí)，如果再繼續(xù)插入新的元素，則會(huì)產(chǎn)生溢出當(dāng)隊(duì)列發(fā)生溢出時(shí)，隊(duì)列存儲(chǔ)結(jié)構(gòu)中可能還存在一些空白位置（已被取走數(shù)據(jù)的元素）解決辦法之一：將隊(duì)列存儲(chǔ)結(jié)構(gòu)首尾相接，形成循環(huán)(環(huán)形)隊(duì)列,.,一、循環(huán)隊(duì)列,43,第六節(jié)循環(huán)隊(duì)列,循環(huán)隊(duì)列采用一組地址連續(xù)的存儲(chǔ)單元將整個(gè)隊(duì)列的存儲(chǔ)單元首尾相連,.,二、循環(huán)隊(duì)列空與滿,44,第六節(jié)循環(huán)隊(duì)列,front = rear，循環(huán)隊(duì)列空(rear+1) % MAXQSIZE = front，循環(huán)隊(duì)列滿,隊(duì)列滿,.,三、循環(huán)隊(duì)列定義,45,第六節(jié)循環(huán)隊(duì)列,Class SqQueue private: DataType dataMAXQSIZE; /循環(huán)隊(duì)列數(shù)組 int front; int rear;public: SqQueue(void) /構(gòu)造函數(shù) front = rear=0; SqQueue(void); /析構(gòu)函數(shù),.,第六節(jié)循環(huán)隊(duì)列,void EnQueue (const DataType,.,四、循環(huán)隊(duì)列插入元素,47,第六節(jié)循環(huán)隊(duì)列,void SqQueue:EnQueue(DataType,.,五、循環(huán)隊(duì)列刪除元素,48,第六節(jié)循環(huán)隊(duì)列,SqQueue:DeQueue(DataType,.,一、鏈隊(duì)列,49,第七節(jié)鏈隊(duì)列,鏈隊(duì)列采用鏈表存儲(chǔ)單元鏈隊(duì)列中，有兩個(gè)分別指示隊(duì)頭和隊(duì)尾的指針。鏈?zhǔn)疥?duì)列在進(jìn)隊(duì)時(shí)無(wú)隊(duì)滿問(wèn)題，但有隊(duì)空問(wèn)題。,.,二、鏈隊(duì)列指針變化狀況,50,第七節(jié)鏈隊(duì)列,鏈隊(duì)列是鏈表操作的子集,.,第七節(jié)鏈隊(duì)列,入隊(duì)操作:template void LinQueue:Append(const T /計(jì)數(shù)器加1,.,第七節(jié)鏈隊(duì)列,出隊(duì)操作:template T LinQueue:Delete(void) /出隊(duì)列,隊(duì)頭結(jié)點(diǎn)刪除由函數(shù)返回 if(count = 0) cout *p = front->next; /p指向新的隊(duì)頭結(jié)點(diǎn)T data = front->data;/保存原隊(duì)頭結(jié)點(diǎn)的data域值delete front;/釋放原隊(duì)頭結(jié)點(diǎn)空間front = p;/front指向新的隊(duì)頭結(jié)點(diǎn)count-;/計(jì)數(shù)器減1return data;/返回原隊(duì)頭結(jié)點(diǎn)的data域值,.,隊(duì)列應(yīng)用舉例,實(shí)例: 編寫(xiě)判斷一個(gè)字符序列是否回文的函數(shù). 回文:一個(gè)字符序列以中間字符為基準(zhǔn)且兩邊字符 完全相同。 算法描述:字符數(shù)組中存放要判斷的字符串。 把字符數(shù)組中字符逐個(gè)分別存入一個(gè)隊(duì)列和一個(gè)堆棧 逐個(gè)出隊(duì)列和退棧并比較出隊(duì)列的字符和退棧的字符是否相等，若全部相等則該字符序列是回文，否則就不是回文。,.,隊(duì)列應(yīng)用舉例,const int MaxQueueSize = 10;const int MaxStackSize = 10;typedef char DataType; /構(gòu)造一個(gè)順序循環(huán)隊(duì)列,一個(gè)順序棧void HuiWen(char str) /判斷字符串str是否是回文SeqStack myStack;SeqQueue myQueue;int n = strlen(str); /求字符串長(zhǎng)度f(wàn)or(int i = 0; i < n; i+)myQueue. EnQueue(stri);myStack.Push(stri); while(myQueue.NotEmpty() ,.,隊(duì)列應(yīng)用舉例,void main(void)char str1 = "ABCDEDCBA"char str2 = "ABCDEDBAC"cout << "字符串ABCDEDCBA"HuiWen(str1);cout << "字符串ABCDEDBAC"HuiWen(str2);,.,隊(duì)列應(yīng)用舉例,下標(biāo) I j pre0 1 1 -11 1 2 02 2 1 03 2 2 14 3 1 25 3 2 36 4 1 47 3 3 58 5 1 69 3 4 710 5 2 811 6 1 812 2 4 913 5 3 1014 7 1 1115 1 4 1216 2 5 1217 6 3 1318 1 5 1519 2 6 1620 6 4 17,0 1 2 3 4 5 6 7 8 9,0 1 2 3 4 5 6 7 8 9,.,隊(duì)列應(yīng)用舉例,下標(biāo) I j pre 1 6 18 6 5 20 5 5 22 7 5 22 4 5 23 5 6 23 8 5 24 4 6 25 5 7 26 8 6 27 4 7 28 5 8 29 6 7 29 8 7 30 3 7 31 4 8 31 6 8 32 8 8 34,迷宮求解結(jié)果：迷宮路徑： (1,1) (2,1) (3,1) (4,1) (5,1) (5,2) (5,3) (6,3) (6,4) (6,5) (7,5) (8,5) (8,6) (8,7) (8,8),.,練 習(xí),1.若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少?一個(gè)棧的入棧序列是abcde，則可能的出棧序列為: A.edcab B.decba C.debcaD.cabde,.,練 習(xí),3. 假定用一維數(shù)組a7順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列，隊(duì)首和隊(duì)尾指針?lè)謩e用front和rear表示，當(dāng)前隊(duì)列中已有5個(gè)元素：23，45，67，80，34，其中23為隊(duì)首元素，front的值為3，請(qǐng)畫(huà)出對(duì)應(yīng)的存儲(chǔ)狀態(tài)，當(dāng)連續(xù)做4次出隊(duì)運(yùn)算后，再讓15，36，48元素依次進(jìn)隊(duì)，再次畫(huà)出對(duì)應(yīng)的存儲(chǔ)狀態(tài)。4. 表達(dá)式a*(b+c)-d的后綴表達(dá)式是 ？,.,練 習(xí),5. 設(shè)有一順序棧S,元素s1,s2,s3,s4,s5,s6依次進(jìn)棧,如果6個(gè)元素出棧的順序是s2，s3，s4，s6，s5，s1,則棧的容量至少應(yīng)該是（）。 A.2 B.3 C.4 D.5 6. 設(shè)已將元素a1，a2，a3依次入棧，元素a4正等待進(jìn)棧。那么下列4個(gè)序列中不可能出現(xiàn)的出棧序列是（）。 Aa3 a1 a4 a2 Ba3 a2 a4 a1 C a3 a4 a2 a1 Da4 a3 a2 a1,.,練 習(xí),7. 向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，其操作步驟為（）。Atop->next=s. Bs->next=top->next;top->next=s.Ctop->next=s;top=s. Ds->next=top; top=top->next.8. 從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn),并將被刪結(jié)點(diǎn)的值保存到x中,其操作步驟為（）。Ax=top->data; top=top->next; Btop=top->next; x=top->data;Cx=top; top=top->next; Dx=top->data.,.,練 習(xí),9. 鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是（）。A通常不會(huì)出現(xiàn)棧滿的情況 B通常不會(huì)出現(xiàn)?？盏那闆rC插入操作更加方便 D刪除操作更加方便 10. 設(shè)數(shù)組Am作為循環(huán)隊(duì)列sq的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行入隊(duì)操作操作修改指針的是（）Asq.front=(sq.front+1)%m Bsq.front=(sq.front+1)%(m+1)Csq.rear=(sq.rear+1)%m Dsq.rear=(sq.rear+1)%(m+1) 11、在一個(gè)鏈隊(duì)列中，若f，r分別為隊(duì)首、隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為（）。Af->next=c;f=s; Br->next=s;r=s;Cs->next=r;r= s Ds->next=f;f=s;,.,隊(duì)列應(yīng)用舉例,課堂練習(xí):報(bào)數(shù)問(wèn)題有10個(gè)人站一排隊(duì),從左向右編號(hào):1-10號(hào)現(xiàn)從左向右報(bào)數(shù)”1,2,1,2,1,2,1,2,1,2”,要求報(bào)數(shù)1的人出列,報(bào)數(shù)2的人立即站到隊(duì)尾,直到所有的人都出列,給出人們的出列順序算法.,