一、堆棧

1.棧堆：具有一定操作約束的線性表；（只在一端做插入刪除）

2.棧的順序存儲結構：

由一個一維數組和一個記錄棧頂元素位置的變量組成。定義方式如下：

3.入棧操作：

注意：（1）top表示棧頂元素的下標，maxsize表示數組容量；

（2）要放入棧頂的上面，同時top加1；

4.出棧操作：

注意：（1）棧堆初始化時top為-1，即數組首元素之前的那個位置的下標；

5.一個數組實現兩個堆棧：

堆棧初始化：

注意：top2代表數組最后一個元素之后位置的下標；

對兩個堆棧的區別方法：引入標識tag：

出棧操作：（記得先檢驗是否為空）

6.堆棧的鏈式存儲：

棧的鏈式存儲結構實際上就是一個單鏈表，叫做鏈棧。插入和刪除操作只能在鏈棧的棧頂進行。

（1）創建堆棧結構：

（2）創建堆棧：

（3）判斷是否為空：

（4）入棧操作：

注意：最后才對s->next做處理；

（5）出棧操作：

注意：第一個賦值語句，是讓firstcell指向s->next指向的位置，所以firstcell指向的是要刪除的結點；

7.中綴轉換為后綴：

8.堆棧的應用：

主要應用的是堆棧的特性：先來先用，后來后用；

二、隊列

1.隊列的順序存儲實現：

隊列的順序存儲結構通常由一個一維數組和一個記錄隊列頭元素的變量front以及一個記錄隊列尾元素位置的變量rear組成；

類比排隊，隊列元素的添加在尾，元素的刪除在頭；

隊列結構創建：

具體位置表示：

2.順環隊列：

這樣的位置排列會出現一個問題：

即無法知道隊列是空的還是滿的，相應的判斷條件都是front=rear

解決辦法：

（1）增加標記size，當增加元素時size+1，用來標識元素個數；

（2）僅僅使用n-1個數組空間，即少使用一個數組空間；

我們一般采用方法（2）；

相應入隊操作：

注意：其中的(ptrq->rear+1) % maxsize代表的是在順環中，rear元素對應的下一個元素的位置下標；

出隊操作：

記住：我們都是在頭刪除元素，在尾添加元素；

3.隊列的鏈式存儲結構：

結構創建：

注意：要額外創建一個結構體，一個存頭部指針，一個存尾部指針；

結構圖解：

出列操作：

這是一個不帶頭結點的隊列，實際上，front指向的頭結點一般為輔助結點（不是空節點），它不存儲實際數據，只是為了方便后續插入、刪除操作；