棧和隊列

棧和隊列基礎(chǔ)（Python）

棧一種先進后出，隊列先進后出。
Python中可以用list實現(xiàn)棧，用append()模擬入棧，用pop()模擬出棧。
也可以用list實現(xiàn)隊列，但是效率較低，一般用collections.deque模擬（雙端）隊列。
5. 數(shù)據(jù)結(jié)構(gòu) — Python 3.11.5 文檔

使用list進行棧的操作

stack = [3, 4, 5]
stack.append(6)
stack.append(7)
stack
[3, 4, 5, 6, 7]
stack.pop()
7
stack
[3, 4, 5, 6]

使用collections.dequez進行隊列操作

from collections import deque
queue = deque(["Eric", "John", "Michael"])
queue.append("Terry")           # Terry arrives
queue.append("Graham")          # Graham arrives
queue.popleft()                 # The first to arrive now leaves
'Eric'
queue.popleft()                 # The second to arrive now leaves
'John'
queue                           # Remaining queue in order of arrival
deque(['Michael', 'Terry', 'Graham'])

232.用棧實現(xiàn)隊列

#模擬
請你僅使用兩個棧實現(xiàn)先入先出隊列。

思路：
使用兩個棧stackin和stackout分別進行入隊和出隊。
出隊時，如果stackout為空，將stackin 倒入 stackout。

class MyQueue:def __init__(self):self.stackin  = []self.stackout = []def push(self, x: int) -> None:self.stackin.append(x)def pop(self) -> int:if self.empty():return Noneif not self.stackout:while self.stackin:self.stackout.append(self.stackin.pop())return self.stackout.pop()def peek(self) -> int:res = self.pop()self.stackout.append(res)return resdef empty(self) -> bool:return not (self.stackin or self.stackout)

225. 用隊列實現(xiàn)棧

#模擬

重點還是pop。使用隊列彈出元素時，需要先把之前的n-1個元素彈出，才能彈出第n個元素。
所以這里先彈出n-1個元素并添加到隊列末尾，然后第n個元素就到了隊列的開頭。

這題沒法仿照232的思路。注意隊列和棧的區(qū)別，棧是反轉(zhuǎn)元素進出順序的，兩次反轉(zhuǎn)則變?yōu)橄冗M先出。而隊列是保持順序的，進出兩次隊列后順序不變。

class MyStack:def __init__(self):self.que = deque()def push(self, x: int) -> None:self.que.append(x)def pop(self) -> int:if self.empty():return Nonefor i in range(len(self.que)-1):self.que.append(self.que.popleft())return self.que.popleft()def top(self) -> int:if self.empty():return Nonereturn self.que[-1]def empty(self) -> bool:return not self.que

20. 有效的括號

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

棧的應(yīng)用，使用棧來存儲左括號，遇到右括號則彈出左括號進行匹配。

class Solution:def isValid(self, s: str) -> bool:stack = []d_k = {'(': ')', '{': '}', '[': ']'}for c in s:if c in  d_k.keys():stack.append(c)else:if len(stack) == 0:return Falseleft = stack.pop()if c != d_k[left]:return Falsereturn  len(stack) == 0

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

刪除字符串的相鄰重復(fù)字母，可以重復(fù)多次，直到?jīng)]有沒有相鄰重復(fù)項。

#模擬 #棧

class Solution:def removeDuplicates(self, s: str) -> str:stack = []for c in s:if len(stack) > 0 and stack[-1] == c:stack.pop()else:stack.append(c)return "".join(stack)

150. 逆波蘭表達式求值

#棧
逆波蘭表達式又叫后綴表達式，運算符在操作數(shù)的后面，如：1 2 +
我們一般寫的是中綴表達式，運算符在操作數(shù)的中間，如 ： 1 + 2
輸入： tokens = [“2”,“1”,“+”,“3”,“*”]
輸出： 9
解釋： 該算式轉(zhuǎn)化為常見的中綴算術(shù)表達式為：((2 + 1) * 3) = 9

借助棧，比較容易計算后綴表達式，遇到操作數(shù)就入棧，遇到運算符就彈出前面兩個數(shù)，然后計算，并將計算結(jié)果入棧。

class Solution:def evalRPN(self, tokens: List[str]) -> int:stack = []res = 0for i in tokens:if i == '+' :a = stack.pop()b = stack.pop()stack.append(b+a)elif i == '-' :a = stack.pop()b = stack.pop()stack.append(b-a)elif i == '*' :a = stack.pop()b = stack.pop()stack.append(b*a)elif i == '/':a = stack.pop()b = stack.pop()stack.append(int(b/a))else :stack.append(int(i))return int(stack[-1])

看起來有點重復(fù)，可以簡化一下：

class Solution:def evalRPN(self, tokens: List[str]) -> int:stack = []res = 0op_map = {'+': add, '-': sub, '*': mul, '/': lambda x, y: int(x / y)}for i in tokens:if i in op_map.keys():a = stack.pop() # 后b = stack.pop() # 前stack.append(op_map[i](b,a)) # 注意順序 b op aelse :stack.append(int(i))return int(stack[-1])

