Back to DSA

Implement Queue using Stacks

easy
Acceptance: 63%
StackQueueDesign

Construct a FIFO queue using nothing but two stacks and their standard operations (push to top, pop from top, peek at top, check if empty). Your MyQueue class should provide push, pop, peek, and empty methods that behave exactly like a real queue.

Examples

Example 1:
Input:MyQueue(), push(5), push(10), peek(), pop(), empty()
Output:[null,null,null,5,5,false]

Hints

Related Problems

Min StackmediumValid ParentheseseasyEvaluate Reverse Polish NotationmediumDaily TemperaturesmediumNext Greater Element Ieasy
00:00
import java.util.*;

class MyQueue {
    private Deque<Integer> in = new ArrayDeque<>();
    private Deque<Integer> out = new ArrayDeque<>();

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

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

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

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

    private void move() { if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop()); }
}
Time complexityO(1) amortized
Space complexityO(n)