Implement Queue using Stacks

# 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 Queue using Stacks

Implement a first-in-first-out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Easy

Examples

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

Approach 1

Level I: Two Stacks (Push O(N))

Intuition

When pushing an element, move all elements from the primary stack to a temporary stack, push the new element, then move everything back.

⏱ Push $O(N)$, Pop $O(1)$.💾 O(N).

Detailed Dry Run

Push(1), Push(2) -> S1: [2, 1] (top is 1)

java

import java.util.*;\nclass MyQueue {\n    Stack<Integer> s1 = new Stack<>(), s2 = new Stack<>();\n    public void push(int x) {\n        while(!s1.isEmpty()) s2.push(s1.pop());\n        s1.push(x);\n        while(!s2.isEmpty()) s1.push(s2.pop());\n    }\n    public int pop() { return s1.pop(); }\n    public int peek() { return s1.peek(); }\n    public boolean empty() { return s1.isEmpty(); }\n}

Approach 2

Level II: Two Stacks (Pop O(N))

Intuition

To make push $O(1)$ , just push to s1. For pop and peek, if s1 has elements, move everything to s2, remove/view the top, then move everything back to s1 to maintain order. This establishes a baseline for amortized optimization.

⏱ Push O(1), Pop/Peek O(N).💾 O(N).

Detailed Dry Run

Push(1), Push(2), Pop()

Op	S1	S2	Action
`push(1)`	`[1]`	`[]`
`push(2)`	`[1, 2]`	`[]`
`pop()`	`[]`	`[1, 2]`	Move S1 to S2, pop 1, move back
Result: 1

java

class MyQueue {
    Stack<Integer> s1 = new Stack<>(), s2 = new Stack<>();
    public void push(int x) { s1.push(x); }
    public int pop() {
        while(!s1.isEmpty()) s2.push(s1.pop());
        int res = s2.pop();
        while(!s2.isEmpty()) s1.push(s2.pop());
        return res;
    }
    public int peek() {
        while(!s1.isEmpty()) s2.push(s1.pop());
        int res = s2.peek();
        while(!s2.isEmpty()) s1.push(s2.pop());
        return res;
    }
    public boolean empty() { return s1.isEmpty(); }
}

Approach 3

Level III: Two Stacks (Amortized O(1))

Intuition

Use inStack for push and outStack for pop. Transfer only when outStack is empty. This way, each element is moved at most twice (once into inStack, once into outStack), leading to $O(1)$ amortized time.

⏱ Push $O(1)$, Pop amortized $O(1)$.💾 O(N).

Detailed Dry Run

Push(1), Push(2) -> In: [1, 2]. Pop() -> Move to Out: [2, 1]. Pop 1.

Op	In	Out	Action
`push(1)`	`[1]`	`[]`
`push(2)`	`[1, 2]`	`[]`
`pop()`	`[]`	`[2]`	Move S1 to S2, return 1
Result: 1

java

import java.util.*;
class MyQueue {
    Stack<Integer> in = new Stack<>(), out = new Stack<>();
    public void push(int x) { in.push(x); }
    public int pop() { peek(); return out.pop(); }
    public int peek() {
        if (out.isEmpty()) while(!in.isEmpty()) out.push(in.pop());
        return out.peek();
    }
    public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}

← Previous QuestionImplement Stack using Queues

Next Question →Design Hit Counter

Found an issue or have a suggestion?

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