LeetCode刷題小記六、【棧與隊列】

1.棧與隊列

文章目錄

- 1.棧與隊列
- 寫在前面
- - 1.1棧與隊列理論基礎
  - 1.2用棧實現隊列
  - 1.3用隊列實現棧
  - 1.4有效的括號
  - 1.5刪除字符串中的所有相鄰重復項
  - 1.6逆波蘭表達式求值
  - 1.7滑動窗口最大值
  - 1.8前K個高頻元素
- Reference

寫在前面

本系列筆記主要作為筆者刷題的題解，所用的語言為Python3，若于您有助，不勝榮幸。

1.1棧與隊列理論基礎

棧[stack]是一種先進后出邏輯的線性數據結構。棧的常用操作如表所示

方法	描述	時間復雜度
`push()`	元素入棧	$\mathcal{O}(1)$
`pop()`	棧頂元素出棧	$\mathcal{O}(1)$
`peek()`	訪問棧頂元素	$\mathcal{O}(1)$

隊列[queue]是一種先進先出邏輯的線性數據結構。我們將隊列的頭部稱為“隊首”，尾部稱為“隊尾”，將把元素加入隊尾的操作稱為“入隊”，刪除隊首元素的操作稱為“出隊”。為了統一我們采用和棧相同的命名方式

方法	描述	時間復雜度
`push()`	元素入隊，即將元素添加到隊尾	$\mathcal{O}(1)$
`pop()`	隊首元素出隊	$\mathcal{O}(1)$
`peek()`	訪問隊首元素	$\mathcal{O}(1)$

1.2用棧實現隊列

232. 用棧實現隊列

請你僅使用兩個棧實現先入先出隊列。隊列應當支持一般隊列支持的所有操作（push、pop、peek、empty）：

實現 MyQueue 類：

void push(int x) 將元素 x 推到隊列的末尾
int pop() 從隊列的開頭移除并返回元素
int peek() 返回隊列開頭的元素
boolean empty() 如果隊列為空，返回 true ；否則，返回 false

思路:使用兩個棧來實現一個隊列，我們需要一個棧充當in，負責接收元素，另一個棧充當out，負責彈出元素，每當我們需要彈出元素的時候，我們就將in中的所有元素彈出并加入到out中，然后再從out中彈出棧頂元素。

class MyQueue:def __init__(self):self.stack_in: List = []self.stack_out: List = []def push(self, x: int) -> None:while self.stack_out:       # 將out棧中的元素恢復到in棧中self.stack_in.append(self.stack_out.pop())self.stack_in.append(x)     # 添加新元素def pop(self) -> int:if self.empty():return Noneif self.stack_out:return self.stack_out.pop()else:while self.stack_in:self.stack_out.append(self.stack_in.pop())return self.stack_out.pop()def peek(self) -> int:res: int = self.pop()self.stack_out.append(res)return resdef empty(self) -> bool:return not self.stack_in and not self.stack_out     # 只要in或out含有元素，說明隊列不為空

1.3用隊列實現棧

225. 用隊列實現棧

請你僅使用兩個隊列實現一個后入先出（LIFO）的棧，并支持普通棧的全部四種操作（push、top、pop 和 empty）。

實現 MyStack 類：

void push(int x) 將元素 x 壓入棧頂。
int pop() 移除并返回棧頂元素。
int top() 返回棧頂元素。
boolean empty() 如果棧是空的，返回 true ；否則，返回 false 。

思路：我們可以使用兩個隊列來實現一個棧，或者使用一個隊列來實現一個棧。兩種方法都是可以的

解法一：使用一個隊列

# 使用一個隊列來實現棧
from collections import deque
class MyStack:def __init__(self):self.queue: deque = deque()self.size: int = 0def push(self, x: int) -> None:self.queue.append(x)self.size += 1def pop(self) -> int:if self.empty():return Nonefor _ in range(self.size-1):self.queue.append(self.queue.popleft())self.size -= 1return self.queue.popleft()def top(self) -> int:if self.empty():return Noneans: int = self.pop()self.push(ans)return ansdef empty(self) -> bool:return not self.queue

解法二：使用兩個隊列

