Command Palette

Search for a command to run...

Hectal
Problem 10.2 · Queue, Deque and Monotonic QueueEasy

Implement Queue Using Stacks

PatternCombine Structures to DesignStack for Matching and Undo

What it teaches: Amortised analysis in action: two stacks reverse order lazily, so each element moves at most twice.

Practise it on judges as “Implement Queue using Stacks”.

The problem

Implement a FIFO queue with push(x), pop(), peek() and empty() using only stack operations.

Example 1

Input: ops = [MyQueue, push, push, peek, pop, empty]
args = [[], [1], [2], [], [], []]
Output: [null, null, null, 1, 1, false]

Constraints

  • 1 ≤ x ≤ 9
  • pop and peek are only called on a non-empty queue
  • At most 100 calls

Pattern clues in the wording

  • → Build one structure from another
  • → Amortised O(1) asked

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

MyQueue.java · starter
import java.util.*;

class MyQueue {
    public MyQueue() {}
    public void push(int x) {}
    public int pop() { return 0; }
    public int peek() { return 0; }
    public boolean empty() { return true; }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
ops = ["MyQueue","push","push","peek","pop","empty"]
args = [[],[1],[2],[],[],[]]
[null,null,null,1,1,false]
2
ops = ["MyQueue","push","pop","push","push","pop","pop","empty"]
args = [[],[1],[],[2],[3],[],[],[]]
[null,null,1,null,null,2,3,true]

From slow to fast

Approaches

1. Optimal: input and output stacks · O(1) amortised per operation
1

Optimal: input and output stacks

Time O(1) amortised per operation Space O(n)

Push onto in. For pop/peek, if out is empty, move everything from in to out (reversing it), then use out's top. Each element moves from in to out once, so operations are O(1) amortised.

Approach 1
import java.util.ArrayDeque;
import java.util.Deque;

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

    public MyQueue() {}

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

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

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

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

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

Verdict: The standard design.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Interleaved pushes and pops
  • peek then pop the same element

Mistakes people make

  • Moving elements back to in after every pop (O(n) per operation).
  • Refilling out while it still has elements (breaks the order).

Interview

Follow-up questions

How about a stack using queues?