第二十六講棧和隊列

1、數(shù)據(jù)結(jié)構和算法作者：小甲魚讓編程改變世界Change the world by program棧的鏈式存儲結(jié)構講完了棧的順序存儲結(jié)構，也給大家結(jié)合了一些例題演練，相信大家對棧再也不陌生了吧？現(xiàn)在我們來看下棧的鏈式存儲結(jié)構，簡稱棧鏈。（通常我們用的都是棧的順序存儲結(jié)構存儲，鏈式存儲我們作為一個知識點，大家知道就好?。Ｒ驗橹皇菞ｍ攣碜霾迦牒蛣h除操作，所以比較好的方法就是將棧頂放在單鏈表的頭部，棧頂指針和單鏈表的頭指針合二為一。No pic you say a J8棧的鏈式存儲結(jié)構棧的鏈式存儲結(jié)構teypedef struct StackNodeElemType data;/ 存放棧的數(shù)據(jù)stru

2、ct StackNode *next; StackNode, *LinkStackPtr;teypedef struct LinkStackLinkStackPrt top;/ top指針int count;/ 棧元素計數(shù)器進棧操作對于棧鏈的Push操作，假設元素值為e的新結(jié)點是s，top為棧頂指針，我們得到如下代碼：Status Push(LinkStack *s, ElemType e)LinkStackPtr p = (LinkStackPtr) malloc (sizeof(StackNode);p-data = e;p-next = s-top;s-top = p;s-count+;

3、return OK;出棧操作至于鏈棧的出戰(zhàn)Pop操作，假設變量p用來存儲要刪除的棧頂結(jié)點，將棧頂指針下移一位，最后釋放p即可。Status Pop(LinkStack *s, ElemType *e)LinkStackPtr p;if( StackEmpty(*s) ) / 判斷是否為空棧return ERROR;*e = s-top-data;p = s-top;s-top = s-top-next;free(p);s-count-;return OK;終極實踐在講解這道例題的時候，請允許小甲魚花一點點的時間對小學時候的數(shù)學老師進行感謝，嗯，謝謝您，讓我學會如何計算以下這道表達式，并且認為它

4、十分簡單：(1-2)*(4+5)人類早就熟悉這種中綴表達式的計算方式，隨便拉一個小朋友過來，給他一顆糖，他會馬上告訴你這個結(jié)果應該是等于-9，因為括號里邊的要先進行計算。但是計算機不喜歡了，因為我們有小括號中括號大括號，還允許一個嵌套一個，這樣子計算機就要進行很多次if判斷才行決定哪里先計算。逆波蘭表達式后來，在20世紀三十年代，波蘭邏輯學家Jan.Lukasiewicz不知道是像牛頓一樣被蘋果砸到腦袋而想到萬有引力原理，或者還是像阿基米德泡在浴缸里突發(fā)奇想給皇冠是否純金做驗證，總之他也是靈感閃現(xiàn)了，然后發(fā)明了一種不需要括號的后綴表達式，我們通常把它稱為逆波蘭表達式(RPN) 。很多魚油好奇為

5、什么他發(fā)明的東西是以他的國籍而不是以他的名字命名的呢？這也告訴我們，想要流芳百世，名字還得起得朗朗上口才行。逆波蘭表達式我們先來看看，對于(1-2)*(4+5)，如果用逆波蘭表示法，應該是這樣：1 2 4 5 + * 這種方式敢情我們?nèi)祟愂遣淮蠛媒邮艿牧耍贿^對于計算機來說，那可是喜愛至極。因為只需要利用棧的特點，就可以將這種后綴表達式的性能發(fā)揮到極致。解析來就讓小甲魚圖文并茂的解釋一下吧！No pic you say a J8逆波蘭表達式數(shù)字1和2進棧，遇到減號運算符則彈出兩個元素進行運算并把結(jié)果入棧。21basetop-1basetop逆波蘭表達式4和5入棧，遇到加號運算符，4和5彈出棧，相加后將結(jié)果9入棧。54-1basetop