深圳大學(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語言中動(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 | ai∈ElemSet, i=1,2,3,…,n} 數(shù)據(jù)關(guān)系：R = { | ai-1,ai∈D} 基本操作： 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;//前視定義,否則友元無法定義 template //模板類型為T class 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 LinStack { private: 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的初值為0 } template 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ù)減1 return 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)算過程如下： N N /8 N mod 8 1348 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)用過程的數(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è)堆棧來進(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(str[i]=='('||str[i]=='['||str[i]=='{') //出現(xiàn)三種左括號(hào)之一壓棧；否則進(jìn)行匹配判斷 stk.push(str[i]); else if(str[i]==')'||str[i]==']'||str[i]=='}') { //遇到右括號(hào),判斷棧頂元素是否為左括號(hào)，如不為匹配的左括號(hào)，括號(hào)不匹配；否則出棧 if(str[i]==')' // 左括號(hào)多于右括號(hào) },.,四、迷宮求解,24,第四節(jié)　棧的應(yīng)用舉例,迷宮求解一般采用“窮舉法” 逐一沿順時(shí)針方向查找相鄰塊（一共四塊－東(右)、南(下)，西(左)、北(上)）是否可通，即該相鄰塊既是通道塊，且不在當(dāng)前路徑上 用一個(gè)棧來記錄已走過的路徑,.,四、迷宮求解,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 mg[m+1][n+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á)式開始及結(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è)過程,.,第四節(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]:寫出表達(dá)式5+(6-4/2)*3的計(jì)算過程,最后的結(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ì)列存在的問題,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 data[MAXQSIZE]; //循環(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í)無隊(duì)滿問題，但有隊(duì)空問題。,.,二、鏈隊(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ù)器減1 return data; //返回原隊(duì)頭結(jié)點(diǎn)的data域值 },.,隊(duì)列應(yīng)用舉例,實(shí)例: 編寫判斷一個(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)度 for(int i = 0; i < n; i++) { myQueue. EnQueue(str[i]); myStack.Push(str[i]); } 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 pre 0 1 1 -1 1 1 2 0 2 2 1 0 3 2 2 1 4 3 1 2 5 3 2 3 6 4 1 4 7 3 3 5 8 5 1 6 9 3 4 7 10 5 2 8 11 6 1 8 12 2 4 9 13 5 3 10 14 7 1 11 15 1 4 12 16 2 5 12 17 6 3 13 18 1 5 15 19 2 6 16 20 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ù)組來實(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.debca D.cabde,.,練 習(xí),3. 假定用一維數(shù)組a[7]順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列，隊(duì)首和隊(duì)尾指針分別用front和rear表示，當(dāng)前隊(duì)列中已有5個(gè)元素：23，45，67，80，34，其中23為隊(duì)首元素，front的值為3，請(qǐng)畫出對(duì)應(yīng)的存儲(chǔ)狀態(tài)，當(dāng)連續(xù)做4次出隊(duì)運(yùn)算后，再讓15，36，48元素依次進(jìn)隊(duì)，再次畫出對(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)的出棧序列是（）。 A．a(chǎn)3 a1 a4 a2 B．a(chǎn)3 a2 a4 a1 C． a3 a4 a2 a1 D．a(chǎn)4 a3 a2 a1,.,練 習(xí),7. 向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，其操作步驟為（）。 A．top->next=s. B．s->next=top->next;top->next=s. C．top->next=s;top=s. D．s->next=top; top=top->next. 8. 從棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn),并將被刪結(jié)點(diǎn)的值保存到x中,其操作步驟為（）。 A．x=top->data; top=top->next; B．top=top->next; x=top->data; C．x=top; top=top->next; D．x=top->data.,.,練 習(xí),9. 鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是（）。 A．通常不會(huì)出現(xiàn)棧滿的情況 B．通常不會(huì)出現(xiàn)棧空的情況 C．插入操作更加方便 D．刪除操作更加方便   10. 設(shè)數(shù)組A[m]作為循環(huán)隊(duì)列sq的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行入隊(duì)操作操作修改指針的是（） A．sq.front=(sq.front+1)%m B．sq.front=(sq.front+1)%(m+1) C．sq.rear=(sq.rear+1)%m D．sq.rear=(sq.rear+1)%(m+1)   11、在一個(gè)鏈隊(duì)列中，若f，r分別為隊(duì)首、隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為（）。 A．f->next=c;f=s; B．r->next=s;r=s; C．s->next=r;r= s D．s->next=f;f=s;,.,隊(duì)列應(yīng)用舉例,[課堂練習(xí)]:報(bào)數(shù)問題 有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ì) 尾,直到所有的人都出列,給出人們的出列順 序算法.,