栈和队列
栈和队列基础（Python）
栈一种先进后出，队列先进后出。
Python中可以用list实现栈，用append()模拟入栈，用pop()模拟出栈。
也可以用list实现队列，但是效率较低，一般用collections.deque模拟（双端）队列。
5. 数据结构 — 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.用栈实现队列
#模拟
请你仅使用两个栈实现先入先出队列。
思路：
使用两个栈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 None if 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 res def empty(self) -> bool: return not (self.stackin or self.stackout)
225. 用队列实现栈
#模拟
重点还是pop。使用队列弹出元素时，需要先把之前的n-1个元素弹出，才能弹出第n个元素。
所以这里先弹出n-1个元素并添加到队列末尾，然后第n个元素就到了队列的开头。
这题没法仿照232的思路。注意队列和栈的区别，栈是反转元素进出顺序的，两次反转则变为先进先出。而队列是保持顺序的，进出两次队列后顺序不变。
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 None for 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 None return self.que[-1] def empty(self) -> bool: return not self.que
20. 有效的括号
#栈
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串的括号是否有效。
栈的应用，使用栈来存储左括号，遇到右括号则弹出左括号进行匹配。
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 False left = stack.pop() if c != d_k[left]: return False return len(stack) == 0
1047. 删除字符串中的所有相邻重复项
删除字符串的相邻重复字母，可以重复多次，直到没有没有相邻重复项。
#模拟 #栈
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. 逆波兰表达式求值
#栈
逆波兰表达式又叫后缀表达式，运算符在操作数的后面，如：1 2 +
我们一般写的是中缀表达式，运算符在操作数的中间，如 ： 1 + 2
输入： tokens = [“2”,“1”,“+”,“3”,“*”]
输出： 9
解释： 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
借助栈，比较容易计算后缀表达式，遇到操作数就入栈，遇到运算符就弹出前面两个数，然后计算，并将计算结果入栈。
class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] res = 0 for 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])
看起来有点重复，可以简化一下：
class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] res = 0 op_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 a else : stack.append(int(i)) return int(stack[-1])
239. 滑动窗口最大值
#单调队列 #队列
整体思路：希望有一个队列，在滑动窗口的时候，用push添加新的元素，用pop弹出被删除的元素，并且能直接获取队列的最大元素。
也就是说，我们希望实现一个队列存储可能成为窗口中最大值的元素。（称为单调队列）
- 为了方便添加和删除元素，使用双端队列存储数据。
self.queue = deque()
- 添加操作 push： 添加元素value时，如果队列末尾比value小，就
pop掉，然后添加value。（也就意味着，队列中的元素都比新加入的value大。push操作很关键，保证了队列中的元素是单调递减的，因此后面可以用self.queue[0]获取最大值）
def push(self, value): while self.queue and value > self.queue[-1]:# 队列末尾比value小则删除 self.queue.pop() # pop，弹出队列末尾元素 self.queue.append(value)
- 删除操作 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]
使用单调队列来解决滑动窗口最大值就比较简单了，不断地调用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 个高频元素
#优先级队列 #堆
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。
最容易想到的是用字典统计频率然后排序。
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的堆（优先级队列）。
在Python中可以用heapq或queue.PriorityQueue 实现。
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]: #要统计元素出现频率 map_ = Counter(nums) #对频率排序 #定义一个小顶堆，大小为k pri_que = [] #小顶堆 #用固定大小为k的小顶堆，扫描所有频率的数值 for key, freq in map_.items(): heapq.heappush(pri_que, (freq, key)) if len(pri_que) > k: #如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k heapq.heappop(pri_que) #找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组 result = [0] * k for 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]: #要统计元素出现频率 map_ = Counter(nums) #对频率排序 from queue import PriorityQueue as PQ pri_que = PQ(k+1) #优先级队列(相当于小根堆)， 最多放k+1个元素 #用固定大小为k的小顶堆，扫描所有频率的数值 for key, freq in map_.items(): pri_que.put((freq, key)) if pri_que.qsize() > k: pri_que.get() print(pri_que.queue) #找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒序来输出到数组 result = [0] * k for i in range(k-1, -1, -1): result[i] = pri_que.get()[1] return result
栈和队列小结
栈主要用来处理相邻匹配问题，队列可以处理滑动窗口的最值问题（单调队列，前k个最值问题（优先级队列/小根堆）。
python中栈可以用list实现，队列用colelctions.deque实现。
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() # 出队
import heapq pri_que = [] #小顶堆 heapq.heappush(pri_que, 1) # 入队 heapq.heappush(pri_que, 2) heapq.heappop(pri_que) # 出队
