stack

中文名

栈（中国），堆疊（台灣）

爲了表達對台灣譯名的喜歡，本文用正體中文書寫。堆疊這個詞十分形象地描述了這個數據結構。試想想，疊盤子的活：有一疊盤子，要添加時，只能往頂上添加，不能從中間或底部插入，要取出盤子時，也只能從頂部依次取，不能從中間或底部抽走。這麼一個形象的說法大體上也就描述了這個數據結構了。

定義

堆疊是這樣一個數據項的集合：只能移除最近加入的數據項。換句話說，要移除較早加入的數據項，就必須把比它晚加入的數據項都移除才行。最後加入的數據項的位置一般稱為頂部（top）。它的最基本的操作是 push 和 pop，通常也還有兩個操作：top 和 isEmpty. 堆疊的特性一般描述為 LIFO(Last-In, First-Out)。

操作定義

操作 new(), push(v, S), top(S), popoff(S) 可以定義如下

  1. new() returns a stack
  2. popoff(push(v, S)) = S
  3. top(push(v, S)) = v

注：S 是一个堆疊，v 是值。pop 操作包含了 top（返回 top 的值）和 popoff （刪除 top 的值）。

對 isEmpty(S) 可定義如下

  1. isEmpty(new()) = true
  2. isEmpty(push(v, S)) = false

經典應用

河內塔(Hanoi Tower)是堆疊的一個經典應用，詳細內容參這裡。

參考