DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Implement Queue using Stacks

easyStack and queue

Problem statement

Build a first-in, first-out queue, MyQueue, using only stacks. You may use two stacks, and you may only use the standard stack operations on them: push to the top, pop from the top, look at the top, check the size and check whether it is empty.

Support these operations:

  • push(x) adds x to the back of the queue.
  • pop() removes and returns the element at the front.
  • peek() returns the element at the front without removing it.
  • empty() returns whether the queue is empty.

pop and peek are only called on a non-empty queue.

Examples

Example 1

Input: push(5) push(8) peek() pop() push(3) pop() empty()

Output: 5 5 8 false

Explanation: 5 went in first, so it comes out first. 8 is next, and 3 is still waiting, so the queue is not empty.

Example 2

Input: push(4) pop() empty()

Output: 4 true

Hints

Approach

Use two stacks and move elements lazily.

  1. push(x) always pushes onto inbox. O(1).
  2. For pop or peek, if outbox is empty, pop every element from inbox and push it onto outbox. This reverses them, so the oldest element is now on top of outbox.
  3. Then pop or read the top of outbox.
  4. The queue is empty only when both stacks are empty.

A single transfer can move many elements, but every element is moved from inbox to outbox at most once in its lifetime. Spread over all operations, each one costs O(1) amortized.

ComplexityTime O(1) amortized per operationSpace O(n)
Python
class MyQueue:
def __init__(self):
self.inbox = [] # new elements go here
self.outbox = [] # oldest element on top
def push(self, x: int) -> None:
self.inbox.append(x)
def _shift(self) -> None:
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
def pop(self) -> int:
self._shift()
return self.outbox.pop()
def peek(self) -> int:
self._shift()
return self.outbox[-1]
def empty(self) -> bool:
return not self.inbox and not self.outbox

Follow-up questions

  • Make every single operation worst-case O(1), not just amortized. Is it possible with only stacks?

Frequently asked questions

One pop may cost O(n) when it has to refill outbox, but that refill moves elements that will never be moved again. Over any sequence of n operations the total work is O(n), so the average per operation is constant.

It tests whether you understand how FIFO and LIFO differ, which matters for work queues, retry queues and log buffers. The in/out buffer trick also mirrors real designs where writes are batched into one buffer and drained into another by a reader.

Not within the rules, since that removes from the bottom of the stack. It is also O(n). For a real queue in Python, use collections.deque with append and popleft.