Implement Queue using one Stack
Filed under Goldman Sachs
Free read 1 of 3Confirm that only one stack is allowed and recursion can be used to hold state on the call stack.
The question
Implement a standard Queue data structure supporting push and pop operations using only a single stack, utilizing recursion for queue operations.
Constraints
- Use only one stack data structure.
- Use recursion to simulate queue operations (such as reversing elements during push/pop).
- Time complexity of operations should be handled within recursion limits.
Examples
- Input
- Queue operations: push(1), push(2), pop()
- Output
- 1
- Why
- First in, first out. 1 was pushed first, so pop returns 1.
Approach
Confirm that only one stack is allowed and recursion can be used to hold state on the call stack.
Normally two stacks are used. For one stack, pop/push requires moving elements.
For enqueue, pop all elements from the stack recursively, push the new element at the bottom, and push the popped elements back.
Operations on an empty queue or single element queue.
Solution
O(N) time for enqueue, O(1) time for dequeue, O(N) space
class QueueUsingOneStack:
def __init__(self):
self.stack = []
def enqueue(self, x):
if not self.stack:
self.stack.append(x)
return
temp = self.stack.pop()
self.enqueue(x)
self.stack.append(temp)
def dequeue(self):
return self.stack.pop() if self.stack else None
Tips
- What they are testing: Test alternating push and pop sequences to ensure FIFO ordering is preserved correctly.
- Common mistake: Using an auxiliary stack or iterative approach when the interviewer specifically asked for a single stack with recursion.
Related Goldman Sachs questions
Collected from public candidate posts and coding forums. Updated Nov 2026.