PPractick

The problem

A functional-programming runtime only offers immutable stacks, but a job scheduler built on it needs a FIFO queue (push, pop, peek, empty). Two stacks solve it: an input stack receives pushes, and an output stack serves pops. When the output stack runs dry, pour the entire input stack into it, which reverses the order so the oldest element ends up on top. Each element is moved at most once, so every operation is amortised O(1).

Example: push(1), push(2), peek() → 1, pop() → 1, empty() → false.

Function signature

class MyQueue {
public:
    void push(int x);
    int pop();      // called only when non-empty
    int peek();     // called only when non-empty
    bool empty();
};

Test cases

Operations	Output	Explanation
push(1) push(2) peek() pop() empty()	1 1 false	LeetCode's example
push(1) push(2) push(3) pop() pop() pop()	1 2 3	First in, first out
push(1) push(2) pop() push(3) pop() pop()	1 2 3	New pushes wait behind older ones
push(9) peek() empty()	9 false
push(4) pop() empty()	4 true

(Confirm: only stack operations may be used; pop and peek are never called on an empty queue; amortised O(1) is expected.)

How interviewers phrase it

• "Implement a first-in-first-out queue using only two stacks" (LeetCode 232), "with amortised O(1) operations".

Clarifying questions to ask

1. Which stack operations are allowed? (push, pop, top, size, empty.)
2. Is amortised O(1) acceptable, or must each operation be worst-case O(1)?
3. Can pop or peek be called on an empty queue?

Follow-ups to expect

1. "When do you transfer from in to out?"
2. "Why is it amortised O(1)?"
3. "What's the worst case for a single operation?"
4. "What's the naive approach?"
5. "Complexity?"

Related questions

• Implement Stack using Queue Easy
• Implement Stack using Arrays Easy
• Implement Queue using Arrays Easy
• Implement stack using Linkedlist Easy
• Implement queue using Linkedlist Easy
• Balanced Paranthesis Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in