from collections import deque
class MyStack:def __init__(self):self.que_in: deque = deque()self.que_out: deque = deque()def push(self, x: int) -> None:while self.que_out:         # 將out中的元素恢復到in中self.que_in.append(self.que_out.popleft())self.que_in.append(x)       # 添加新的元素def pop(self) -> int:"""1. 首先確認不空2. 因為隊列的特殊性，FIFO，所以我們只有在pop()的時候才會使用queue_out3. 先把queue_in中的所有元素（除了最后一個），依次出列放進queue_out4. 交換in和out，此時out里只有一個元素5. 把out中的pop出來，即是原隊列的最后一個tip：這不能像棧實現隊列一樣，因為另一個queue也是FIFO，如果執行pop()它不能像stack一樣從另一個pop()，所以干脆in只用來存數據，pop()的時候兩個進行交換"""if self.empty():return Nonefor _ in range(len(self.que_in)-1):     # 保存前n-1個元素self.que_out.append(self.que_in.popleft())self.que_out, self.que_in = self.que_in, self.que_out   # 這里很重要return self.que_out.popleft()def top(self) -> int:if self.empty():return Nonefor _ in range(len(self.que_in)-1):     # 保存前n-1個元素self.que_out.append(self.que_in.popleft())self.que_out, self.que_in = self.que_in, self.que_outans: int = self.que_out.popleft()self.que_in.append(ans)return ansdef empty(self) -> bool:return not self.que_in and not self.que_out

使用兩個隊列，用存儲空間來換取時間，明顯看出這樣的執行速度更快。

1.4有效的括號

20. 有效的括號

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判斷字符串是否有效。

有效字符串需滿足：

左括號必須用相同類型的右括號閉合。
左括號必須以正確的順序閉合。
每個右括號都有一個對應的相同類型的左括號。

思路：首先我們需要找到有哪些不匹配的情況，其實這道題目一共只有三種不匹配的情況，分別是：

情況1：字符串左邊存在多余的括號([{}]()
情況2：字符串中間存在不匹配的括號[{(]}]
情況3：字符串右邊存在多余的括號[{}]()))

針對這三種情況我們分別來進行處理即可。

class Solution:def isValid(self, s: str) -> bool:stack: List = []if len(s) % 2 != 0:     # 剪枝（可省略）return Falsefor char in s:if char == '(':stack.append(')')elif char == '[':stack.append(']')elif char == '{':stack.append('}')elif not stack or char != stack[-1]:        # 處理情況二中間不匹配，或者情況三右邊有多余的元素return Falseelse:stack.pop()return True if not stack else False             # 處理情況一左邊有多余的元素

1.5刪除字符串中的所有相鄰重復項

1047. 刪除字符串中的所有相鄰重復項

給出由小寫字母組成的字符串 S，重復項刪除操作會選擇兩個相鄰且相同的字母，并刪除它們。

在 S 上反復執行重復項刪除操作，直到無法繼續刪除。

在完成所有重復項刪除操作后返回最終的字符串。答案保證唯一。

思路：這是一道典型的使用棧來完成的題目，我們只需要判斷入棧的元素是否等于棧頂元素，如果等于則表明這是一對需要刪除的元素，我們只需要移除棧頂元素即可，最后返回由棧中所有元素構成的字符串即可。

class Solution:def removeDuplicates(self, s: str) -> str:stack: List[str] = []for c in s:if stack and c == stack[-1]:    # 如果當前入棧的元素等于棧頂元素，且棧不為空，則刪除棧頂元素stack.pop()else:stack.append(c)return ''.join(stack)

1.6逆波蘭表達式求值

150. 逆波蘭表達式求值

給你一個字符串數組 tokens ，表示一個根據逆波蘭表示法表示的算術表達式。

請你計算該表達式。返回一個表示表達式值的整數。

思路：什么是逆波蘭表達式呢？這其實是一種方便計算機運算的存儲方式，逆波蘭表達式其實是相當于二叉樹的后序遍歷，本題中每一個子表達式要得出一個結果，然后拿這個結果再進行運算，這就非常像一個字符串匹配的問題，我們就可以用棧這種數據結構來進行處理。注意：第一個彈出的數字應該在運算符的后面。

class Solution:       def evalRPN(self, tokens: List[str]) -> int:op_map = {'+': add, '-': sub, '*': mul, '/': lambda x, y: int(x/y)}stack: List[int] = []for c in tokens:if c in ['+', '-', '*', '/']:num2 = stack.pop()num1 = stack.pop()stack.append(op_map[c](num1, num2)) # 第一個出來的在運算符后面else:stack.append(int(c))return stack[-1]

