Here's a more compact version of the variant with an underlying dict:

    class MyQueue(Queue):
        def _init(self, maxsize):
            self.end = 0
            self.q = {}
        def _qsize(self):
            return len(self.q)
        def _put(self, x):
            self.q[self.end] = x
            self.end += 1
        def _get(self):
            i = self.end - len(self.q)
            return self.q.pop(i)