单调队列

https://labuladong.github.io/algo/2/20/51/

也许这种数据结构的名字你没听过，其实没啥难的，就是一个「队列」，只是使用了一点巧妙的方法，使得队列中的元素全都是单调递增（或递减）的。

「单调栈」主要解决 Next Great Number 一类算法问题，而「单调队列」这个数据结构可以解决滑动窗口相关的问题，比如说LeetCode第 239 题「滑动窗口最大值」

class MonotonicQueue
{
    private LinkedList<Integer> queue = new LinkedList<Integer>();
    public MonotonicQueue()
    {
        queue = new LinkedList<Integer>();
    }
    
    public void push(int x)
    {
        while(!queue.isEmpty() && queue.getLast() < x)
        {
            queue.pollLast();
        }
        queue.addLast(x);
    }
    
    public int max()
    {
        return queue.getFirst();
    }
    
    public void pop(int x)
    {
        if( x == queue.getFirst()) 
        {
            queue.pollFirst();
        }
    }
}