Deque

应用

Deque又叫做双端队列。一般来说，如果我们想要同时具备stack和queue的操作性质，我们可以考虑使用deque。

题型

• 比如说sliding window maximum这道题，我们本质上的思想是递增栈，所以我们肯定需要栈的性质。但是又因为window size的性质，我们得删除很久之前加进来的过期的number，这时我们又需要queue的性质。所以我们使用deque。
• 比如说design snake game这道题，我们本质上的思想是每次move需要删掉尾巴，加入新的头。那么我们需要在两端都能进行操作，所以我们使用deque。

题目

• Leetcode 353. Design Snake Game (因为每次贪吃蛇移动时我们既需要更新头，也需要更新尾，所以需要deque)
• Leetcode 239. Sliding Window Maximum
• Sliding Window Maximum for Data Streaming