Implement stack using queue
Filed under Amazon · Also reported at MakeMyTrip, Mindtree, Red Hat, Traveloka
Free read 1 of 3Understand whether the push operation or the pop operation should be made costly (O(n) time), and confirm the allowed queue interface.
The question
Implement a last-in, first-out (LIFO) stack using only standard queue operations (enqueue, dequeue, peek, size, and is_empty).
Constraints
- You must use only standard queue operations: push to back, peek/pop from front, size, and is empty.
- Depending on the design, either push or pop should operate in O(n) time complexity.
- The stack should support standard operations: push, pop, top, and empty.
Examples
- Input
- push(1), push(2), top(), pop(), empty()
- Output
- 2, 2, false
- Why
- After pushing 1 and then 2, top returns 2. Pop removes 2 and returns it. Empty returns false since 1 is still in the stack.
Approach
Understand whether the push operation or the pop operation should be made costly (O(n) time), and confirm the allowed queue interface.
Maintain two queues, copying elements back and forth during pushes and pops to mimic stack order.
Make push costly by rotating the queue elements upon each new insertion so that the newly added element is always at the front of the queue.
Popping or peeking from an empty stack, and handling a stack with a single element.
Solution
O(n) time for push, O(1) time for pop/top, O(n) space
from collections import deque
class MyStack:
def __init__(self):
self.q = deque()
def push(self, x: int) -> None:
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self) -> int:
return self.q.popleft()
def top(self) -> int:
return self.q[0]
def empty(self) -> bool:
return not self.q
Tips
- What they are testing: Test alternating push and pop operations to ensure LIFO order is maintained correctly under mixed workloads.
- Common mistake: Trying to make both push and pop O(1) operations, which is impossible using only standard queues without auxiliary data structures.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.