女性內(nèi)衣內(nèi)褲選擇技巧

棧與隊列西安交通大學(xué)計教中心棧的定義

棧是限制在表的一端進行插入和刪除操作的線性表。允許進行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。 如果多個元素依次進棧，則后進棧的元素必然先出棧，所以堆棧又稱為后進先出（LIFO）表。堆棧設(shè)有一個棧頂指針標志棧頂位置。

棧示意圖a1a3a2進棧出棧top堆棧的主要操作有：?創(chuàng)建空棧。?進棧(push)操作:在棧頂插入元素。?出棧(pop)操作:在棧頂刪除元素。?讀棧頂元素:只是讀出棧頂元素，并不改變棧內(nèi)元素。

順序棧#defineSTACKSIZE100 //堆棧最大可分配空間數(shù)量classSqStack{public: ElemTypedata[STACKSIZE]; //存儲元素的數(shù)組 inttop; //棧頂指針，存儲棧頂元素的下標 SqStack(){top=-1;} //構(gòu)造函數(shù) voidPush(ElemTypex); //入棧操作 voidPop(ElemType&result); //出棧操作voidGetTop(ElemType&result); //取棧頂元素};

一般將數(shù)組的0下標單元作為棧底，將棧頂元素的下標存儲在棧頂指針top中，它隨著元素進棧出棧而變化。top為-1表示空棧，top等于stacksize-1則表示棧滿。（1）進棧操作若棧不滿，則在棧頂插入元素x作為新的棧頂。voidSqStack::Push(ElemTypex){ if(top<stacksize-1) { top++; data[top]=x; } elsecout<<”棧滿”;}（2）出棧操作若棧不空，則刪除棧頂元素，用result返回其值。voidSqStack::Pop(ElemType&result){ if(top>-1){ result=data[top]; top--; }elsecout<<"?？?;}（3）取棧頂元素若棧不空，則用result返回棧頂元素。voidSqStack::GetTop(ElemType&result){ if(top>-1){ result=data[top]; } elsecout<<"?？?;}鏈式棧

