[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; } } ~~~