How to Solve: Implement Stack Using Queues (and Vice Versa) – Complete Guide for FAANG Interviews

How to Solve: Implement Stack Using Queues (and Vice Versa) – Complete Guide for FAANG Interviews

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—mastering it proves you can design data structures from scratch, a skill that separates L4 from L5 engineers at FAANG."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, you must understand: 1. Queue (FIFO): enqueue(), dequeue(), peek(), isEmpty(). 2. Stack (LIFO): push(), pop(), peek(), isEmpty(). 3. Time/Space Complexity: Amortized vs. worst-case analysis.

If you’re shaky on any of these, stop and review—this guide assumes fluency.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK

Run this checklist for every "Implement X Using Y" problem:

1. Clarify Requirements
2. Ask: "Can I use built-in methods (e.g., collections.deque)?"

3. Confirm: "What’s the expected time complexity for each operation?"

4. Choose the Right Technique

5. If push() must be O(1) → Single Queue (Rotate on Pop).

6. If pop() must be O(1) → Two Queues (Transfer on Push).

7. Draw the Data Flow

8. Sketch how elements move between queues/stacks during each operation.

9. Example: For push(1), push(2), pop() → show how 2 ends up at the front.

10. Handle Edge Cases

11. Empty structure (pop()/peek() on empty stack).

12. Single-element case (pop() after one push()).

13. Optimize for Constraints

14. If space is tight, prefer single-queue (no extra storage).

15. If time is critical, prefer two-queue (O(1) pop()).

16. Write Pseudocode First

17. Example for Stack Using Queues (Single Queue):
    ```
    push(x):
    q.enqueue(x)
    for i in 1..len(q)-1:
    q.enqueue(q.dequeue())

    pop():
    return q.dequeue() ```

18. Code + Test

19. Implement in Python/Java/C++.

20. Test with:

    • push(1), push(2), pop() → 2
    • push(3), peek() → 3
    • pop(), pop() → 1, then error.

21. Analyze Complexity

22. Single Queue: push() = O(n), pop() = O(1).
23. Two Queues: push() = O(1), pop() = O(n).

? WORKED EXAMPLES

Example 1 – Basic: Implement Stack Using a Single Queue (Push-O(n))

Problem: Design a stack using one queue where push() is O(n) and pop() is O(1).

Thought Process

1. Key Insight: To simulate LIFO, the most recently pushed element must be at the front of the queue.
2. Trick: After enqueue(x), rotate the queue to move x to the front.

Python Code

from collections import deque

class MyStack:

    def __init__(self):

        self.q = deque()


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

        self.q.append(x)

        # Rotate the queue to move x to the front

        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 len(self.q) == 0

Complexity

• Time:
• push(): O(n) (rotate n-1 elements).
• pop()/top(): O(1).
• Space: O(n).

Why This Works

• The rotation ensures the last pushed element is always at the front, so pop() removes it in O(1).

Example 2 – Medium: Implement Stack Using Two Queues (Pop-O(n))

Problem: Design a stack using two queues where push() is O(1) and pop() is O(n).

Thought Process

1. Key Insight: Use one queue (q1) as the "active" queue and another (q2) as temporary storage.
2. Trick: On pop(), transfer all elements except the last from q1 to q2, then swap the queues.

Python Code

from collections import deque

class MyStack:

    def __init__(self):

        self.q1 = deque()

        self.q2 = deque()


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

        self.q1.append(x)


    def pop(self) -> int:

        # Move all elements except last from q1 to q2

        while len(self.q1) > 1:

            self.q2.append(self.q1.popleft())

        # Swap q1 and q2

        self.q1, self.q2 = self.q2, self.q1

        return self.q2.popleft()


    def top(self) -> int:

        # Same as pop, but don't remove the last element

        while len(self.q1) > 1:

            self.q2.append(self.q1.popleft())

        top_val = self.q1[0]

        self.q2.append(self.q1.popleft())

        self.q1, self.q2 = self.q2, self.q1

        return top_val


    def empty(self) -> bool:

        return len(self.q1) == 0

Complexity

• Time:
• push(): O(1).
• pop()/top(): O(n) (transfer n-1 elements).
• Space: O(n).

Why This Works

• q1 always holds the stack elements in order. On pop(), we isolate the last element by transferring the rest to q2.

Example 3 – Hard/Follow-Up: Implement Queue Using Two Stacks (Amortized O(1))

Problem: Design a queue using two stacks with amortized O(1) time per operation.

Thought Process

1. Key Insight: Use one stack (s1) for enqueue() and another (s2) for dequeue().
2. Trick: Transfer elements from s1 to s2 only when s2 is empty (lazy transfer).

Python Code

class MyQueue:

    def __init__(self):

        self.s1 = []  # For enqueue

        self.s2 = []  # For dequeue


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

        self.s1.append(x)


    def pop(self) -> int:

        if not self.s2:

            while self.s1:

                self.s2.append(self.s1.pop())

        return self.s2.pop()


    def peek(self) -> int:

        if not self.s2:

            while self.s1:

                self.s2.append(self.s1.pop())

        return self.s2[-1]


    def empty(self) -> bool:

        return not self.s1 and not self.s2

Complexity

• Time:
• push(): O(1).
• pop()/peek(): Amortized O(1) (each element is moved once from s1 to s2).
• Space: O(n).

Why This Works

• The lazy transfer ensures that each element is moved at most once, making pop() amortized O(1).

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. For ‘Implement X Using Y’ problems, follow this playbook:

1. Clarify constraints: Ask if push() or pop() needs to be O(1).
2. Choose your technique:
3. For stack using queues, use one queue + rotation (O(n) push) or two queues + transfer (O(n) pop).
4. For queue using stacks, use two stacks + lazy transfer (amortized O(1)).
5. Draw the data flow: Sketch how elements move during each operation.
6. Handle edge cases: Empty structure, single element.
7. Code it cleanly: Use deque for queues, and test with push(1), push(2), pop().

Remember: The key is to simulate the target structure’s behavior using the given primitives. If you get stuck, fall back to the rotation or transfer trick. You’ve got this!

? Final Notes

• Practice: Implement both stack using queues and queue using stacks in one sitting.
• Follow-ups: Be ready for "Can you do it with one queue?" or "What’s the space complexity?"
• Whiteboard: Draw the data flow before coding—interviewers love this.

Now go crush that interview! ?