Implement Stack using Queues

# System & Data Structure Design Design problems in DSA interviews test your ability to translate requirements into a functional, efficient, and maintainable class structure. Unlike standard algorithmic problems, the focus here is on **State Management** and **API Design**. ### Core Principles 1. **Encapsulation:** Keep data private and expose functionality through well-defined methods. 2. **Trade-offs:** Every design choice has a cost. Is it better to have $O(1)$ read and $O(N)$ write, or vice versa? 3. **State Consistency:** Ensure that your internal data structures (e.g., a Map and a List) stay in sync after every operation. ### Common Design Patterns #### 1. HashMap + Doubly Linked List (DLL) The "Gold Standard" for $O(1)$ caching (LRU/LFU). ```text [Head] <-> [Node A] <-> [Node B] <-> [Node C] <-> [Tail] ^ ^ ^ ^ ^ (MRU) (Data) (Data) (Data) (LRU) ``` - **HashMap:** Provides $O(1)$ lookups for keys to their corresponding nodes. - **DLL:** Provides $O(1)$ addition/removal of nodes at both ends, maintaining the order of access. #### 2. Amortized Analysis (Rebalancing) Commonly used in **Queue using Stacks** or **Dynamic Arrays**. - Instead of doing heavy work on every call, we batch it. Pushing to a stack is $O(1)$, and "flipping" elements to another stack happens only when necessary, averaging $O(1)$ per operation. #### 3. Ring Buffers (Circular Arrays) Used for fixed-size memory management (e.g., **Circular Queue**, **Hit Counter**). ```text [0] [1] [2] [3] [4] [5] ^ ^ ^ Head (Data) Tail (Pops) (Next Push) ``` - Use `(index + 1) % capacity` to wrap around the array. #### 4. Concurrency & Thread Safety For "Hard" design problems (e.g., **Bounded Blocking Queue**). - Use **Mutexes** (Locks) to prevent data races. - Use **Condition Variables** (`wait`/`notify`) to manage producer-consumer logic efficiently without busy-waiting. ### How to Approach a Design Problem 1. **Identify the API:** What methods do you need to implement? (`get`, `put`, `push`, etc.) 2. **Define the State:** What variables represent the current state? (Size, Capacity, Pointers). 3. **Choose the Data Structures:** Select the combination that minimizes time complexity for the most frequent operations. 4. **Dry Run:** Trace the state changes through a sequence of operations based on your chosen structure.

Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using one or more queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Easy

Examples

Input: ["MyStack", "push", "push", "top", "pop", "empty"]\n[[], [1], [2], [], [], []]
Output: [null, null, null, 2, 2, false]

Approach 1

Level I: Two Queues (Push O(1))

Intuition

Maintain two queues. push is $O(1)$ to q1. For pop, we move all elements except the last one from q1 to q2, then the last one is the stack's top.

⏱ O(1) push, O(N) pop/top.💾 O(N).

Detailed Dry Run

Input: push(1), push(2), pop()\n| Step | Op | Q1 | Q2 | Result |\n| :--- | :--- | :--- | :--- | :--- |\n| 1 | push(1) | [1] | [] | null |\n| 2 | push(2) | [1, 2] | [] | null |\n| 3 | pop() | [] | [1] | 2 |

java

import java.util.*;\nclass MyStack {\n    private Queue<Integer> q1 = new LinkedList<>();\n    private Queue<Integer> q2 = new LinkedList<>();\n    private int top;\n    public void push(int x) { q1.add(x); top = x; }\n    public int pop() {\n        while (q1.size() > 1) { top = q1.poll(); q2.add(top); }\n        int res = q1.poll();\n        Queue<Integer> temp = q1; q1 = q2; q2 = temp;\n        return res;\n    }\n    public int top() { return top; }\n    public boolean empty() { return q1.isEmpty(); }\n}

Approach 2

Level II: Two Queues (Pop/Top O(1))

Intuition

To make pop and top $O(1)$ , we do the heavy lifting during push. When pushing x, we add it to q2, then move everything from q1 to q2, then swap names. This keeps q1 in LIFO order.

⏱ O(N) push, O(1) pop/top.💾 O(N).

Detailed Dry Run

Push(1), Push(2)

Op	Q1	Q2	Action
`push(1)`	`[1]`	`[]`	Simple add
`push(2)`	`[]`	`[2, 1]`	Add 2 to Q2, then move 1 from Q1 to Q2
`pop()`	`[1]`	`[]`	pop from Q1

java

class MyStack {
    private Queue<Integer> q1 = new LinkedList<>(), q2 = new LinkedList<>();
    public void push(int x) {
        q2.add(x);
        while(!q1.isEmpty()) q2.add(q1.poll());
        Queue<Integer> temp = q1; q1 = q2; q2 = temp;
    }
    public int pop() { return q1.poll(); }
    public int top() { return q1.peek(); }
    public boolean empty() { return q1.isEmpty(); }
}

Approach 3

Level III: One Queue (Optimal)

Intuition

The optimal implementation uses only one queue. For push, we add the element and rotate the queue $N-1$ times so the newly added element becomes the front of the queue.

⏱ O(N) push, O(1) pop/top.💾 O(N).

Detailed Dry Run

Queue: [1, 2] -> push(3) -> [1, 2, 3] -> Rotate 1: [2, 3, 1] -> Rotate 2: [3, 1, 2]

Step	Queue	Action
1	`[1,2]`	Initial
2	`[1,2,3]`	Add 3 to back
3	`[2,3,1]`	Poll 1, Add to back
4	`[3,1,2]`	Poll 2, Add to back
Result: 3 is at front (LIFO)

java

import java.util.*;
class MyStack {
    private Queue<Integer> q = new LinkedList<>();
    public void push(int x) {
        q.add(x);
        for (int i = 0; i < q.size() - 1; i++) q.add(q.poll());
    }
    public int pop() { return q.poll(); }
    public int top() { return q.peek(); }
    public boolean empty() { return q.isEmpty(); }
}

← Previous QuestionDesign Tic-Tac-Toe

Next Question →Implement Queue using Stacks

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.