[TOC] # 棧（stack） 定義： * 棧是一種線性結構，來自線性表數據結構，“操作受限”的線性表 * 是限制在表的一端進行插入和刪除操作的線性表。又稱之為后進先出（Last In First Out）或先進后出FILO（First In Last Out） * 棧頂（Top）：允許進行插入、刪除操作的一端，又稱為表尾。用棧頂指針（top）來指示棧頂元素 * 棧底（Bottom）：是固定端，又稱為表頭  * 在計算機世界中，棧擁有著不可思議的作用 # 棧在計算機中的實現方式 * 硬堆棧：利用CPU中的某些寄存器組或類似的硬件或使用內存的特殊區域來實現。這類堆棧容量有限，但速度很快。 * 軟堆棧：這類堆棧主要是在內存中實現。堆棧容量可以達到很大。在實現方式上，又有動態方式和靜態方式兩種 # 棧的類型 * 順序棧：用數組實現的棧 * 鏈式棧：用鏈表實現的棧 # 棧的漸進時間復雜度 * 出棧：不會涉及內存的重新申請和數據的搬移，出棧的時間復雜度是O(1) * 入棧：當棧有空閑空間時，入棧操作的時間復雜度為O(1)。但當空間不夠時，就需要重新申請內存和數據遷移，所以時間復雜度就變成了O(n)。 # 棧的應用 * 無處不在的Undo操作（撤銷）：編輯器中的撤銷操作 * 系統棧：記錄代碼中斷執行的位置，以便后面從這個地方開始執行  * 括號匹配：編譯器 # 代碼實現 ## 鏈式方式 ~~~ class LNode { public $mElem; public $mNext; public function __construct() { $this->mElem = null; $this->mNext = null; } } ~~~ ``` class StackOnLinkedList { public $mNext;//頭指針，指向棧頂元素,既保存了棧頂元素的值，還保存了一個指向下一個元素的指針 public static $mLength;//棧元素個數 /** * 初始化棧 */ public function __construct() { $this->mNext = null; self::$mLength = 0; } /** * 元素進棧 * @param $e 進棧元素值 */ public function getPushStack($e){ $newLn = new LNode(); $newLn->mElem = $e; $newLn->mNext = $this->mNext; $this->mNext = &$newLn; self::$mLength++; } /** * 元素出棧 * @param $e 保存出棧的元素的變量 */ public function getPopStack(&$e){ if ($this->getIsEmpty()){ return false; } $p = $this->mNext; $e = $p->mElem; $this->mNext = $p->mNext; self::$mLength--; return true; } /** * 將所有元素出棧 */ public function getAllPopStack(){ $e = array(); if ($this->getIsEmpty()){ return false; }else{ while($this->mNext != null){ $e[] = $this->mNext->mElem; $this->mNext = $this->mNext->mNext; } } self::$mLength = 0; return $e; } /** * 判斷是否為空棧 */ public function getIsEmpty(){ if ($this->mNext == null){ return true; }else{ return false; } } } ``` ## LeetCode題目(有效的括號) 題目： ``` 給定一個只包括 '('，')'，'{'，'}'，'['，']'?的字符串，判斷字符串是否有效。 有效字符串需滿足： 左括號必須用相同類型的右括號閉合。 左括號必須以正確的順序閉合。 注意空字符串可被認為是有效字符串。 來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/valid-parentheses ``` 思路： ``` 有效字符串條件：與棧的先進后出，后進先出很契合 1. 遍歷字符串找到'(','{','['就入棧 2. 遍歷字符串找到')','}',']'就與棧頂元素匹配，匹配成功，就出棧，匹配不成功，該字符串就無效 3. 字符串遍歷完成，查看是否是空棧，如果是空棧則該字符串有效，否則無效 ``` 代碼實現： ~~~ class Solution { /** * 括號匹配 * @param String $s * @return Boolean */ function isValid(String $s) { $stack = [];//使用PHP數組實現棧，順序棧（也可以使用鏈式棧） for ($i=0;$i<strlen($s);$i++){ if ($s[$i] == '(' || $s[$i] == '{' || $s[$i] == '['){ array_push($stack,$s[$i]); } if ($s[$i] == ')' || $s[$i] == '}' || $s[$i] == ']'){ if (count($stack) == 0) return false; $topChar = array_pop($stack); if ($topChar == '(' && $s[$i] != ')' ) return false; if ($topChar == '{' && $s[$i] != '}' ) return false; if ($topChar == '[' && $s[$i] != ']' ) return false; } } if (count($stack) == 0) return true; else return false; } } ~~~