Implement Queue using Stacks

The problem description can be found in LeetCode.

Approach

Suppose that we need to make a lot of push operations. After doing so, the first element that is in the stack (we are forced to use a stack as data structure) is at the bottom. So we cannot directly access it, since there is no stack operation that allows us to do it. In fact, we cannot use any index (as for the requirements).

Now, suppose that we have the same number of pop operations. We know that we must use another stack (as for the requirements), so we can use the other stack to store the values we have to pop. If we pop from the first stack and we push to the second one, magically the actual order is restored, we can start to return the values from the second stack.

Let's take an example:

obj = MyQueue()
obj.push(1)
obj.push(2)
obj.push(3)
obj.push(4)

# `obj.stack_1` would be
#
# | 4 |
# | 3 |
# | 2 |
# | 1 |
# |___|

Now, let's make a single pop operation and move all the elements to the other stack:

obj = MyQueue()
_ = obj.pop()

# `obj.stack_2` would be
#
# | 1 |
# | 2 |
# | 3 |
# | 4 |
# |___|

So if we pop from obj.stack_2 we can get the proper order.

Solution

from typing import List


class MyQueue:
    def __init__(self) -> None:
        self.stack_push: List[int] = []
        self.stack_pop: List[int] = []

    def push(self, x: int) -> None:
        self.stack_push.append(x)

    def pop(self) -> int:
        if self.stack_pop:
            return self.stack_pop.pop()

        self._reorganize_stacks()
        return self.pop()

    def peek(self) -> int:
        if self.stack_pop:
            return self.stack_pop[-1]

        self._reorganize_stacks()
        return self.peek()

    def empty(self) -> bool:
        return not self.stack_push and not self.stack_pop

    def _reorganize_stacks(self) -> None:
        assert not self.stack_pop
        assert self.stack_push

        while self.stack_push:
            self.stack_pop.append(self.stack_push.pop())

Complexity

For the single operation, we would have the following complexities:

• push:
  • Time: $O(1)$
  • Space: $O(1)$
• pop:
  • Time: $O(1)$
  • Space: $O(1)$
• peek:
  • Time: $O(1)$
  • Space: $O(1)$
• empty:
  • Time: $O(1)$
  • Space: $O(1)$