双端队列
在普通队列的基础上，两端都可以进行入队和出队的队列
当然，更常见的情况是：
- 一端只能入队，另一端可以入队和出队
- 一端只能出队，另一端可以入队和出队
双端队列的应用——动态窗口最值问题
例1.直接上题：求滑动窗口最大值问题leetcode239
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。以list形式返回每一次滑动窗口中的最大值
例如：
输入: nums = [1,3,-1,-3,5,3,6,7] and k = 3
输出: [3,3,5,5,6,7]
这是动态窗口问题的模板例题，一定要熟烂于心阿同志们
思路：
- 首先，窗口滑动的过程显然 = 队列的出入队过程。因此，你的好友【队列】已上线准备解决这道题
- 本题的解决基于这样的性质：当前队列（窗口）即将发生元素ele的入队操作时，如果ele大于任何一个当前窗口内的元素，那么当前窗口内的所有元素【瞬间失效】，因为ele入队后会自己称王更新窗口的最大值=ele，直到它被踢出这个队列。因此，我们考虑维护一个双端不增队列deque：当任一元素e尝试入队时，检查队尾的元素，不断在队尾弹出小于e的元素，然后再将e入队，实现该双端队列内的元素单调不增；双端队列deque的队首元素就是当前窗口内的最大值
例如，我们将数字 1 3 2 5 4 依次纳入一个常规队列queue（窗口），过程如下：
queue #### deque
[1] #### [1]
[1,3] #### [1] -> 队尾的1比3小, 队尾弹出1得到[ ] -> 3入队得到[3]
[1,3,2] #### [3] -> 队尾的3比2大,2入队得到[3,2]
[1,3,2,5] #### [3,2] -> 队尾的3和2都比5小,全部在队尾弹出,5入队得到[5]
[1,3,2,5,4] #### [5] -> 队尾的5比4大,4入队得到[5,4]
本题借助双端队列的解法如下，维护一个不增的双端队列deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = list()
if nums:
# 初始化双端队列deque。头部只能出队，尾部可以出入队
deque = list()
for index in range(k):
while deque and deque[-1] < nums[index]:
deque.pop(-1)
deque.append(nums[index])
res.append(deque[0])
for index in range(k, len(nums)):
# 窗口最前元素出队，修改deque
if nums[index-k] == deque[0]:
deque.pop(0)
# 新元素入队
while deque and deque[-1] < nums[index]:
deque.pop(-1)
deque.append(nums[index])
# 更新res
res.append(deque[0])
return res
总结
对于常规队列，因为受到FIFO规则的约束，一端入队，另一端出队，队列内元素的顺序是死的
但双端队列不同，双端队列至少有一端可以实现出队和入队，因此，某种意义上看，deque = mix(stack, queue)
正是因为带上了栈的基因，双端队列可以根据需要来实现队内元素的某种顺序化
