基础

stl中栈和队列不是容器，而是容器适配器。它们提供接口，由其他容器实现。

20. 有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()” 输出：true
示例 2：

输入：s = “()[]{}” 输出：true
示例 3：

输入：s = “(]” 输出：false
示例 4：

输入：s = “([)]” 输出：false
示例 5：

输入：s = “{[]}” 输出：true

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。

tips：在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！

class Solution:def isValid(self, s: str) -> bool:stack = []for x in s:if x == '(':stack.append(')')elif x == '[':stack.append(']') elif x == '{':stack.append('}') # 当前元素与栈顶元素不符合 或者 栈已空s却没遍历完 说明多了右括号 # 先要判断栈空不空 空了再去判断栈顶元素满不满足 否则栈空时 -1会越界elif not stack or x!=stack[-1]:return False# 如果遇到右括号 弹出栈顶元素else:stack.pop()# 遍历完后 如果栈为空成功 栈不空失败if stack==[]:return Trueelse:return False 

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入： [“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”] [[], [1], [2],
[], [], []]
输出： [null, null, null, 1, 1, false]

解释： MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

class MyQueue:def __init__(self):"""in主要负责push，out主要负责pop"""self.stack_in = []self.stack_out = []def push(self, x: int) -> None:# 有新元素就进来 放在inself.stack_in.append(x)def pop(self) -> int:if self.empty():return None# 如果出栈不空 直接pop 如果为空就先将入栈的所有元素移动到出栈if self.stack_out:return self.stack_out.pop()else:for i in range(len(self.stack_in)):self.stack_out.append(self.stack_in.pop())return self.stack_out.pop()def peek(self) -> int:# 只需要返回第一个元素 所有pop后还要加回来ans=self.pop()self.stack_out.append(ans)return ansdef empty(self) -> bool:"""只要in或者out有元素，说明队列不为空"""return not(self.stack_in or self.stack_out)# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入： [“MyStack”, “push”, “push”, “top”, “pop”, “empty”] [[], [1], [2],
[], [], []] 输出： [null, null, null, 2, 2, false]

解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2);
myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回
False

用两个队列que1和que2实现队列（先进先出）的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

优化
其实这道题目就是用一个队列就够了。

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。

