PPractick

The problem

A message broker's SDK only exposes a FIFO queue primitive, but one feature (undoing the most recent actions) needs LIFO behaviour. The task is to build a stack (push, pop, top, empty) on top of queue operations only: push to back, pop from front, peek at the front, size. The standard trick uses a single queue: after pushing a new element, rotate all the older elements behind it, so the newest element is always at the front, where pop and top can reach it in O(1).

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

Function signature

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

Test cases

Operations	Output	Explanation
push(1) push(2) top() pop() empty()	2 2 false	LeetCode's example
push(1) push(2) push(3) pop() pop() pop()	3 2 1	Last in, first out
push(1) push(2) pop() push(3) top()	2 3	Interleaved
push(5) top() empty()	5 false
push(4) pop() empty()	4 true

(Confirm: only standard queue operations may be used; pop and top are never called on an empty stack.)

How interviewers phrase it

• "Implement a last-in-first-out stack using only queues" (LeetCode 225), with "can you do it with one queue?" as the follow-up.

Clarifying questions to ask

1. Which queue operations are allowed? (push to back, pop from front, front, size, empty.)
2. Which operation should be cheap: push or pop?
3. Can pop or top be called on an empty stack?

Follow-ups to expect

1. "How does the one-queue version work?"
2. "What's the two-queue version?"
3. "Can you make push O(1) instead?"
4. "Which is better?"
5. "Complexity?"

Related questions

• Implement Queue using Stack 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