不朽情缘五滴血图片

1-4 棧

棧也是一種數據呈線性排列的數據結構，不過在這種結構中，我們只能訪問最新添加的數據。棧就像是一摞書，拿到新書時我們會把它放在書堆的最上面，取書時也只能從最上面的新書開始取。

這就是棧的概念圖?，F在存儲在棧中的只有數據Blue。

然后，棧中添加了數據Green。

接下來，數據Red入棧。

從棧中取出數據時，是從最上面，也就是最新的數據開始取出的。這里取出的是Red。

如果再進行一次出棧操作，取出的就是Green了。

解說

像棧這種最后添加的數據最先被取出，即“后進先出”的結構，我們稱為Last In First Out，簡稱LIFO。

與鏈表和數組一樣，棧的數據也是線性排列，但在棧中，添加和刪除數據的操作只能在一端進行，訪問數據也只能訪問到頂端的數據。想要訪問中間的數據時，就必須通過出棧操作將目標數據移到棧頂才行。

應用示例

棧只能在一端操作這一點看起來似乎十分不便，但在只需要訪問最新數據時，使用它就比較方便了。

比如，規定（AB（C（DE）F）（G（（H）I J）K））這一串字符中括號的處理方式如下：首先從左邊開始讀取字符，讀到左括號就將其入棧，讀到右括號就將棧頂的左括號出棧。此時，出棧的左括號便與當前讀取的右括號相匹配。通過這種處理方式，我們就能得知配對括號的具體位置。

另外，我們將要在4-3節中學習的深度優先搜索算法，通常會選擇最新的數據作為候補頂點。在候補頂點的管理上就可以使用棧。

參考：4-3 深度優先搜索