โ† Goldman Sachs questions

Implement Queue using one Stack

Filed under Goldman Sachs

Free read 1 of 3

Confirm 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

  1. Confirm that only one stack is allowed and recursion can be used to hold state on the call stack.

Solution

O(N) time for enqueue, O(1) time for dequeue, O(N) space

Python
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.