程式設計概念：棧

棧是一種ADT，它可能涉及動態或靜態實現。棧是後進先出 (LIFO) 或先進後出 (FILO) ADT。實現應包括兩個操作，入棧和出棧，以及指向棧頂的指標。

現實生活中的例子是您可能放在桌子上的書堆

在這個例子中，我們不斷地將（入棧）書籍新增到書堆中。如果我們要拿到最底部的關於汽車的書，我們必須首先移除（出棧）上面的所有書。因此，先進後出 (FILO)

讓我們看看棧的計算機實現

• 入棧：將一個新的指定項新增到棧頂
• 出棧：從棧頂移除項。

狀態 1	狀態 2	狀態 3	狀態 4	狀態 5
入棧 '大象'	入棧 '河馬'	入棧 '斑馬'	出棧	入棧 '火烈鳥'
記憶體位置 資料 棧頂 4 3 2 1 大象 <--	記憶體位置 資料 棧頂 4 3 2 河馬 <-- 1 大象	記憶體位置 資料 棧頂 4 3 斑馬 <-- 2 河馬 1 大象	記憶體位置 資料 棧頂 4 3 斑馬 2 河馬 <-- 1 大象 請注意資料並沒有被“刪除” 棧頂指標移動 以表明它不再位於 棧中	記憶體位置 資料 棧頂 4 3 火烈鳥 <-- 2 河馬 1 大象

棧有幾種用途

• 反轉佇列（如上面用字母排序的名稱所示）
• 執行逆波蘭計算（參見……）
• 儲存遞迴函式呼叫的返回地址和系統狀態

練習：棧 在執行以下每個命令後繪製棧，從空棧開始。棧實現了什麼 入棧 '安娜貝爾' 入棧 '克里斯' 入棧 '海明威' 入棧 '詹姆斯' 出棧 出棧 出棧 出棧 答案 命令 1 命令 2 命令 3 命令 4 記憶體位置 資料 棧頂 4 3 2 1 安娜貝爾 <-- 記憶體位置 資料 棧頂 4 3 2 克里斯 <-- 1 安娜貝爾 記憶體位置 資料 棧頂 4 3 海明威 <-- 2 克里斯 1 安娜貝爾 記憶體位置 資料 棧頂 4 詹姆斯 <-- 3 海明威 2 克里斯 1 安娜貝爾 命令 5 命令 6 命令 7 命令 8 記憶體位置 資料 棧頂 4 詹姆斯 3 海明威 <-- 2 克里斯 1 安娜貝爾 Output: James 記憶體位置 資料 棧頂 4 詹姆斯 3 海明威 2 克里斯 <-- 1 安娜貝爾 Output: Hemingway 記憶體位置 資料 棧頂 4 詹姆斯 3 海明威 2 克里斯 1 安娜貝爾 <-- Output: Chris 記憶體位置 資料 棧頂 4 詹姆斯 3 海明威 2 克里斯 1 安娜貝爾 Output: Annabelle 棧頂 = 0 棧為空 這組指令使用棧按順序輸入資料，然後以反序輸出資料 給出從狀態 1 到狀態 2 所需的指令集，如下所示 狀態 1 狀態 2 記憶體位置 資料 棧頂 4 3 鯊魚 <-- 2 粉筆 1 乳酪 記憶體位置 資料 棧頂 4 3 女巫 <-- 2 沙子 1 乳酪 答案 出棧 出棧 入棧 '沙子' 入棧 '女巫' 如果我們有一個空棧，我們將棧頂指標設定為多少？ 答案 0 或 null 描述棧資料型別 答案 棧是一種先進後出或後進先出的資料型別 給出棧在計算機中使用的兩種情況 答案 反轉佇列（如上面用字母排序的名稱所示） 執行逆波蘭計算（參見……） 儲存遞迴函式呼叫的返回地址

Dim myStack(10) as string
Dim ToS as integer = 0 'this is our pointer
Dim item as string

While item <> “#”
  Console.writeline(“please insert item ” & ToS & “ into the stack: ”)
  item = Console.readline()
  myStack(ToS) = item
  ToS = ToS + 1
End While

For x = ToS to 0 step -1
  Console.writeline(“Stack item: ” & x & “ = ”  & myStack(x) )
Next

console.readline()