一、概念：
棧是一種 “操作受限” 的線性表，體現(xiàn)在只能在一端插入刪除數(shù)據(jù)，符合先進后出的特性。
二、操作：
入棧 push：
從棧頂放入元素， O（1）
出棧 pop：
從棧頂取出元素， O（1）
取棧頂元素 top 或者 peek：
訪問棧頂元素但不彈出， O（1）
三、棧的特性：
棧可以用數(shù)組實現(xiàn)（順序棧），也可以用鏈表實現(xiàn)（鏈式棧）
四、注意點：
1、函數(shù)調(diào)用棧
2、編譯器利用棧實現(xiàn)表達式求值
3、瀏覽器的前進后退功能使用棧
五、常見面試題：
例題1：1021. 刪除最外層的括號
https://leetcode-cn.com/problems/remove-outermost-parentheses/
有效括號字符串為空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括號字符串，+ 代表字符串的連接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括號字符串。
如果有效字符串 S 非空，且不存在將其拆分為 S = A+B 的方法，我們稱其為原語（primitive），其中 A 和 B 都是非空有效括號字符串。
給出一個非空有效字符串 S，考慮將其進行原語化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括號字符串原語。
對 S 進行原語化分解，刪除分解中每個原語字符串的最外層括號，返回 S 。
示例 1：
輸入："(()())(())"
輸出："()()()"
解釋：
輸入字符串為 "(()())(())"，原語化分解得到 "(()())" + "(())"，
刪除每個部分中的最外層括號后得到 "()()" + "()" = "()()()"。
示例 2：
輸入："(()())(())(()(()))"
輸出："()()()()(())"
解釋：
輸入字符串為 "(()())(())(()(()))"，原語化分解得到 "(()())" + "(())" + "(()(()))"，
刪除每個部分中的最外層括號后得到 "()()" + "()" + "()(())" = "()()()()(())"。
示例 3：
輸入："()()"
輸出：""
解釋：
輸入字符串為 "()()"，原語化分解得到 "()" + "()"，
刪除每個部分中的最外層括號后得到 "" + "" = ""。
思路：
思路：借助輔助棧，如果是左括號，同時stack中還有元素的話，則加入返回的結(jié)果集中；如果是右括號，先彈出一個棧中元素，如果棧中還有元素的話，則加入至返回的結(jié)果集中。
時間復雜度：O（n），n為字符串的長度
空間復雜度：O（k） ，0 < k < n
代碼實現(xiàn)：
class Solution:
def removeOuterParentheses(self, S: str) -> str:
res = ''
stack = []
for s in S:
if s == '(':
if stack:
res += s
stack.append(s)
else:
stack.pop()
if stack:
res += s
return res
例題2：394. 字符串解碼 https://leetcode-cn.com/problems/decode-string/
給定一個經(jīng)過編碼的字符串，返回它解碼后的字符串。
編碼規(guī)則為: k[encoded_string]，表示其中方括號內(nèi)部的 encoded_string 正好重復 k 次。注意 k 保證為正整數(shù)。
你可以認為輸入字符串總是有效的；輸入字符串中沒有額外的空格，且輸入的方括號總是符合格式要求的。
此外，你可以認為原始數(shù)據(jù)不包含數(shù)字，所有的數(shù)字只表示重復的次數(shù) k ，例如不會出現(xiàn)像 3a 或 2[4] 的輸入。
示例 1：
輸入：s = "3[a]2[bc]"
輸出："aaabcbc"
示例 2：
輸入：s = "3[a2[c]]"
輸出："accaccacc"
示例 3：
輸入：s = "2[abc]3[cd]ef"
輸出："abcabccdcdcdef"
示例 4：
輸入：s = "abc3[cd]xyz"
輸出："abccdcdcdxyz"
思路：
思路：借助輔助棧
1、遇到左括號 '['，則將結(jié)果和乘數(shù)壓入棧中
2、遇到右括號 ']'， 則彈出上次記錄的res結(jié)果和乘數(shù)，進行當前結(jié)果res的拼接
3、遇到數(shù)字，則進行乘數(shù)計算
4、遇到字母，則加入返回結(jié)果集中
時間復雜度：O（n）
空間復雜度：O（1）
代碼實現(xiàn)：
class Solution:
def decodeString(self, s: str) -> str:
stack, res, multi = [], "", 0
for c in s:
if c == '[':
stack.append([multi, res])
res, multi = "", 0
elif c == ']':
cur_multi, last_res = stack.pop()
res = last_res + cur_multi * res
elif '0' <= c <= '9':
multi = multi * 10 + int(c)
else:
res += c
return res
例題3： 20. 有效的括號https://leetcode-cn.com/problems/valid-parentheses/
給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。
有效字符串需滿足：
左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
示例 1：
輸入：s = "()"
輸出：true
示例 2：
輸入：s = "()[]{}"
輸出：true
示例 3：
輸入：s = "(]"
輸出：false
示例 4：
輸入：s = "([)]"
輸出：false
示例 5：
輸入：s = "{[]}"
輸出：true
思路：
思路：借助輔助棧
1、如果是左括號，則壓入棧中；
2、如果是右括號，先判斷棧中是否有元素，無的話，則為False；有的話，根據(jù)棧中的左括號取出字典中的右括號，判斷是否和當前右括號一致。
3、最后判斷棧中是否還有元素，有的話，說明括號不能完全匹配。返回False。
時間復雜度：O（n）
空間復雜度：O（n）
代碼實現(xiàn)：
class Solution:
def isValid(self, s: str) -> bool:
dic = {'{': '}', '[': ']', '(': ')'}
stack = []
for c in s:
if c in dic:
stack.append(c)
else:
if not stack:
return False
if dic[stack.pop()] != c:
return False
return len(stack) == 0
撰寫記錄
2021.01.18-07:25:00-第一次撰寫
2021.02.13-23:15:00-第二次撰寫
2021.02.14-11:22:00-第三次撰寫
