Simple queue with O(1) retrieval of minimum and maximum values

minmaxqueue.py

from collections import deque


class MinMaxQueue(object):

    def __init__(self, maxlen=None):
        self._queue_all = deque(maxlen=maxlen)
        self._queue_min = deque(maxlen=maxlen)
        self._queue_max = deque(maxlen=maxlen)

    def __getitem__(self, index):
        return self._queue_all[index]

    def __len__(self):
        return len(self._queue_all)

    def min(self):
        return self._queue_min[0]

    def max(self):
        return self._queue_max[0]

    def push(self, element):
        self._queue_all.append(element)

        while self._queue_min and self._queue_min[-1] > element:
            self._queue_min.pop()
        self._queue_min.append(element)

        while self._queue_max and self._queue_max[-1] < element:
            self._queue_max.pop()
        self._queue_max.append(element)

    def pop(self):
        head_element = self._queue_all[0]

        if head_element == self._queue_min[0]:
            self._queue_min.popleft()

        if head_element == self._queue_max[0]:
            self._queue_max.popleft()

        return self._queue_all.popleft()