IT Notes‎ > ‎Data Structure‎ > ‎

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)是堆疊的一個經典應用,詳細內容參這裡

參考

Comments