< Back





232. Implementing Queue using Stacks

We're asked to implement a queue class using stacks. We could just simply use just one stack and do
some Python operations on it to simulate a queue, but that beats the purpose of this exercise.
Realistically, we want to use the stacks the way the were intended, by only using push and pop
operations.

Therefore, we use two stacks. The first stack will be used for all push operations. The second stack
is used to amortize the pop operation. What do I mean by this? When the second stack is empty, when
a pop operation happens, all the contents of the first stack will be popped off and pushed onto the
second stack. This essentially reverses the order of the contents of the first stack, allowing us
to simulate a queue.

After conducting this operation, we can now return the top of the second stack, either during a peek
operation or a pop operation, returning the first element in the queue. This is amortized because
we won't do this operation again until the second stack is empty.

The solution is as follows:


  class MyQueue:
      def __init__(self):
          self.stack1 = []
          self.stack2 = []

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

      def pop(self) -> int:
          self.peek()
          return self.stack2.pop()

      def peek(self) -> int:
          if not self.stack2:
              while self.stack1:
                  self.stack2.append(self.stack1.pop())
          return self.stack2[-1]

      def empty(self) -> bool:
          return not (self.stack1 or self.stack2)


_ Time Complexity:

  O(1) - Pushing and popping are amortized operations.

_ Space Complexity:

  O(n) - We store the queue elements in two stacks.