class MyStack:def __init__(self):"""Python普通的Queue或SimpleQueue没有类似于peek的功能也无法用索引访问，在实现top的时候较为困难。用list可以，但是在使用pop(0)的时候时间复杂度为O(n)因此这里使用双向队列，我们保证只执行popleft()和append()，因为deque可以用索引访问，可以实现和peek相似的功能in - 存所有数据out - 仅在pop的时候会用到"""self.queue_in =deque()self.queue_out = deque()def push(self, x: int) -> None:self.queue_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()的时候两个进行交换例子:old_in： 1 2 3 4out： 1 2 3new_in： 4交换out 和 new_in然后弹出4 实现后进先出"""if self.empty():return Nonefor i in range(len(self.queue_in)-1):self.queue_out.append(self.queue_in.popleft())# 交换in和outself.queue_in,self.queue_out = self.queue_out,self.queue_inreturn self.queue_out.popleft()def top(self) -> int:"""1. 首先确认不空2. 我们仅有in会存放数据，所以返回第一个即可"""if self.empty():return Nonereturn self.queue_in[-1]def empty(self) -> bool:"""因为只有in存了数据，只要判断in是不是有数即可"""return len(self.queue_in) == 0# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入：“abbaca” 输出：“ca” 解释： 例如，在 “abbaca” 中，我们可以删除 “bb”
由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa”
可以执行重复项删除操作，所以最后的字符串为 “ca”。

class Solution:def removeDuplicates(self, s: str) -> str:res = list()# 相当于括号匹配'''"abbaca"遇到ab 添加 res=[a,b]遇到第二个b时候 pop 弹出b'''for x in s:# 先确保栈不空 才有-1if res and res[-1] == x:res.pop()else:res.append(x)return ''.join(res)# 字符串拼接

150. 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = [“2”,“1”,“+”,“3”,“*”]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：

输入：tokens = [“4”,“13”,“5”,“/”,“+”]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：

输入：tokens = [“10”,“6”,“9”,“3”,“+”,“-11”,““,”/“,””,“17”,“+”,“5”,“+”]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

相邻字符串消除的过程，和1047.删除字符串中的所有相邻重复项 (opens new window)中的对对碰游戏是不是就非常像了。

class Solution:def evalRPN(self, tokens: List[str]) -> int:res=[]for i in range(len(tokens)):if tokens[i] =='+' or tokens[i] =='-' or tokens[i] =='*' or tokens[i] =='/' :num1=int(res.pop())num2=int(res.pop())if tokens[i] =='+':res.append(num1+num2)if tokens[i] =='-':res.append(num2-num1)if tokens[i] =='*':res.append(num1*num2)if tokens[i] =='/':res.append(int(num2 / num1))else:# 添加数字res.append(tokens[i])return int(res[-1])

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

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

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值

---

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

示例 2：

输入：nums = [1], k = 1 输出：[1]

思路
在上述滑动窗口形成及移动的过程中，我们注意到元素是从窗口的右侧进入的，然后由于窗口大小是固定的，因此多余的元素是从窗口左侧移除的。 一端进入，另一端移除，这不就是队列的性质吗？所以，该题目可以借助队列来求解。

• 遍历给定数组中的元素，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。直到，队列为空或当前考察元素小于新的队尾元素；

• 当队首元素的下标小于滑动窗口左侧边界left时，表示队首元素已经不再滑动窗口内，因此将其从队首移除。

• 由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时，意味着窗口形成。此时，队首元素就是该窗口内的最大值

题解参考：

class Solution:def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:left,right = 0,0n = len(nums)# 左头右尾deque=collections.deque()while right<k:if deque and deque[-1] < nums[right]:deque.pop()else:deque.append(nums[right])right += 1#窗口设置完成 dequeue为[ 3, -1]res = []res.append(deque[0]) while right < n:# 如果队列不空且当前元素大于队尾元素 将队尾元素移除 直到保持队列内递减次序# 即把队列内小于当前元素的值移除while deque and nums[right]>deque[-1]:deque.pop()# 加入当前元素deque.append(nums[right])# 判断队首元素下标是否 < left, 是说明队首不在窗口内，移除队首 队首元素是否在窗口中# 在python判断不了下标 所以等价于 如果left指向的值与队首元素相同 下一步left++ 则这个max就需要移除 不被包含在队列中#例如 1 3-1 -3 5 deque=[3 -1 -3] 此时left==1 3是max弹出if nums[left] == deque[0]:deque.popleft()left+=1res.append(deque[0])right +=1return res

 class Solution:def maxSlidingWindow(self, nums,k) :queue=[] #记录的是元素的索引值，对应的元素按照递减顺序ans=[]for index,value in enumerate(nums):print(index,value,nums,queue)#移除不在窗口中的元素 队首元素下标在left左边 说明不在窗口left = index-k+1while queue and queue[0]<left:queue.pop(0)#添加新元素 如果当前元素比队尾元素大 则移除队尾元素 直到满足队列元素递减while queue and nums[queue[-1]]<=value:queue.pop()queue.append(index)#选择最大值ans.append(nums[queue[0]])#ans [1, 3, 3, 3, 5, 5, 6, 7] 去除ansreturn ans[k-1:]

347.前 K 个高频元素

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:

输入: nums = [1], k = 1 输出: [1]

法一：用库

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:c = collections.Counter(nums)# Counter({1: 3, 2: 2, 3: 1})c = c.most_common(k)#C [(1, 3), (2, 2)]res=[]for x in c:# 添加keyres.append(x[0])return res

法二 优先队列
参考https://www.programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html

• 要统计元素出现频率
• 对频率排序
• 找出前K个高频元素
  因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢？

缺省情况下priority_queue利用max-heap（大顶堆）完成对元素的排序，这个大顶堆是以vector为表现形式的complete binary tree（完全二叉树）。

如果定义一个大小为k的大顶堆，在每次移动更新大顶堆的时候，每次弹出都把最大的元素弹出去了，那么怎么保留下来前K个高频元素呢。

我们要用小顶堆，因为要统计最大前k个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前k个最大元素。

 class Solution(object):def topKFrequent(self, nums, k):""":type nums: List[int]:type k: int:rtype: List[int]"""count = {}for x in nums:if x not in count:count[x] = 1else:count[x] += 1# 小顶堆 从小到大排序pri_que = []for key, freq in count.items():# 带权值排序 即按freq排序但带着keyheapq.heappush(pri_que, (freq, key))print(pri_que)if len(pri_que) > k:heapq.heappop(pri_que)result = [0] * k# 倒序输出 输出keyfor i in range(k - 1, -1, -1):print()result[i] = heapq.heappop(pri_que)[1]return result