在數據結構的舞臺上，棧與隊列宛如兩位優雅的舞者，以獨特的節奏演繹著數據的進出規則。它們雖不像順序表與鏈表那般復雜多變，卻有著令人著迷的簡潔與實用，在眾多程序場景中發揮著不可或缺的作用。今天，就讓我們一同去探索棧與隊列的奇妙世界，掌握它們的操作技巧，并領略它們在實際應用中的風采。
?
棧：后進先出的奇妙空間
?
棧的概念
?
棧是一種特殊的線性表，它的特殊之處在于操作受限。棧的插入和刪除操作只能在表的一端進行，這一端被稱為 “棧頂”，另一端稱為 “棧底”。這就使得棧具備了 “后進先出”（Last In First Out，LIFO）的特點，就像一個裝滿盤子的摞柱，最后放上去的盤子總是最先被取下來。
?
棧的基本操作
?
- 入棧（Push） ：將一個元素插入到棧頂位置。如果棧已滿，則無法繼續入棧，這種情況稱為 “棧溢出”。
- 出棧（Pop） ：將棧頂元素移除。若棧為空時執行出棧操作，則會引發 “空棧” 錯誤。
- 獲取棧頂元素（Top） ：查看棧頂元素的值，但不將其移出棧。
?
棧的應用場景
?
- 括號匹配檢測 ：在編寫代碼或處理數學表達式時，括號的正確匹配至關重要。棧能輕松應對這一問題。例如，當我們遇到一個左括號時，將其入棧；當遇到右括號時，檢查棧頂是否為對應的左括號，若是則出棧，否則說明括號不匹配。通過這種方式，我們可以精準判斷括號序列是否合法。
- 遞歸函數的實現 ：遞歸本質上是函數自己調用自己，在這個過程中，系統會使用一個隱式的棧來保存函數的調用信息，包括參數、返回地址等。這個棧就是 “調用棧”。每當一個遞歸函數調用自身時，相關信息就會被壓入棧中；當函數執行完畢返回時，信息從棧中彈出，從而保證了程序能夠正確地回到上一層調用的位置并繼續執行。
?
棧的代碼實現（以 Python 為例）
python
class Stack:
? ? def __init__(self):
? ? ? ? self.items = []
?
? ? def is_empty(self):
? ? ? ? return len(self.items) == 0
?
? ? def push(self, item):
? ? ? ? self.items.append(item)
?
? ? def pop(self):
? ? ? ? if self.is_empty():
? ? ? ? ? ? raise IndexError("棧為空，無法出棧")
? ? ? ? return self.items.pop()
?
? ? def top(self):
? ? ? ? if self.is_empty():
? ? ? ? ? ? raise IndexError("棧為空，無棧頂元素")
? ? ? ? return self.items[-1]
?
隊列：先進先出的有序行進
?
隊列的概念
?
隊列同樣是特殊的線性表，但它的操作規則與棧截然不同。隊列的插入操作只能在一端（稱為 “隊尾”）進行，刪除操作只能在另一端（稱為 “隊頭”）進行。這種操作規則使得隊列呈現出 “先進先出”（First In First Out，FIFO）的特性，就像生活中的排隊場景，先來的人先接受服務，后來的人排在隊伍末尾等待。
?
隊列的基本操作
?
- 入隊（Enqueue） ：將一個元素添加到隊尾。若隊列已滿，則無法繼續入隊。
- 出隊（Dequeue） ：將隊頭元素移除。若隊列為空時執行出隊操作，則會引發錯誤。
- 獲取隊頭元素（Front） ：查看隊頭元素的值，但不將其移出隊列。
- 獲取隊尾元素（Rear） ：查看隊尾元素的值。
?
隊列的應用場景
?
- 任務調度模擬 ：在操作系統中，多個任務常常需要共享有限的資源，如 CPU。隊列可用于模擬任務的調度過程。任務按照提交的先后順序進入隊列，等待 CPU 的分配。每當 CPU 完成一個任務，就從隊列中取出下一個任務進行處理，確保了任務的公平調度。
- 緩沖區管理 ：在數據傳輸過程中，如網絡通信或文件讀寫，隊列可充當緩沖區的角色。數據以隊列的形式暫存，發送方將數據依次寫入隊尾，接收方從隊頭依次讀取數據，使得數據的發送速度和接收速度能夠協調一致，避免數據丟失或阻塞。
?
隊列的代碼實現（以 Python 為例）
python
class Queue:
? ? def __init__(self):
? ? ? ? self.items = []
?
? ? def is_empty(self):
? ? ? ? return len(self.items) == 0
?
? ? def enqueue(self, item):
? ? ? ? self.items.append(item)
?
? ? def dequeue(self):
? ? ? ? if self.is_empty():
? ? ? ? ? ? raise IndexError("隊列為空，無法出隊")
? ? ? ? return self.items.pop(0)
?
? ? def front(self):
? ? ? ? if self.is_empty():
? ? ? ? ? ? raise IndexError("隊列為空，無隊頭元素")
? ? ? ? return self.items[0]
?
? ? def rear(self):
? ? ? ? if self.is_empty():
? ? ? ? ? ? raise IndexError("隊列為空，無隊尾元素")
? ? ? ? return self.items[-1]
?
棧與隊列的專項練習
?
棧的練習
?
? 1. 括號匹配驗證 ：編寫一個函數，判斷一個包含多種括號（如圓括號、方括號、大括號）的字符串是否匹配。例如，"({[]})" 是匹配的，而 "({[})]" 是不匹配的。
? ? ?- 思路：利用棧的后進先出特性，遇到左括號入棧，遇到右括號則檢查棧頂是否為對應的左括號。若匹配則出棧，否則返回不匹配。遍歷完整個字符串后，若棧為空則說明括號全部匹配。
?
? 2. 遞歸函數改寫 ：將一個遞歸計算斐波那契數列的函數改寫為非遞歸形式，借助棧來模擬遞歸過程。
? ? ?- 思路：在遞歸中，每次函數調用會保存當前的參數和返回地址。用棧來手動保存這些信息，通過循環逐步處理棧中的元素，模擬遞歸的調用過程，最終得到斐波那契數。
?
隊列的練習
?
? 1. 模擬超市收銀 ：假設超市有多個收銀臺，顧客按照到達時間進入隊列，每個收銀臺每次只能為一個顧客服務。編寫程序模擬顧客排隊和收銀的過程，計算每個顧客的等待時間和服務完成時間。
? ? ?- 思路：使用一個隊列來存儲等待的顧客，按照到達時間依次入隊。為每個收銀臺設置一個服務隊列，當收銀臺空閑時，從主隊列中取出顧客并將其分配到服務隊列中。記錄每個顧客進入隊列、開始服務和結束服務的時間，從而計算等待時間。
?
? 2. 生產者 - 消費者問題 ：模擬生產者和消費者之間的關系。生產者生產產品并放入緩沖區隊列，消費者從緩沖區隊列中取出產品進行消費。要求實現生產者和消費者之間的同步，避免緩沖區溢出或消費者取空緩沖區。
? ? ?- 思路：利用隊列作為緩沖區。生產者在生產產品后嘗試將其入隊，如果隊列已滿則等待。消費者在消費前檢查隊列是否為空，如果為空則等待。通過引入鎖和條件變量等同步機制，確保生產者和消費者對隊列的操作是線程安全的。
?
總結與交流
?
通過學習棧和隊列的概念、操作以及應用場景，我們對這兩種數據結構有了較為全面且深入的理解，并通過代碼實現和專項練習進一步鞏固了知識。棧以其后進先出的特點在括號匹配、遞歸等問題中大顯身手，而隊列憑借先進先出的規則在任務調度、緩沖區管理等場景中發揮著關鍵作用。
?
現在，我想邀請大家在評論區分享自己對棧和隊列的見解，或是你在學習和實踐中遇到的有趣問題與解決方案。有沒有在解決括號匹配問題時發現一些獨特的技巧？或者在模擬任務調度時遇到了什么挑戰？讓我們共同交流、探討，讓知識在互動中不斷深化，一起在這條數據結構與算法的學習之路上砥礪前行！
