解题思路
主要思路:
常规的遍历求队列最大值的方法时间复杂度太高，不符合题意。因此可考虑使用一个辅助队列sup来保存队列中元素最大值的方法。具体实现方法是：如果sup不为空，并且sup的最后一位元素小于当前入队元素value的话，直接把最后一位元素弹出，直到sup为空，或sup的最后一位元素大于等于value。这就保证了sup是单调递减的，且sup的头部总是原始队列的最大值。
步骤：
1)初始化原始队列que和辅助队列sup；
2)求最大值，即辅助队列的首元素sup[0]；
3)入队，首先，在原始队列que末尾添加当前元素value；其次，对于辅助队列，如果sup不为空，并且sup的最后一位元素小于当前入队元素value的话，直接把最后一位元素弹出，直到sup为空，或sup的最后一位元素大于等于value，然后把value加入辅助队列。
4)出队，原始队列首元素出队，并将其与辅助队列的首元素比较，如果相同，辅助队列的首元素也出队，否则，只出队原始队列的首元素。
注：Python中的list形式，用pop(0)的方法可以弹出list的第一个元素，但时间复杂度是O(n)。因此这里采用了Python中的deque()，其可以用popleft()实现pop(0)，时间复杂度为O(1)。
复杂度分析
时间复杂度：O(1)（插入，删除，求最大值），删除操作于求最大值操作显然只需要 O(1) 的时间。而插入操作虽然看起来有循环，做一个插入操作时最多可能会有 n 次出队操作。但要注意，由于每个数字只会出队一次，因此对于所有的 n 个数字的插入过程，对应的所有出队操作也不会大于 n 次。因此将出队的时间均摊到每个插入操作上，时间复杂度为 O(1)。
空间复杂度：O(n)，需要用队列存储所有插入的元素。
代码
class MaxQueue:
def __init__(self):
from collections import deque
self.queue = deque()
self.queue_sup = deque() #辅助队列
def max_value(self) -> int:
if not self.queue_sup:
return -1
else:
return self.queue_sup[0]
def push_back(self, value: int) -> None:
self.queue.append(value)
while self.queue_sup and self.queue_sup[-1] < value:
self.queue_sup.pop()
self.queue_sup.append(value)
def pop_front(self) -> int:
if not self.queue_sup:
return -1
else:
res = self.queue.popleft()
if res == self.queue_sup[0]:
self.queue_sup.popleft()
return res
# Your MaxQueue object will be instantiated and called as such:
# obj = MaxQueue()
# param_1 = obj.max_value()
# obj.push_back(value)
# param_3 = obj.pop_front()
