Queue

理论

• 支持操作：O(1) Push / O(1) Pop / O(1) Top
• 队列的基本作用就是用来做 BFS

应用：

• 1. 用来淘汰过期的
• 2. 单调Queue
• 3. 实现stack

Problems

1. 用来淘汰过期的\

933. Number of Recent Callswhile self.q and self.q[0] + 3000 < t:pop\

649. Dota2 Senate用queue来模拟senator投票排队，每次从左边pop出一个投票，若他没有被禁止，则可继续排到队尾继续参与投票；为了简化实行，用+-1代表双方阵营，ban=0或者q.popleft()*-1,当queue的长度等于abs(sum(queue))时，结束投票
1823. Find the Winner of the Circular Game循环queue, starting from i=0, 每次pop出index=(i-1+k)%len(q), 直至len(q)==1\

2. 单调Queue

• 超出范围的从左边出，新加入的放入右边，保持单调性（类似sliding window）

3. 实现stack

225. Implement Stack using Queues每次push如的元素置于队最左边（通过popleft出所有元素后再放入实现\

Deque

理论

应用：

• 1. 实现新加入+旧淘汰
• 2. 单调deque
• 3. 两个deque

Problems

1. 实现新加入+旧淘汰\

• 为了提高效率，deque中存pair (val, cnt)\

362. Design Hit Counter和933的不同在于，同一个timestamp可以hit多次，虽然仍旧可以用933的方式做，但为了节省空间时间，可以在deque中存（timestamp, count)，当同一个timestamp被再次敲中的时候，deque最右边的count+=1
103. Binary Tree Zigzag Level Order Traversal可以用queue加reverse， 也可以只用一个queue: pop from left in odd levels & pop from right in even levels. 每次在与pop相反方向的另一头加入元素，Trick is to flip the order of left and right when we are appending from left.\

2. 单调deque

239. Sliding Window Maximumdeque中存指数，左边淘汰过期的，右边保持单减特性\

经典题：用单调减deque的好处是永远只存将来可能成为max的值This is solved super smart through deque, which only contains the potential maximal index in the deque. The front will pop out those passed by the moving window, while the back will pop out those smaller than the new element, since they will never become the max after seeing the new element. It can also be solved through multiset in C++ and heap.

862. Shortest Subarray with Sum at Least K因为元素可能为负数，所以不能用sliding window；用mono deque存presum, 当curr_sum - dq[0] >= k时，更新答案，加入时右边pop出所有比curr_sum大的元素，因为curr_sum有更小的值，且更近的index\

1425. Constrained Subsequence Sum用dp[i]表示以nums[i]结尾并包含nums[i]的最大subsequenceSum, deque存放最近的k个dp[i], 那么dp[i]=num+max(deque)，用单减deque即可实现
1696. Jump Game VI左边pop出过期的，右边保持单调减\

3. 两个deque

2534. Time Taken to Cross the Door用entry和exit两个deque，+1推进time(不能用for loop，因为不知道time什么时候结束)，若有arriva Time<currTime, 全部压入deque；依据lastStatus判断popleft哪个deque
353. Design Snake Game用deque装蛇身，snakeset装同样的东西，为了帮助判断蛇头是否撞到蛇身\

• 由doubly linked list 来实现