每日一道Leetcode - 剑指 Offer 59 - II. 队列的最大值 【队列】

import queue
class MaxQueue:

    def __init__(self):
        # 初始化队列queue 双端队列deque
        # 双端队列：维护递减队列需要队首元素弹出，队尾元素插入、队尾弹出操作均为O(1)时间复杂度
        self.queue = queue.Queue()
        self.deque = queue.deque()

    def max_value(self) -> int:
        if self.deque:
            return self.deque[0]
        else:
            return -1

    def push_back(self, value: int) -> None:
        # 入队 维护递减序列
        self.queue.put(value)
        # 双端队列不为空，只要队尾元素小于value,一直弹出队尾元素
        while self.deque and self.deque[-1] < value:
            self.deque.pop()
        # 插入元素
        self.deque.append(value)

    def pop_front(self) -> int:
        # queue队列为空,则返回-1
        if self.queue.empty():
            return -1
        val = self.queue.get()
        if val == self.deque[0]:
            # 如果弹出的元素为最大值,需要从双端队列最左侧弹出
            self.deque.popleft()
        return val


# 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()