栈和队列
LeetCode栈和队列刷题记录
基础知识
栈
线性表，只允许在表的一段进行插入和删除操作，满足先进后出原则
栈在python中没有特定的类或库函数，一般通过列表（list）或是collections.deque双端队列来实现
- list
stack = []
stack.append(1) # 压栈
stack.append(2)
print(stack.pop()) # 弹出栈顶元素，输出 2
print(stack.pop()) # 输出 1
- collections.deque
from collections import deque
stack = deque()
stack.append(1) # 压栈
stack.append(2)
print(stack.pop()) # 弹出栈顶元素，输出 2
print(stack.pop()) # 输出 1
存储方式
- 顺序存储：连续地址存放从栈底到栈顶的元素，指针指示栈顶位置
- 链式存储：链表存储栈，每次插入节点都是插入到头节点的位置，指针指向头节点
应用
括号匹配
思考一下，哪几种情况下括号不匹配：
- 左括号多了
"(({[]})" - 右括号多了
"[{}]))" - 括号类型不匹配
"[{(})]"
遇到左括号，就把匹配的右括号压入栈中
- 遇到右括号，就从栈里面弹出元素，如果此时栈是空的，没有元素，说明不匹配 — 对应“右括号多了”这种情况
- 进行比较，如果相等匹配，如果括号类型不相等不匹配 — 对应“括号类型不匹配”这种情况
- 最后如果栈是空的，匹配成功，如果栈还有元素，匹配不成功 — 对应“左括号多了”这种情况
class Solution:
def isValid(self, s: str) -> bool:
stack = []
top = -1
pair = {')':'(', '}':'{',']':'['} # 用来化简重复代码
if len(s) % 2 != 0:
return False
for string in s:
if string in pair:
# 遇到右括号，出栈匹配
if top != -1 and pair[string] == stack[top]:
top -= 1
stack.pop()
else:
# 不匹配
return False
else:
# 遇到左括号，入栈
stack.append(string)
top += 1
if top == -1:
return True
return False
表达式求值
- 思路：表达式求值关键是顺序问题，加减乘除中乘除的优先级是最高的，所以可以把待加减的数现存如栈中，最后一并运算，当遇到乘除的时候直接计算出来。乘除的两个元素，前一个是栈顶元素，后一个是遍历过程中后一位的元素
- 如何处理多位数：如
'100/5'这种情况，我们并不知道除数和被除数到底有几位，所以需要单独记录，当碰到非数字的字符的时候，说明数字部分结束，前面的所有数字字符构成一个完整的数字’abc’ = a × 100 + b × 10 + c a \times 100 + b \times 10 + c a×100+b×10+c当然也可以用int()函数直接转换 - 如何处理第一位数：别的数加入数组的时候，可以根据前面的符号是正号还是负号来判断加入
numor-num但是第一位前面没有符号，可以为默认为正号
def calculate(self, s: str) -> int:
stack = []
top = -1
op = '+'
i = 0
while i < len(s):
num = ''
while i < len(s) and s[i] >= '0' and s[i] <= '9':
num += s[i]
i += 1
# 因为计算操作需要两个数字，一个是运算符前面的，一个运算符后面的
# 此处的num必须是后面的数字，前面的数字存储在栈中
print(num)
if op == '+' and num != '':
stack.append(int(num))
top += 1
elif op == '-' and num != '':
stack.append(-int(num))
top += 1
elif op == '*' and num != '':
stack[top] = stack[top] * int(num)
elif op == '/' and num != '':
stack[top] = int(stack[top] / int(num))
if i < len(s) and s[i] in "+-*/":
op = s[i]
# 记录下一次的operator
i += 1
return sum(stack)
注意：除法实现的时候需要int(stack[top] / int(num))而不是stack[top] // int(num)，后者再做负数除法的时候会有问题，因为//在python中为向下取整$ -3 // 2 = -2$，而int()函数是直接舍去小数部分int(-1.7) = -1
单调栈
在栈的基础性质上再加上要求从栈顶到栈底的元素是单调的
应用： 寻找一个数组中，左侧第一个比当前元素大的元素
- 建立一个从栈顶到栈底单调递增的栈
- 从左往右遍历栈，当前元素入栈时的栈顶元素就是左侧第一个比当前元素大的元素
e.g 假设数组为 [2, 1, 4, 3, 5]，我们需要找到每个元素左侧第一个比它大的元素
-
初始化：栈：
[]结果：[] -
处理元素
2：栈为空，左侧没有比2大的元素。结果：[-1]栈：[2] -
处理元素
1： 栈顶元素2比1大，所以2是1左侧第一个比它大的元素。结果：[-1, 2]栈：[2, 1] -
处理元素
4：栈顶元素1比4小，弹出1。栈顶元素2比4小，弹出2。栈为空，左侧没有比4大的元素。结果：[-1, 2, -1]栈：[4] -
处理元素
3： 栈顶元素4比3大，所以4是3左侧第一个比它大的元素。结果：[-1, 2, -1, 4]栈：[4, 3] -
处理元素
5：栈顶元素3比5小，弹出3。栈顶元素4比5小，弹出4。栈为空，左侧没有比5大的元素。结果：[-1, 2, -1, 4, -1]栈：[5]
def find_left_first_greater(nums):
stack = []
result = []
for i in range(len(nums)):
while stack and nums[i] >= stack[-1]:
# 到可以入栈了为止
stack.pop()
if stack:
result.append(stack[-1])
else:
result.append(-1)
stack.append(nums[i])
return result
应用： 寻找一个数组中，右侧第一个比当前元素大的元素
- 第一种想法就是基于同样的原则，不过从右边开始遍历
- 第二种想法，一样从左边开始遍历，建立从栈顶到栈底单调递增的栈，当前元素出栈时，等待压入栈的元素就是右侧第一个比当前元素大的元素
e.g 假设数组为 [2, 1, 4, 3, 5]，我们需要找到每个元素右侧第一个比它大的元素
-
初始化：栈：
[]结果：[-1, -1, -1, -1, -1]（初始化为-1） -
处理元素
2：栈为空，直接入栈。栈：[2] -
处理元素
1：栈顶元素2比1大，直接入栈。栈：[2, 1] -
处理元素
4：栈顶元素1比4小，弹出1，并记录1的右侧第一个更大元素是4。结果更新为：[-1, 4, -1, -1, -1]。栈顶元素2比4小，弹出2，并记录2的右侧第一个更大元素是4。结果更新为：[4, 4, -1, -1, -1]栈为空，将4入栈。栈：[4] -
处理元素
3：栈顶元素4比3大，直接入栈。栈：[4, 3] -
处理元素
5：栈顶元素3比5小，弹出3，并记录3的右侧第一个更大元素是5。结果更新为：[4, 4, -1, 5, -1]。栈顶元素4比5小，弹出4，并记录4的右侧第一个更大元素是5。结果更新为：[4, 4, 5, 5, -1]栈为空，将5入栈。栈：[5]
def find_right_first_greater(nums):
stack = []
result = [-1] * len(nums)
for i in range(len(nums)):
# 入栈的是索引，因为需要知道存到result的第几个位置
while stack and nums[i] > nums[stack[-1]]:
result[stack.pop()] = nums[i]
stack.append(i)
return result
题1:下一个更大的元素
nums1 数组中数字 x x x的下一个更大元素，是指 x x x在 nums2中对应位置右侧的第一个比 x x x大的元素
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
## 遍历数组nums2，做两件事
## 1.算出每个位置右侧比x大的第一个元素
## 2.建立一个字典（哈希表），方便查询
index = [-1] * len(nums2)
stack = []
dic = {}
for i in range(len(nums2)):
while stack and nums2[stack[-1]] <= nums2[i]:
index[stack.pop()] = nums2[i]
stack.append(i)
dic[nums2[i]] = i
result = []
## 遍历nums1数组
for i in range(len(nums1)):
result.append(index[dic[nums1[i]]])
return result
利用单调栈和哈希表来化简算法时间复杂度 O ( n 1 + n 2 ) O(n_1 + n_2) O(n1+n2)
题2:每日温度
给定一个整数数组temperatures，表示每天的温度，返回一个数组answer ，其中answer[i]是指对于第
i
i
i天，下一个更高温度出现在几天后，如果气温在这之后都不会升高，请在该位置用 0 来代替
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
result = [0] * len(temperatures)
stack = []
for i in range(len(temperatures)):
while stack and temperatures[stack[-1]] < temperatures[i]:
result[stack.pop()] = i - stack[-1]
stack.append(i)
return result
队列
线性表，只允许在表的一端进行插入操作，在表的另一端进行删除操作，先进先出
存储方式
- 顺序存储：存储在地址连续的单元中，
front指针指向队头元素，rear指针指向队尾元素 - 链式存储：用链表存储，
front指针指向头指针，rear指针指向链表的尾部，每次在链表的尾部插入新的节点，每次在头部删除节点 O ( 1 ) O(1) O(1)
优先队列
在优先队列中，元素被赋予优先级，当访问队列元素时，具有最高优先级的元素最先删除，优先队列的出队顺序和入队顺序无关，和优先级有关
python可以通过heapq来实现优先队列
存储方式
- 数组：出队的时候要遍历队列，寻找优先级最高的元素 出队 O ( n ) O(n) O(n) 入队 O ( 1 ) O(1) O(1)
- 链表：存储的时候直接按照优先级存储，入队要寻找合适位置插入 O ( n ) O(n) O(n) 出队 O ( 1 ) O(1) O(1) 这两种存储方式在入队和出队中必有一者效率较低
- 二叉堆：插入元素的时候，从堆的最末尾开始上浮
heapify，直到满足堆的性质 O ( log n ) O(\log n) O(logn)，出队，删除第一个元素（最大堆），将最后一个元素移动到堆顶，然后从堆顶开始下沉，直到满足堆的性质 O ( log n ) O(\log n) O(logn)
手写堆实现优先队列
class PriorityQueue:
def __init__(self):
self.heap = [] # 用数组存储二叉堆
def is_empty(self):
return len(self.heap) == 0
def get(self):
if self.is_empty():
raise Exception("Heap is empty")
return self.heap[0] #返回优先级最高的元素，不出队
def push(self, value):
self.heap.append(value) # 将新元素插入数组末尾
self._sift_up(len(self.heap) - 1) # 从新插入的元素开始上浮调整
def pop(self):
if self.is_empty():
raise Exception("Queue is empty")
self._swap(0, len(self.heap) - 1)
value = self.heap.pop() # 删除堆顶元素
self._sift_down(0) # 从堆顶开始下沉调整
return value
def _sift_up(self, index):
while index > 0:
parent = (index - 1) // 2
if self.heap[index] > self.heap[parent]:
self._swap(index, parent) # 交换节点
index = parent # 继续向上调整
else:
break
def _sift_down(self, index):
n = len(self.heap)
while index < n:
left = index * 2 + 1
right = index * 2 + 2
large = index
if left < n and self.heap[left] > self.heap[large]:
large = left
if right < n and self.heap[right] > self.heap[large]:
large = right
if large != index:
self._swap(large, index)
index = large
else:
# 不交换说明已经完成shift down了
break
def _swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
使用python模块heapq来实现优先队列
import heapq
class PriorityQueue:
def __init__(self):
self.queue = []
self.index = 0
def push(self, item, priority):
heapq.heappush(self.queue, (-priority, self.index, item))
# `heappop`会优先返回优先级最小的元素（从小到大的堆排序）
# 所以把优先级取相反数可以达到返回优先级最大元素的效果
# self.index 是用来处理优先级相同的时候的排序问题
self.index += 1
def pop(self):
return heapq.heappop(self.queue)[-1]
应用1：滑动窗口最大值
class Solution:
import heapq
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
# 优先队列，每个数的值最为priority
q = [(-nums[i], i) for i in range(k)]
heapq.heapify(q)
result = [-q[0][0]]
for i in range(k,len(nums)):
# 依次添加元素
heapq.heappush(q,(-nums[i],i))
while q[0][1] <= i - k:
heapq.heappop(q)
result.append(-q[0][0])
return result
这种算法的时间复杂度是
O
(
n
log
n
)
O(n\log n)
O(nlogn)，如果nums数组的元素单调递增，那么每次返回的都是第一个元素，但是所有元素都要加入优先队列（堆），push的复杂度是
O
(
log
m
)
O(\log m)
O(logm)，
m
m
m为当前队列长度，总复杂度是
O
(
log
k
+
log
(
k
+
1
)
+
⋯
+
log
n
)
=
O
(
n
log
n
)
O(\log k + \log (k+1) + \cdots + \log n) = O(n \log n)
O(logk+log(k+1)+⋯+logn)=O(nlogn)
可以进一步改进
队列中有一些元素是不必要的，可以删除，当nums[i]和nums[j]都在队列里，nums[i] < nums[j] 并且
i
<
j
i < j
i<j的时候，说明nums[i]可以直接被删除，它不可能被作为当前滑动窗口最大的元素，因为nums[j]比它大，当滑动窗口不断向右移动的时候，只要i还在范围内j一定还在范围内（类似于数学上的帕累托最优
j
j
j比
i
i
i优）
基于这种想法，在我们的队列里可以只存有可能作为最大值的元素，当 i < j i < j i<j的时候，一定有 n u m s [ i ] > n u m s [ j ] nums[i] > nums[j] nums[i]>nums[j]，不然 n u m s [ i ] nums[i] nums[i]会被淘汰掉，所以当我们以降序排序数组数值的时候，数组元素的下标索引一定是升序排序
class Solution:
from collections import deque
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = deque() #直接调用python的库函数实现双端队列
# 前k个数先建立一个符合要求的队列
# q存储在nums中的索引，索引是升序的
for j in range(k):
while q and nums[q[-1]] <= nums[j]:
# 发生i < j and nums[i] <= nums[j]的情况
# nums[i]不需要存在队列中了
q.pop() #右端删除
q.append(j)
result = [nums[q[0]]]
for j in range(k,len(nums)):
# 加入新元素
while q and nums[q[-1]] <= nums[j]:
q.pop()
q.append(j)
while q[0] <= j - k:
# 不在滑动窗口的范围内
q.popleft()
result.append(nums[q[0]])
return result
进一步化简，单调队列里面存的是索引，但其实还可以更简单一点，直接存值，那么当滑动窗口向后移动的时候，怎么判断队列里面的元素是否还在? 一个元素被pop，有两种情况
- 后续来的元素 n u m s [ j ] > n u m s [ i ] nums[j] > nums[i] nums[j]>nums[i] and j > i j > i j>i那么在 n u m s [ j ] nums[j] nums[j]被加入队列的时候， n u m s [ i ] nums[i] nums[i]就已经被弹出队列了
- 后续一直没有来比 n u m s [ i ] nums[i] nums[i]更大的元素，但是 i ≤ j − k i \leq j - k i≤j−k不在滑动窗口的范围内，需要弹出，对于这种情况，直接判断 q [ 0 ] = = n u m s [ j − k ] q[0] == nums[j-k] q[0]==nums[j−k]
class Solution:
from collections import deque
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = deque() #直接调用python的库函数实现双端队列
result = []
for j in range(len(nums)):
while q and q[-1] < nums[j]:
q.pop()
q.append(nums[j])
if j>=k and q[0] == nums[j-k]:
q.popleft()
if j >= k-1:
result.append(q[0])
return result
要注意q[-1] < nums[j]不能写等于号，如果有等于，那么nums里如果有相同的元素，会把之前弹出，加入这个相同的元素，正好是两个区间的最大值，那么后一个区间的最大值会发生变化
应用2:前k个高频元素
给一个整数数组nums和一个整数
k
k
k，请返回其中出现频率前
k
k
k高的元素
思路挺简单的，就是先统计后排序。一般的排序算法的时间复杂最少为 O ( n log n ) O(n \log n) O(nlogn)，但是仔细思考发现我们并不需要 k k k位之后的数据，可以利用只需要前 k k k这一点建立一个优先队列来化简排序过程。每次最先出栈最小的元素，所以使用小顶堆
class Solution:
from collections import defaultdict
def shiftup(self, heap:List[tuple], index:int) -> List:
while index > 0:
parent = (index - 1) //2
if heap[index][1] < heap[parent][1]:
heap[index], heap[parent] = heap[parent], heap[index]
index = parent
else:
break
return heap
def shiftdown(self, heap:List[tuple], index:int) -> List:
n = len(heap)
while index < n:
left = index * 2 + 1
right = index * 2 + 2
minid = index
if left < n and heap[left][1] < heap[minid][1]:
minid = left
if right < n and heap[right][1] < heap[minid][1]:
minid = right
if minid != index:
heap[index],heap[minid] = heap[minid], heap[index]
index = minid
else:
break
return heap
def push(self, heap:List[tuple], num:tuple) -> List:
heap.append(num)
return self.shiftup(heap,len(heap) - 1)
def pop(self,heap:List[tuple]) -> List:
heap[0],heap[-1] = heap[-1], heap[0]
heap.pop()
return self.shiftdown(heap,0)
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# 统计频率
dic = defaultdict(int)
for num in nums:
dic[num] += 1
minheap = []
for key,item in dic.items():
if len(minheap) < k:
# 堆没有满
self.push(minheap,(key,item))
elif item > minheap[0][1]:
# 当前元素大于堆顶元素
# 弹出堆顶，当前元素加入堆
self.pop(minheap)
self.push(minheap,(key,item))
result = []
for num in minheap:
result.append(num[0])
return result
题1:用栈实现队列
请仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）
class MyQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, x: int) -> None:
self.stack1.append(x)
def pop(self) -> int:
if self.empty():
return None
if len(self.stack2) == 0:
# 如果输出栈为空
# 那么把输入栈全部存储到输出栈中
for i in range(len(self.stack1)):
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
def peek(self) -> int:
if len(self.stack2) == 0:
# 如果输出栈为空
# 那么把输入栈全部存储到输出栈中
for i in range(len(self.stack1)):
self.stack2.append(self.stack1.pop())
return self.stack2[-1]
def empty(self) -> bool:
return len(self.stack1) == 0 and len(self.stack2) == 0
出队入队的算法效率是 O ( 1 ) O(1) O(1) 不是 O ( n ) O(n) O(n) 一个循环 n n n会被使用 n n n次，因为这 n n n个加入到出栈的元素，会一次输出，最后还是O(1)
peek可以做代码复用
def peek(self) -> int:
# 代码复用
# 先弹出，再放回
result = self.pop()
self.stack2.append(result) # 放回stackout的栈顶
# 注意不是push，不然从队头出来加入到队尾去了
return result
题2:用队列实现栈
不同于用栈来实现队列，两个栈是用于反转数据的顺序，但是用队列来实现栈，两个队列仅仅是起到备份数据的作用，队列是先进先出，叠加再多的队列，也无法实现改变数据输入输出流的方向（就好像负负得正，但是正正不可能得负一样）
class MyStack:
from collections import deque
def __init__(self):
self.queue1 = deque()
self.queue2 = deque()
# 互相用于备份数据
def push(self, x: int) -> None:
if len(self.queue2) != 0:
self.queue2.append(x)
else:
self.queue1.append(x)
def pop(self) -> int:
if self.empty():
return None
if len(self.queue1) == 0:
#数据都在self.deque2里面
for i in range(len(self.queue2)-1):
self.queue1.append(self.queue2.popleft())
return self.queue2.popleft()
if len(self.queue2) == 0:
for i in range(len(self.queue1)-1):
self.queue2.append(self.queue1.popleft())
return self.queue1.popleft()
def top(self) -> int:
result = self.pop()
self.push(result)
return result
def empty(self) -> bool:
return len(self.queue1) == 0 and len(self.queue2) == 0
可以用一个队列实现栈，每次pop的时候，元素依次出队后入队，直到最后一个元素，输出最后一个元素，即实现栈的操作，时间复杂度为 O ( n ) O(n) O(n)
class MyStack:
from collections import deque
def __init__(self):
self.queue = deque()
def push(self, x: int) -> None:
self.queue.append(x)
def pop(self) -> int:
if self.empty():
return None
count = len(self.queue) - 1 # 弹出次数
while count != 0:
self.push(self.queue.popleft())
count -= 1
return self.queue.popleft()
def top(self) -> int:
# 先出栈后入栈，栈顶元素还是在栈顶
result = self.pop()
self.push(result)
return result
def empty(self) -> bool:
return len(self.queue) == 0
题3:删除字符串中的所有相邻重复项
规则：消消乐，注意题设，重复想删除会选择两个相邻且相同的字母，但不是把所有相邻且相同的全删了
关键在于要想到用栈这种数据结构来处理
class Solution:
def removeDuplicates(self, s: str) -> str:
stack = []
for letter in s:
if stack and stack[-1] == letter:
stack.pop()
else:
stack.append(letter)
return ''.join(stack)
一开始没想到栈，用了双指针
class Solution:
def removeDuplicates(self, s: str) -> str:
lit = list(s)
left , right = 0, 0
while right < len(s):
if right < len(s) - 1 and lit[right] == lit[right+1]:
right += 2
if right >= len(s):
break
lit[left] = lit[right]
if left > 0 and lit[left] == lit[left-1]:
left -= 2
left += 1
right += 1
return ''.join(lit[0:left])
题3:逆波兰表达式求值
数字消消乐，一旦碰到运算符就"消除" 逆波兰表达式本身完美符合栈的性质，遇到运算符就出栈，第一个弹出的是第二个算子，把运算结果再次入栈
逆波兰表达式相当于二叉树中的后序遍历
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
lit = []
for op in tokens:
if op == '+':
num1 = lit.pop()
num2 = lit.pop()
lit.append(num2+num1)
elif op == '-':
num1 = lit.pop()
num2 = lit.pop()
lit.append(num2-num1)
elif op == '*':
num1 = lit.pop()
num2 = lit.pop()
lit.append(num2*num1)
elif op == '/':
num1 = lit.pop()
num2 = lit.pop()
lit.append(int(num2/num1))
else:
lit.append(int(op))
return lit[0]
总结