239. 滑動窗口最大值

#單調(diào)隊列 #隊列
整體思路：希望有一個隊列，在滑動窗口的時候，用push添加新的元素，用pop彈出被刪除的元素，并且能直接獲取隊列的最大元素。
也就是說，我們希望實現(xiàn)一個隊列存儲可能成為窗口中最大值的元素。（稱為單調(diào)隊列）

1. 為了方便添加和刪除元素，使用雙端隊列存儲數(shù)據(jù)。
   self.queue = deque()
2. 添加操作 push： 添加元素value時，如果隊列末尾比value小，就pop掉，然后添加value。（也就意味著，隊列中的元素都比新加入的value大。push操作很關(guān)鍵，保證了隊列中的元素是單調(diào)遞減的，因此后面可以用self.queue[0]獲取最大值）

def push(self, value):while self.queue and value > self.queue[-1]:# 隊列末尾比value小則刪除self.queue.pop() # pop，彈出隊列末尾元素self.queue.append(value)

3. 刪除操作 pop：刪除元素value時，如果value等于隊首元素que[0]，則彈出隊首popleft()。

def pop(self, value):if self.queue and value == self.queue[0]:self.queue.popleft() # 彈出隊首元素

獲取最大值：

def front(self):return self.queue[0]

使用單調(diào)隊列來解決滑動窗口最大值就比較簡單了，不斷地調(diào)用pop和push和 front。

class MyQueue:def __init__(self):self.queue = deque()# 刪除value ，如果value 在隊首則刪除def pop(self, value):if self.queue and value == self.queue[0]:self.queue.popleft()# 添加value， valuea前面的比value小的都刪除def push(self, value):while self.queue and value > self.queue[-1]:self.queue.pop()self.queue.append(value)def front(self):return self.queue[0]class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:que = MyQueue()res = []for i in range(k):que.push(nums[i])res.append(que.front())for i in range(k, len(nums)):que.pop(nums[i-k])que.push(nums[i])res.append(que.front())return res

347.前 K 個高頻元素

#優(yōu)先級隊列 #堆
給你一個整數(shù)數(shù)組?nums?和一個整數(shù)?k?，請你返回其中出現(xiàn)頻率前?k?高的元素。

最容易想到的是用字典統(tǒng)計頻率然后排序。

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:mmap =  Counter(nums)sort = sorted(zip(mmap.values(),mmap.keys()), reverse=True)res = []for i in range(k):res.append(sort[i][1])return res

用堆排序，我們只需要維護一個大小為k的堆（優(yōu)先級隊列）。
在Python中可以用heapq或queue.PriorityQueue 實現(xiàn)。
heapq — 堆隊列算法 — Python 3.11.5 文檔
queue — 一個同步的隊列類 — Python 3.11.5 文檔

使用heapq

import heapq
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:#要統(tǒng)計元素出現(xiàn)頻率map_ = Counter(nums)#對頻率排序#定義一個小頂堆，大小為kpri_que = [] #小頂堆#用固定大小為k的小頂堆，掃描所有頻率的數(shù)值for key, freq in map_.items():heapq.heappush(pri_que, (freq, key))if len(pri_que) > k: #如果堆的大小大于了K，則隊列彈出，保證堆的大小一直為kheapq.heappop(pri_que)#找出前K個高頻元素，因為小頂堆先彈出的是最小的，所以倒序來輸出到數(shù)組result = [0] * kfor i in range(k-1, -1, -1):result[i] = heapq.heappop(pri_que)[1]return result

使用PriorityQueue

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:#要統(tǒng)計元素出現(xiàn)頻率map_ = Counter(nums)#對頻率排序from queue import PriorityQueue as PQpri_que = PQ(k+1) #優(yōu)先級隊列(相當于小根堆)， 最多放k+1個元素#用固定大小為k的小頂堆，掃描所有頻率的數(shù)值for key, freq in map_.items():pri_que.put((freq, key))if pri_que.qsize() > k:pri_que.get()print(pri_que.queue)#找出前K個高頻元素，因為小頂堆先彈出的是最小的，所以倒序來輸出到數(shù)組result = [0] * kfor i in range(k-1, -1, -1):result[i] = pri_que.get()[1]return result

棧和隊列小結(jié)

棧主要用來處理相鄰匹配問題，隊列可以處理滑動窗口的最值問題（單調(diào)隊列，前k個最值問題（優(yōu)先級隊列/小根堆）。

python中?？梢杂胠ist實現(xiàn)，隊列用colelctions.deque實現(xiàn)。

stack = [3, 4, 5]
stack.append(6)
stack.append(7)
stack.pop()

import collections
queue = collections.deque()
queue.append(1) # 入隊
queue.append(2)
queue.popleft() # 出隊

此外還用到了優(yōu)先級隊列（堆），默認實現(xiàn)的是小根堆（堆頂元素最小）。

import heapq
pri_que = [] #小頂堆
heapq.heappush(pri_que, 1) # 入隊
heapq.heappush(pri_que, 2)
heapq.heappop(pri_que) # 出隊