算法工程師面試必考項——棧與隊列
AI編輯：田旭
AI作者：田旭
1 知識點
1.1 棧
堆棧（英語：stack）又稱為棧或堆疊，是計算機科學中的一種抽象數(shù)據(jù)類型，只允許在有序的線性數(shù)據(jù)集合的一端（稱為堆棧頂端，英語：top）進行加入數(shù)據(jù)（英語：push）和移除數(shù)據(jù)（英語：pop）的運算。因而按照后進先出（LIFO, Last In First Out）的原理運作。
棧常用一維數(shù)組或鏈表來實現(xiàn)。
棧使用兩種基本操作：推入（壓棧，push）和彈出（彈棧，pop）：
推入：將數(shù)據(jù)放入堆棧頂端，堆棧頂端移到新放入的數(shù)據(jù)。 彈出：將堆棧頂端數(shù)據(jù)移除，堆棧頂端移到移除后的下一筆數(shù)據(jù)。
棧的基本特點：
先入后出，后入先出。 除頭尾節(jié)點之外，每個元素有一個前驅(qū)，一個后繼。
棧中的每個元素稱為一個frame。而最上層元素稱為top frame。棧只支持三個操作， pop, top, push。
pop取出棧中最上層元素(8)，棧的最上層元素變?yōu)樵缦冗M入的元素(9)。
top查看棧的最上層元素(8)。
push將一個新的元素(5)放在棧的最上層。
棧不支持其他操作。如果想取出元素12, 必須進行3次pop操作。
1.2 隊列
隊列（queue）是一種采用先進先出(FIFO)策略的抽象數(shù)據(jù)結構，即最先進隊列的數(shù)據(jù)元素，同樣要最先出隊列。隊列跟我們排隊買票一樣，先來排隊的肯定先買票，后來排隊的的后買到票。隊列如下圖所示：
隊列有兩個重要的概念，一個叫隊頭，一個叫隊尾，隊頭指向的是第一個元素，而隊尾指向的是最后一個元素。隊列跟棧一樣也是訪問受限制的，所以隊列也只有兩個主要的操作：入隊(enqueue)操作?和?出隊(dequeue)操作?。入隊操作就是將一個元素添加到隊尾，出隊操作就是從隊頭取出一個元素。
隊列的底層實現(xiàn)可以用數(shù)組和鏈表，基于數(shù)組實現(xiàn)的隊列叫作順序隊列，基于鏈表實現(xiàn)的隊列叫作鏈式隊列
隊列的操作方式和棧類似，唯一的區(qū)別在于隊列只允許新數(shù)據(jù)在后端進行添加。
2 常見面試題
2.1 棧
155. 最小棧
設計一個支持 push ，pop ，top 操作，并能在常數(shù)時間內(nèi)檢索到最小元素的棧。
push(x) —— 將元素 x 推入棧中。pop() —— 刪除棧頂?shù)脑亍op() —— 獲取棧頂元素。getMin() —— 檢索棧中的最小元素。
class MinStack:def __init__(self):"""initialize your data structure here."""self.stack = []self.minx = [] # 利用輔助棧來存儲最小值def push(self, x: int) -> None:self.stack.append(x)if not self.minx or x <= self.minx[-1]: # 如果minx沒有元素，或者當前x小于等于輔助棧頂元素，則將當前x存入輔助棧頂self.minx.append(x)def pop(self) -> None:if self.stack.pop() == self.minx[-1]: # 先進行stack.pop()，如果去除元素與輔助棧頂元素相同，則輔助棧也去除元素self.minx.pop()def top(self) -> int:return self.stack[-1] # 返回數(shù)據(jù)棧頂元素def getMin(self) -> int:return self.minx[-1] # 返回輔助棧頂元素# Your MinStack object will be instantiated and called as such:# obj = MinStack()# obj.push(x)# obj.pop()# param_3 = obj.top()# param_4 = obj.getMin()
150. 逆波蘭表達式求值
根據(jù)?逆波蘭表示法，求表達式的值。
有效的運算符包括?
+,?-,?*,?/?。每個運算對象可以是整數(shù)，也可以是另一個逆波蘭表達式。
思路：利用棧的思想，如果是數(shù)字，則壓入棧；若為符號，即執(zhí)行“pop取棧頂 -> pop取新棧頂 -> 計算”操作。
class Solution:def evalRPN(self, tokens: List[str]) -> int:symbol = ["+", "-", "*", "/"]resList = []if len(tokens) == 0:return 0else:for c in tokens:if c not in symbol:resList.append(int(c))else:b = resList.pop()a = resList.pop()if c == "+":resList.append(a+b)elif c == "-":resList.append(a-b)elif c == "*":resList.append(a*b)elif c == "/":resList.append(int(a/b))return resList[0]
394. 字符串解碼
給定一個經(jīng)過編碼的字符串，返回它解碼后的字符串。
編碼規(guī)則為: k[encoded_string]，表示其中方括號內(nèi)部的 encoded_string 正好重復 k 次。注意 k 保證為正整數(shù)。
思路：通過輔助棧進行操作
class Solution:def decodeString(self, s: str) -> str:stack = []res = ""multi = 0for c in s:if "0" <= c <= "9":multi = multi*10 + int(c) # 考慮數(shù)字是2位以上的情況elif c == "[":stack.append([multi, res]) # 當前 multi 和 res 入棧，并分別置空置 00multi = 0 # 重置res = ""elif c == "]":cur_multi, last_res = stack.pop() # 取出[]中的重復倍數(shù)和字符串res = last_res + cur_multi * res # 拼接字符串else:res += c # 遇到其他，則當字母串處理return res
利用棧進行 DFS 遞歸搜索模板
class Solution:def decodeString(self, s: str) -> str:def dfs(i):res = ""multi = 0while i < len(s):if '0' <= s[i] <= '9':multi = multi * 10 + int(s[i])# 遇到'['開始將后續(xù)的string遞歸elif s[i] == '[':i, temp = dfs(i + 1)# 注意，返回i的含義是更新上層遞歸指針位置，因為內(nèi)層遞歸已經(jīng)吃掉一串str，若不跟新i，外層仍然從i+1開始，則會重復處理內(nèi)層處理過的一串str。res += multi * tempmulti = 0# 遇到']'到達遞歸邊界，結束遞歸，返回新i和處理好的內(nèi)層reselif s[i] == ']':return i, reselse:res += s[i]i += 1return resreturn dfs(0)
94. 二叉樹的中序遍歷
給定一個二叉樹，返回它的中序?遍歷。
思路：通過stack 保存已經(jīng)訪問的元素，用于原路返回
class Solution:def inorderTraversal(self, root: TreeNode) -> List[int]:res = []stack = []while stack or root:while root:stack.append(root)root = root.leftroot = stack.pop() # 此時左子樹遍歷完成res.append(root.val) # 將父節(jié)點加入列表root = root.right # 遍歷右子樹return res
200. 島嶼數(shù)量
給定一個由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格，計算島嶼的數(shù)量。一個島被水包圍，并且它是通過水平方向或垂直方向上相鄰的陸地連接而成的。你可以假設網(wǎng)格的四個邊均被水包圍。
思路：通過深度搜索遍歷可能性（注意標記已訪問元素）
class Solution:def numIslands(self, grid: List[List[str]]) -> int:if not grid:return 0m, n = len(grid), len(grid[0])res = 0def backtrack(grid, i, j):if i < 0 or i >=m or j < 0 or j >= n or grid[i][j] != '1': # 判斷邊界returngrid[i][j] = '0' # 遍歷過的地方都標記為0，避免重復尋找backtrack(grid, i, j+1)backtrack(grid, i+1, j)backtrack(grid, i, j-1)backtrack(grid, i-1, j)for i in range(m):for j in range(n):if grid[i][j] == '1':backtrack(grid, i, j)res += 1return res
133. 克隆圖
給你無向?連通?圖中一個節(jié)點的引用，請你返回該圖的?深拷貝（克隆）。
圖中的每個節(jié)點都包含它的值?
val（int） 和其鄰居的列表（list[Node]）。
思路：遍歷整個圖，遍歷時候要記錄已經(jīng)訪問點，我們用一個字典記錄。
# DFS 深度優(yōu)先遍歷class Solution:def cloneGraph(self, node: 'Node') -> 'Node':lookup = {}def dfs(node):if not node:returnif node in lookup:return lookup[node]clone = Node(node.val, [])lookup[node] = clonefor i in node.neighbors:clone.neighbors.append(dfs(i))return clonereturn dfs(node)
# BFS 廣度優(yōu)先遍歷class Solution:def cloneGraph(self, node: 'Node') -> 'Node':from collections import dequelookup = {}if not node:returnclone = Node(node.val, [])lookup[node] = clonequeue = deque()queue.appendleft(node)while queue:temp = queue.pop()for n in temp.neighbors:if n not in lookup:lookup[n] = Node(n.val, [])queue.appendleft(n)lookup[temp].neighbors.append(lookup[n])return clone
84. 柱狀圖中最大的矩形
給定?n?個非負整數(shù)，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。
求在該柱狀圖中，能夠勾勒出來的矩形的最大面積
# 優(yōu)化中心擴展法class Solution:def largestRectangleArea(self, heights: List[int]) -> int:n = len(heights)l, r, ans = [-1] * n, [n] * n, 0for i in range(1, n):j = i - 1while j >= 0 and heights[j] >= heights[i]:j = l[j]l[i] = jfor i in range(n - 2, -1, -1):j = i + 1while j < n and heights[j] >= heights[i]:j = r[j]r[i] = jfor i in range(n):ans = max(ans, heights[i] * (r[i] - l[i] - 1))return ans
# 單調(diào)棧class Solution:def largestRectangleArea(self, heights: List[int]) -> int:"""頭部加0便于處理當棧里只有一個有效元素要彈出的時候計算面積。如果頭部不加0，最后一個有效元素被彈出的時候，棧已經(jīng)為空了，則還需要特殊處理。尾部加0，如果0最后一個入棧，所有的數(shù)都會彈出"""stack = []heights = [0] + heights + [0]res = 0for i in range(len(heights)):while stack and heights[stack[-1]] > heights[i]:tmp = stack.pop()res = max(res, (i - stack[-1] - 1) * heights[tmp])stack.append(i)return res
2.2 隊列
232. 用棧實現(xiàn)隊列
使用棧實現(xiàn)隊列的下列操作：
push(x) -- 將一個元素放入隊列的尾部。pop() -- 從隊列首部移除元素。peek() -- 返回隊列首部的元素。empty() -- 返回隊列是否為空。
思路：定義兩個棧，一個負責入棧，一個負責出棧，元素先進入入棧，再壓入出棧
class MyQueue:def __init__(self):"""Initialize your data structure here."""self.instack = []self.outstack = []def push(self, x: int) -> None:"""Push element x to the back of queue."""self.instack.append(x)def pop(self) -> int:"""Removes the element from in front of queue and returns that element."""if not self.outstack:while self.instack:self.outstack.append(self.instack.pop())return self.outstack.pop()def peek(self) -> int:"""Get the front element."""if not self.outstack:while self.instack:self.outstack.append(self.instack.pop())return self.outstack[-1]def empty(self) -> bool:"""Returns whether the queue is empty."""return not self.instack and not self.outstack
542. 01 矩陣
給定一個由 0 和 1 組成的矩陣，找出每個元素到最近的 0 的距離。
兩個相鄰元素間的距離為 1 。
思路：BFS，從0進隊列，彈出之后計算上下左右的結果，將上下左右重新進隊列進行二層操作
class Solution:def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:m, n = len(matrix), len(matrix[0])q = collections.deque([])visited = set()# 初始化隊列，將所有起始點加入for i in range(m):for j in range(n):if matrix[i][j] == 0:q.append((i, j))visited.add((i, j))# 將所有相鄰節(jié)點加入隊列while q:i, j = q.popleft()for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:if 0 <= x < m and 0 <= y < n and (x, y) not in visited:matrix[x][y] = matrix[i][j] + 1visited.add((x, y))q.append((x, y))return matrix
參考資料
堆棧-維基百科 https://juejin.im/post/6844903928476368909 LeetCode題解 https://greyireland.gitbook.io/algorithm-pattern/shu-ju-jie-gou-pian/stack_queue
推薦閱讀
機器學習算法工程師
? ??? ? ? ? ? ? ? ? ? ? ? ??????????????????一個用心的公眾號
?
