05-Implement-Queue-using-Stacks.md

Implement Queue using Stacks

Problem Link

https://leetcode.com/problems/implement-queue-using-stacks/

---

Pattern

• Stack
• Queue
• Design

---

Approach

Use one stack for input and one for output. Transfer only when needed.

---

Time Complexity

Amortized O(1) per operation

Space Complexity

O(n)

---

Java Solution

import java.util.*;
class MyQueue {
    private Stack<Integer> in = new Stack<>();
    private Stack<Integer> out = new Stack<>();

    public void push(int x) {
        in.push(x);
    }

    private void shift() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) out.push(in.pop());
        }
    }

    public int pop() {
        shift();
        return out.pop();
    }

    public int peek() {
        shift();
        return out.peek();
    }

    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}