棧(Stack)

棧的基本概念

?？梢钥醋魇遣僮魇芟薜木€性表，限制在表的一端進行插入和刪除操作的線性表。成為先進先出(LIFO)，先進后出(FILO)線性表。

棧頂(Top):允許插入刪除操作的一段，稱為表尾。

棧底(Bottom):固定端，稱為表頭。

進棧(push):又稱為壓棧。

出棧(pop):又稱為彈棧。

棧的修改是按先進后出原則進行的

順序棧

由數組是否可以擴充可分為靜態(tài)順序棧，動態(tài)順序棧。

靜態(tài)順序棧:實現簡單，但不能做擴充

動態(tài)順序棧:實現較復雜，可以擴充

結點進棧:將數據元素存到top指針所指的位置，top移向棧的下一存儲位置，即top+1

結點出棧: 先將top指向上一存儲位置，即top-1，再將top指向的當前結點的數據元素取出，

初始化棧:top = bottom = -1 / 0 / n / n - 1

0 / n - 1 的設置方式 top 始終指向下一個值為空的結點，且要先賦值再top++ / --，而 -1 / n 的設置方式要先top++ / --再賦值

動態(tài)棧:

靜態(tài)棧:

對頂棧:

• 兩個棧共享一片空間

• 把兩個棧的棧底設置在數組的兩端

• |top1 - top2| == 1 表示棧滿

鏈棧

棧的鏈式存儲結構，是運算受限的單鏈表，其插入和刪除操作只能在表頭位置上進行，頭出頭插的單鏈表結構

棧的應用

1.檢查一個字符串或者一個表達式中的括號是否相匹配，例如:[4 + (2 + 8) * [ 5 / (9 - 7)] * 3

算法思想:

• 設置一個棧

• 當讀到左括號時，左括號進棧。

• 當讀到右括號時，則從棧中彈出一個元素，與讀到的右括號進行匹配，若匹配成功，繼續(xù)讀入；

• 否則匹配失敗，返回false。

上代碼??

2.中綴表達式:b - (a + 5) * 3 轉后綴表達式: b a5+ 3 * -

①初始化一個數字棧（s1）和符號棧（s2），從左到右掃描表達式，若遇到數字直接鋪設到數字棧

②遇到符號，設符號為 ch

Ⅰ.若符號棧為空，則s2.push(ch)

Ⅱ.若ch為左括號，則s2.push(ch)

Ⅲ.若s2的棧頂為左括號 則s2.push(ch)

Ⅳ.若ch優(yōu)先級大于s2棧頂元素的優(yōu)先級，則s2.push(ch)，否則將從s2中彈出棧頂元素，壓到s1中（若要計算結果的，則從s1中彈出兩個數完成運算，然后將運算結果壓回s1中，回到Ⅱ 繼續(xù)執(zhí)行）