VB.NET 堆疊 (Stack) 筆記 (基礎篇)
堆疊的本質
堆疊就像是一個整齊疊放的盤子，最後放上去的盤子總是最先被取走，而最早放入的盤子則會被壓在最底下。這種先進後出 (First-In-Last-Out，FILO) 的特性，使得堆疊成為一個非常實用的資料結構。就像疊放盤子一樣，我們可以將資料一個個放入堆疊，需要時再依序取出。堆疊提供了一種有序且方便管理的方式來處理資料，讓程式運行更加高效。
堆疊 (Stack): 堆疊是一種抽象資料型別 (Abstract Data Type，ADT)抽象資料型別是一種描述資料的行為和操作，而不關心其具體實現方式的資料型別。，它以後進先出 (Last-In-First-Out，LIFO) 的方式存儲和檢索資料。堆疊的操作主要包括推入 (Push) 和彈出 (Pop)，分別對應資料的插入和刪除。
堆疊的操作特性使其非常適合處理具有階層性 (Hierarchical)階層性指的是資料之間存在著上下層的關係，就像一棵樹的結構一樣。或遞迴性 (Recursive)遞迴性指的是一個問題可以分解為多個相同但規模更小的子問題，並且子問題的解可以用來構建原問題的解。的問題。例如，在函式調用中，後調用的函式總是先完成執行，這就形成了一個函式調用堆疊。再如，在迷宮求解、括號匹配等問題中，堆疊都扮演著至關重要的角色。
堆疊的操作
堆疊主要支持兩種操作：推入 (Push) 和彈出 (Pop)。
- 推入 (Push): 將一個元素添加到堆疊的頂部。
- 彈出 (Pop): 移除並返回堆疊頂部的元素。
此外，還有一些常用的輔助操作：
- 查看頂部元素 (Peek): 返回堆疊頂部的元素，但不移除它。
- 判斷是否為空 (IsEmpty): 檢查堆疊是否為空。
- 獲取元素數量 (Count): 返回堆疊中元素的數量。
使用這些操作，就可以輕鬆地管理堆疊中的數據，並實現各種基於堆疊的算法和功能。
堆疊的實現
在 VB.NET 中，可以使用System.Collections.Generic命名空間提供的Stack (Of T)泛型類別來實現堆疊。這個類別提供了一組方便的方法和屬性，使得操作堆疊變得非常簡單。
下面是使用Stack (Of T)類別實現堆疊的基本範例：
Imports System.Collections.Generic
Public Class Form1
Private Sub Form1_Load(sender As Object, e As EventArgs) Handles MyBase.Load
' 建立一個字串類型的堆疊
Dim stack As New Stack(Of String)()
' 推入元素到堆疊
stack.Push("apple")
stack.Push("banana")
stack.Push("cherry")
' 輸出堆疊中的元素數量
MessageBox.Show($"堆疊中有 {stack.Count} 個元素")
' 查看堆疊頂部的元素
MessageBox.Show($"堆疊頂部的元素是：{stack.Peek()}")
' 彈出堆疊頂部的元素
Dim item As String = stack.Pop()
MessageBox.Show($"彈出的元素是：{item}")
' 檢查堆疊是否為空
If stack.Count = 0 Then
MessageBox.Show("堆疊目前為空")
Else
MessageBox.Show($"堆疊中還有 {stack.Count} 個元素")
End If
End Sub
End Class
範例首先建立了一個名為stack的字串類型堆疊。接著，使用Push方法將三個元素推入堆疊。
接下來，使用Count屬性輸出堆疊中的元素數量，並使用Peek方法查看堆疊頂部的元素，但不移除它。
然後，使用Pop方法彈出堆疊頂部的元素，並將其存儲在item變數中。彈出後，堆疊中的元素數量減少了一個。
最後，使用Count屬性檢查堆疊是否為空。如果堆疊為空，則輸出相應的提示信息；否則，輸出堆疊中剩餘的元素數量。
這個範例展示了使用Stack (Of T)類別實現堆疊的基本操作，包括推入元素、彈出元素、查看頂部元素以及檢查堆疊是否為空等。通過這些操作，就可以輕鬆地管理堆疊中的數據。
堆疊的應用
堆疊在許多場景中都有著廣泛的應用，特別是在需要追蹤歷史狀態、實現遞迴算法或處理具有階層性的數據時。以下是一些常見的堆疊應用案例：
函式調用堆疊
在程式執行過程中，每次函式調用都會將函式的相關信息（如返回地址、參數等）推入堆疊，函式執行完畢後再從堆疊中彈出。這樣就形成了一個函式調用堆疊，記錄了函式的調用順序和歷史。
表達式求值
在對數學表達式進行求值時，可以使用堆疊來處理運算符號和操作數。通過將操作數推入堆疊，並根據運算符號的優先級和結合性進行計算，最終得到表達式的結果。
瀏覽器的前進和後退
瀏覽器中的前進和後退功能可以使用堆疊來實現。每次訪問一個新頁面時，將當前頁面的 URL 推入堆疊。當用戶點擊後退按鈕時，從堆疊中彈出上一個頁面的 URL 並導航到該頁面。
迷宮求解
在迷宮求解問題中，可以使用堆疊來記錄探索的路徑。每次遇到岔路口時，將當前位置推入堆疊，然後選擇一個方向繼續探索。如果達到死胡同，就從堆疊中彈出上一個位置，回溯到之前的岔路口，直到找到出口或遍歷完整個迷宮。
這些僅僅是堆疊應用的幾個典型案例，堆疊在許多其他領域和問題中也都有著廣泛的應用。無論是在算法設計、數據處理，還是在軟件工程中，堆疊都扮演著重要的角色，幫助我們更高效、更簡潔地解決問題。
堆疊的應用範例
下面是一個使用堆疊來檢查括號匹配的完整範例。這個範例將展示如何使用堆疊來解決實際問題，並且使用窗體控件來與用戶進行交互。
元件清單
- TextBox1：用於輸入待檢查的括號字串的文本框控件。
- Button1：用於觸發括號匹配檢查的按鈕控件。
- Label1：用於顯示檢查結果的標籤控件。
Imports System.Collections.Generic
Public Class Form1
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim input As String = TextBox1.Text
Dim stack As New Stack(Of Char)()
Dim isMatched As Boolean = True
For Each c As Char In input
If c = "(" OrElse c = "[" OrElse c = "{" Then
' 如果是左括號，則推入堆疊
stack.Push(c)
ElseIf c = ")" OrElse c = "]" OrElse c = "}" Then
' 如果是右括號，則檢查堆疊頂部的元素是否匹配
If stack.Count = 0 Then
' 如果堆疊為空，說明沒有匹配的左括號
isMatched = False
Exit For
End If
Dim top As Char = stack.Pop()
If (c = ")" AndAlso top <> "(") OrElse
(c = "]" AndAlso top <> "[") OrElse
(c = "}" AndAlso top <> "{") Then
' 如果堆疊頂部的元素與當前右括號不匹配，說明括號不匹配
isMatched = False
Exit For
End If
End If
Next
If isMatched AndAlso stack.Count = 0 Then
' 如果所有括號都匹配，並且堆疊為空，說明括號完全匹配
Label1.Text = "括號完全匹配"
Else
Label1.Text = "括號不匹配"
End If
End Sub
End Class
在這個範例中，我們首先從TextBox1中獲取用戶輸入的括號字串，然後建立一個字符類型的堆疊stack和一個布爾變量isMatched，用於記錄括號是否匹配。
接下來，我們遍歷輸入字串中的每個字符。如果當前字符是左括號，就將其推入堆疊；如果是右括號，則檢查堆疊頂部的元素是否與之匹配。如果堆疊為空或者頂部元素不匹配，說明括號不匹配，將isMatched設為False並退出循環。
最後，根據isMatched的值和堆疊是否為空，在Label1中顯示相應的檢查結果。如果所有括號都匹配且堆疊為空，說明括號完全匹配；否則，說明括號不匹配。
這個範例展示了如何使用堆疊來解決括號匹配問題，通過將左括號推入堆疊，並在遇到右括號時進行匹配檢查，可以有效地判斷括號是否正確配對。同時，使用窗體控件實現了與用戶的交互，使得程式更加直觀和易於使用。
堆疊的效能分析
在使用堆疊時，瞭解其效能特點對於編寫高效的程式非常重要。以下是堆疊的效能分析：
| 操作 | 時間複雜度 | 說明 |
|---|---|---|
| Push | O(1) | 將元素推入堆疊頂部，是一個恆定時間的操作。 |
| Pop | O(1) | 從堆疊頂部彈出元素，也是一個恆定時間的操作。 |
| Peek | O(1) | 查看堆疊頂部的元素，而不移除它，是一個恆定時間的操作。 |
| IsEmpty | O(1) | 檢查堆疊是否為空，是一個恆定時間的操作。 |
| Count | O(1) | 獲取堆疊中元素的數量，是一個恆定時間的操作。 |
從上述分析可以看出，堆疊的基本操作（如推入、彈出、查看頂部元素等）都是恆定時間的操作，即時間複雜度為 O(1)。這意味著，無論堆疊中存儲了多少元素，這些操作的執行時間都是固定的，不會隨著元素數量的增加而增加。
然而，堆疊的效能也有一些限制：
- 堆疊的大小受限於可用內存。如果堆疊的增長超出了可用內存，就會導致堆疊溢出。
- 堆疊只允許在頂部進行操作，不能直接訪問堆疊中間的元素。如果需要訪問堆疊中間的元素，必須先彈出頂部的元素。
儘管有這些限制，堆疊仍然是一種非常高效且實用的資料結構。在適當的場景下使用堆疊，可以大大提高程式的效能和可讀性。同時，通過合理地設計算法和管理堆疊的大小，可以避免堆疊溢出等問題，確保程式的正確性和穩定性。