1.7滑動窗口最大值

239. 滑動窗口最大值

給你一個整數數組 nums，有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口內的 k 個數字。滑動窗口每次只向右移動一位。

返回 滑動窗口中的最大值 。

思路：維護一個單調隊列，如果push()進的值大于當前隊列的隊首位置的，則將隊列清空，再將這個值push()進來，這樣就維護了一個單調遞減的隊列，并且每次訪問隊首位置就能夠訪問隊列中的最大值，那我們應該如何做pop()呢？通常來說做pop()不需要傳入任何的值，但是這里我們可以判斷我們當前需要pop()的值是否和隊首的位置相等，如果相等則表明這是需要彈出的元素：

pop(value)：如果窗口移除的元素value等于單調隊列的出口元素，那么隊列彈出元素，否則不用任何操作
push(value)：如果push的元素value大于入口元素的數值，那么就將隊列入口的元素彈出，直到push元素的數值小于等于隊列入口元素的數值為止

保持如上規則，每次窗口移動的時候，只要問que.front()就可以返回當前窗口的最大值。

from collections import deque
class MyQueue:def __init__(self):	# 單調隊列，從大到小self.que: deque = deque()#每次彈出的時候，比較當前要彈出的數值是否等于隊列出口元素的數值，如果相等則彈出。#同時pop之前判斷隊列當前是否為空。def pop(self, value):if self.que and self.que[0] == value:self.que.popleft()#如果push的數值大于入口元素的數值，那么就將隊列后端的數值彈出，直到push的數值小于等于隊列入口元素的數值為止。#這樣就保持了隊列里的數值是單調從大到小的了。def push(self, value):while self.que and value > self.que[-1]:self.que.pop()self.que.append(value)def front(self):return self.que[0]class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:result: List[int] = []queue: MyQueue = MyQueue()for i in range(k):queue.push(nums[i])result.append(queue.front())for i in range(k, len(nums)):queue.pop(nums[i-k])    # 判斷進入上個隊列的首個元素還存在嗎？如果存在就表明這個元素是最大的值，并且沒有被pop掉，就手動popleft掉這個元素queue.push(nums[i])result.append(queue.front())return result

1.8前K個高頻元素

347. 前 K 個高頻元素

給你一個整數數組 nums 和一個整數 k ，請你返回其中出現頻率前 k 高的元素。你可以按 任意順序 返回答案。

思路：先使用哈希法得到一個可供查詢的map，然后獲取這個map中value值的前k個即可，但是我們無需對整個map都進行排序，而是我們只維護一個大小為k的有序區間。這就涉及到了大頂堆和小頂堆這樣的數據結構。這里涉及到選擇小頂堆還是大頂堆的問題，如果我們選擇大頂堆的話，每次彈出的元素都是最大的元素，這樣我們就把最大的元素都彈出了，只保留了較小的元素，相反如果我們選擇小頂堆的話，每次彈出都是彈出最小的元素，這樣就保留了加大的元素。

import heapq
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:elem_map: dict = {}for elem in nums:elem_map[elem] = elem_map.get(elem, 0) + 1# 對頻率進行排序,定義一個小頂堆pri_que = []for key, value in elem_map.items():heapq.heappush(pri_que, (value, key))   # heapq按照tuple中的第一個元素來進行排序if len(pri_que) > k:    #如果堆的大小大于了K，則隊列彈出，保證堆的大小一直為kheapq.heappop(pri_que)return [key for value, key in pri_que]      # 對返回的順序沒有要求，我們可以不用每次都進行彈出

import heapq
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:elem_map: dict = {}for elem in nums:elem_map[elem] = elem_map.get(elem, 0) + 1# 對頻率進行排序,定義一個小頂堆pri_que: List[int] = []for key, value in elem_map.items():heapq.heappush(pri_que, (value, key))   # heapq按照tuple中的第一個元素來進行排序if len(pri_que) > k:    #如果堆的大小大于了K，則隊列彈出，保證堆的大小一直為kheapq.heappop(pri_que)res: List[int] = [0] * kfor i in range(k):          # 按照頻率順序進行彈出res[k-i-1] = heapq.heappop(pri_que)[1]return res