棧的鏈式存儲結(jié)構(gòu)實質(zhì)上就是一個無頭結(jié)點、只能在頭部插入、刪除元素的單鏈表。typedefstructnode{ ElemTypedata; //數(shù)據(jù)域 structnode*next; //指針域}SNode; classLinkStack{ public: SNode*top; //棧頂指針 LinkStack(){top=NULL;} //構(gòu)造函數(shù) voidPush(ElemTypex); //入棧操作 voidPop(ElemType&result); //出棧操作};

（1）進棧操作若棧不滿，則在棧頂插入元素x作為新的棧頂。voidLinkStack::Push(ElemTypex){ SNode*p=newSNode; if(p!=NULL){ p->data=x; p->next=top; top=p; }}（2）出棧操作若棧不空，則刪除棧頂元素，用result返回其值。voidLinkStack::Pop(ElemType&result);{ SNode*p; if(top!=NULL){ result=top->data; p=top; top=top->next; deletep; }}舉例:后后綴表達達式求值假定表達式式是由加減減乘除和數(shù)數(shù)字構(gòu)成。。最簡單的的表達式為為下列形式式：(操作數(shù)S1)(運算符符OP)(操作數(shù)數(shù)S2)三種不同的的表示方法法：前綴表示法法OPS1S2例如6+3寫寫成+63中綴表示法OPS1S2例如6+3寫寫成63+后綴表示法S1S2OP例如6+3寫寫成63+同時，任何表表達式都可分分解為下列形形式：(子表達式E1)(運算符OP)(子表達式式E2)它的后綴表示示法應(yīng)寫成：：(E1的后綴表示)(E2的后綴表示)OP只要不斷對子子表達式進一一步分解，總總能將子表達達式分解為最最簡單形式，，因此任何四四則運算表達達式都可寫成成前綴式或后后綴式。例如：2*(6+3)2(6+3)*263+*。(注意：轉(zhuǎn)化化為后綴式后后括號去掉)中綴式雖然容容易理解，但但在求值的時時候利用前綴綴式或后綴式式更為簡單。。用后綴式求求值的算法為為：首先設(shè)立一個個堆棧，依此此讀取后綴式式中的字符，，若字符是數(shù)數(shù)字，則進棧棧并繼續(xù)讀取取，若字符是是運算符（記記為OP），則連續(xù)出出棧兩次得到到數(shù)字S1和S2，計算表達式式S1OPS2并將結(jié)果入棧棧，繼續(xù)讀取取后綴式。當當讀到結(jié)束符符時停止讀操操作，這時堆堆棧中只應(yīng)該該有一個數(shù)據(jù)據(jù)，即結(jié)果數(shù)數(shù)據(jù)。例如后綴式263+*的的計算過程為為2、6、3依次入棧，，讀+號則令令3和6依次次出棧，計算算6+3后將將結(jié)果9入棧棧，讀*號則則令9和2依依次出棧，計計算2*9后后將結(jié)果18入棧。這時時18就是最最終結(jié)果?！纠?-3】假定表達式是是由不超過四個實數(shù)進行行四則運算構(gòu)成的算算式，要編寫一個程序來求解該該算式的結(jié)果果。中綴表達式變變成等價的后后綴表達式將中綴表達式式變成等價的的后綴表達式式，表達式中中操作數(shù)次序序不變，運算算符次序發(fā)生生變化，同時時去掉了圓括括號。轉(zhuǎn)換規(guī)規(guī)則是：設(shè)立一個棧，，存放運算符符，首先棧為為空，編譯程程序從左到右右掃描中綴表表達式，若遇遇到操作數(shù)，，直接輸出，，并輸出一個個空格作為兩兩個操作數(shù)的的分隔符；若若遇到運算符符，則必須與與棧頂比較，，運算符級別別比棧頂級別別高則進棧，，否則退出棧棧頂元素并輸輸出，然后輸輸出一個空格格作分隔符；；若遇到左括括號，進棧；；若遇到右括括號，則一直直退棧輸出，，直到退到左左括號止。當當棧變成空時時，輸出的結(jié)結(jié)果即為后綴綴表達式。步驟棧中元素

輸出結(jié)果

說明1(

（進棧2(1輸出13(+1+進棧4(+12輸出25

12++退棧輸出，退棧到（止6*12+*進棧7*(12+（進棧8*((12+（進棧9*((12+8輸出810*((-12+8

-進棧將中綴表達式式(1+2)*((8-2)/(7-4))變變成等價的后后綴表達式。。

現(xiàn)在用棧棧來實現(xiàn)該運運算，棧的變變化及輸出結(jié)結(jié)果如下：11*((-12+82輸出212*(12+82--退棧輸出，退棧到（止13*(/12+82-/進棧14*(/(12+82-（進棧15*(/(12+82-7輸出716*(/(-12+82-7-進棧17*(/(-12+82-74輸出418*(/12+82-74--退棧輸出，退棧到（止19*12+82-74-//退棧輸出，退棧到（止20

12+82-74-/*

*退棧并輸出隊列定義隊列是只能在在表的一端進進行插入、在在另一端進行行刪除操作的的線性表。允允許刪除元素素的一端稱為為隊頭，允許許插入元素的的一端稱為隊隊尾。顯然不論元素素按何種順序序進入隊列，，也必然按這這種順序出隊隊列，所以隊隊列又稱為先先進先出（FIFO）表表。隊列有兩兩個活動端，，所以設(shè)置了了對頭和隊尾尾兩個位置指指針。一般隊隊頭指針記作作front，隊尾指針針記作rear。abcfrontrear入隊出隊隊列示意圖循環(huán)隊列—隊隊列順序存儲儲順序存儲的隊隊列中，每次次出隊列的元元素必定是隊隊頭元素，因因此如果采取取與普通順序序表同樣的操操作方式，則則每次出隊操操作必然將整整個隊列向前前移動，這使使得效率大大大降低。因此在順序存儲的的隊列中，出出隊和入隊操操作都不移動動元素而是移移動指針。為方便起見，，這里規(guī)定隊隊頭指針front指向隊頭元素素的前一個位位置，隊尾指指針rear指向隊尾元素素所在位置。。這樣，入隊隊和出隊操作作的執(zhí)行步驟驟都是首先執(zhí)執(zhí)行指針移動，再再進行元素讀讀寫。對空隊列而言言，可假定front和和rear的的值為-1假溢出ABCfrontrearfrontrear(a)

A?B?C入隊

(b)

A?B出隊,D?E入隊

(c)隊列假溢出隊列假溢出示意圖CDEfrontrear隨著元素不斷斷入隊列、出出隊列，rear和front指針針會不斷向后后移動（如圖圖(b)所示示），最終會會指向數(shù)組的的最大下標位位置（如圖(c)所示））。由于rear和front指針針只能單方向向移動，這時時元素無法入入隊列，但是是隊列中仍有有大量空閑位位置。這種情情況稱為假溢溢出。循環(huán)隊列解決隊列假溢溢出的辦法是是將存放隊列列元素的數(shù)組組首尾相接，，形成循環(huán)隊隊列。循環(huán)隊列的基基本操作方式式為：入隊列時先執(zhí)執(zhí)行rear=(rear+1)%M，再將新新元素在rear指示位位置加入；出隊列時先執(zhí)執(zhí)行front=(front+1)%M，再再將下標為front的的元素取出。。為了將隊空和和對滿的條件件加以區(qū)分，，一般不使用用front指針所指的的位置。隊空條件為front=rear隊滿條件為(rear+1)%M=front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE(a)循環(huán)隊隊列空(b)非空循循環(huán)隊列(c)循環(huán)環(huán)隊列滿循環(huán)隊列示意意圖循環(huán)隊列描述述如下：#defineMAXSIZE100//隊列最大大可分配空間間數(shù)量classSqQueue{public:ElemTypedata[MAXSIZE]; //存放元素素的數(shù)組intfront;//隊隊頭頭指指針針intrear;//隊隊尾尾指指針針voidEnQueue(ElemTypex);//入入隊隊操操作作voidDeQueue(ElemType&e);//出出隊隊操操作作voidGetHead(ElemType&e);//取取隊隊頭頭元元素素};front和和rear指指針針取取值值均均為為所所指指數(shù)數(shù)組組單單元元的的下下標標。。由于于隊隊頭頭指指針針所所指指單單元元總總是是空空的的，，length比比實實際際能能存存儲儲的的元元素素多多一一。。（1））入入隊隊操操作作若隊隊列列不不滿滿，，則則在在隊隊尾尾插插入入元元素素x作為為新新的的隊隊尾尾。。voidSqQueue::EnQueue(ElemTypex){if((rear+1)%MAXSIZE==front)cout<<"隊隊列列已已滿滿";else{rear=(rear+1)%MAXSIZE;data[rear]=x;}}常用算算法（2））出隊隊操作作若隊列列不空空，則則刪除除隊頭頭元素素并用用e取回該該元素素的值值。voidSqQueue::DeQueue(ElemType&e){if(rear==front)cout<<"隊隊列已已空";else{front=(front+1)%MAXSIZE;e=data[front];}}（3））取隊隊頭元元素若隊列不空空，則用e取回隊頭元元素的值。。voidSqQueue::GetHead(ElemType&e){if(rear==front)cout<<"隊隊列已空";else{inti=(front+1)%MAXSIZE;e=data[i];}}鏈隊列—隊隊列鏈式存存儲鏈隊列實質(zhì)質(zhì)上就是只只能在頭部部刪除元素素、只能在在尾部插入入元素的單單鏈表。隊頭指針front就是單鏈鏈表的頭指指針，隊尾尾指針rear則是是指向單鏈鏈表最后一一個結(jié)點的的指針。Qa1an∧frontrear非空鏈隊列

鏈隊列的結(jié)結(jié)點可定義義如下：structQNode{ElemTypedata;structQNode*next;};鏈隊列有兩兩個指針，，因此可采采用下面定定義:classLinkQueue{public:QNode*front;//隊隊頭指針針QNode*rear;//隊隊尾指針針(下頁頁繼續(xù)………)(接接上頁)LinkQueue(){front=newQNode;//建建立頭結(jié)結(jié)點front->next=NULL;rear=front;//尾指指針也指指向頭結(jié)結(jié)點}intLength();//求隊隊列長度度voidEnQueue(ElemTypex);//入隊操操作voidDeQueue(ElemType&e);//出隊隊操作voidGetHead(ElemType&e);//求隊隊頭元素素};（1）求求隊列的的長度返回隊列列的元素素個數(shù)，，即隊列列的長度度。intLinkQueue::Length(){QNode*p=front;intlen=0;while(p!=rear){len++;p=p->next;}returnlen;}（2）入隊列列操作插入元素x為為隊列新的隊隊尾元素。voidLinkQueue::EnQueue(ElemTypex){QNode*s=newQNode;//建立新結(jié)結(jié)點ss->data=x;s->next=NULL;rear->next=s;//在隊隊尾插插入結(jié)結(jié)點srear=s;//修修改隊隊尾指指針}（3））出隊隊列操操作若隊列列不空空，則則刪除除隊頭頭元素素，用用e返返回其其值。。voidLinkQueue::DeQueue(ElemType&e){QNode*p;if(front==rear)cout<<"隊列列已空空";else{