leetcode-Queue

队列

用队列表栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class MyStack:
    def __init__(self):
        self.query_in = deque()
        self.query_out = deque()
        
    def empty(self)-> bool:
        return not self.query_in
        
   	def push(self, num:int)-> None:
        self.query_in.append(num)
        
    def pop(self)-> None:
        if self.empty():
            return None
        n = len(self.query_in())
  
        for i in range(0:n-1):
        # 清空前 i-1 位置的self.query_in，只留下最后一个需要弹出的 i 在self.query_in中
            self.query_out.append(self.query_in.popleft())
        # 交换in和out，此时out中只有一个需要弹出的i
        self.query_out, self,query_in = self.query_in, self.query_out
        return self.query_out.popleft()
    
   	def top(self)-> int:
        if self.empty():
            return None
       	return self.query_in[-1]

单调队列

单调队列：队列中元素之间的关系具有单调性，而且队首和队尾都可以进行出队操作，只有队尾可以进行入队操作。

单调队列和单调栈的区别:

  1. 队列可以从队列头弹出元素，可以方便地根据入队的时间顺序（访问的顺序）删除元素。这样导致了单调队列和单调栈维护的区间不同。

  2. 当访问到第i个元素时，单调栈维护的区间为[0, i)，而单调队列维护的区间为(lastpop, i)

  3. 单调队列可以访问“头部”和“尾部”，而单调栈只能访问栈顶（也就是“尾部”）。这导致单调栈无法获取[0, i)的区间最大值/最小值。

综上所述，单调队列实际上是单调栈的的升级版。单调栈只支持访问尾部，而单调队列两端都可以

算法流程：
初始化： 双端队列 deque ，结果列表 res ，数组长度 n ；
滑动窗口： 左边界范围 i∈[1−k,n−k] ，右边界范围 j∈[0,n−1] ；
若 i>0 且 队首元素 deque[0] = 被删除元素 nums[i−1] ：则队首元素出队；
删除 deque 内所有 <nums[j] 的元素，以保持 deque 递减；
将 nums[j] 添加至 deque 尾部；
若已形成窗口（即 i≥0 ）：将窗口最大值（即队首元素 deque[0] ）添加至列表 res ；
返回值： 返回结果列表 res ；

1
2
3
4
# importing "collections" for deque operations
import collections import deque

queue = deque()