Interview Prepstacks-monotonic-stackeasyAmazonBloomberg

Implement Stack Using Queues

Choose your preparation mode4 modes available

Try It Solution Trace

📋

Problem

Imagine you only have a queue data structure available, but you need to implement a stack for your application. How can you simulate the Last-In-First-Out behavior using First-In-First-Out operations?

Implement a last-in-first-out (LIFO) stack using only two queues or one queue. The implemented stack should support all the functions of a normal stack: push, pop, top, and empty. Implement the MyStack class: - void push(int x) Pushes element x onto the stack. - int pop() Removes the element on top of the stack and returns it. - int top() Returns the element on the top of the stack. - boolean empty() Returns true if the stack is empty, false otherwise. Notes: - You must use only standard operations of a queue, which means only push to back, peek/pop from front, size and is empty operations are valid. - Depending on the approach, you may use one or two queues.

1 ≤ x ≤ 10^5At most 10^5 calls will be made to push, pop, top, and empty.pop and top operations will always be called on non-empty stacks.

Edge cases: pop on stack with only one element → returns that element and stack becomes emptytop on stack with only one element → returns that element without removing itempty on newly created stack → returns true

</>

IDE

class MyStack:
    def __init__(self):
        pass
    def push(self, x: int) -> None:
        pass
    def pop(self) -> int:
        pass
    def top(self) -> int:
        pass
    def empty(self) -> bool:
        pass

class MyStack:
    def __init__(self):
        # Write your solution here
        pass
    def push(self, x: int) -> None:
        pass
    def pop(self) -> int:
        pass
    def top(self) -> int:
        pass
    def empty(self) -> bool:
        pass

class MyStack {
    public MyStack() {
        // Write your solution here
    }
    public void push(int x) {
    }
    public int pop() {
        return 0;
    }
    public int top() {
        return 0;
    }
    public boolean empty() {
        return false;
    }
}

#include <queue>
using namespace std;

class MyStack {
public:
    MyStack() {
        // Write your solution here
    }
    void push(int x) {
    }
    int pop() {
        return 0;
    }
    int top() {
        return 0;
    }
    bool empty() {
        return false;
    }
};

class MyStack {
    constructor() {
        // Write your solution here
    }
    push(x) {
    }
    pop() {
        return 0;
    }
    top() {
        return 0;
    }
    empty() {
        return false;
    }
}

0/9

Common Bugs to Avoid

Wrong: pop returns elements in FIFO order instead of LIFOPush operation does not rotate the queue after enqueue, so the oldest element is popped first.✅ After enqueueing new element in push, rotate the queue by dequeuing and enqueuing all previous elements once.

Wrong: top returns wrong element after multiple popsTop operation returns last element enqueued instead of front of queue after rotation.✅ Ensure push rotates queue so that the top element is always at the front; top returns front element.

Wrong: empty returns false on new stackEmpty method does not check if internal queue is empty properly.✅ Implement empty() by checking if the queue size is zero.

Wrong: pop or top fails on single element stackPop or top does not handle single element queue correctly, possibly causing errors or wrong returns.✅ Handle single element queue case explicitly or ensure queue operations work correctly for size one.

Wrong: TLE on large inputPush operation implemented with nested loops or inefficient queue operations causing O(n^2) or worse complexity.✅ Use efficient queue rotation with O(n) per push and O(1) pop/top; avoid nested loops.

✓

Test Cases

t1_01basic

Input["push(1)","push(2)","top()","pop()","empty()"]

Expected[2,2,false]

After pushing 1 and 2, the top is 2. Popping removes 2. The stack is not empty after popping 2.

t1_02basic

Input["push(3)","push(4)","top()","pop()","top()","empty()"]

Expected[4,4,3,false]

Push 3 then 4; top is 4; pop removes 4; new top is 3; stack is not empty.

Practice

(1/5)

1. Given the following Python code for asteroid collision, what is the output when the input is [8, -8, 5, -10]?

def asteroidCollision(asteroids):
    stack = []
    for a in asteroids:
        alive = True
        while alive and stack and stack[-1] > 0 and a < 0:
            if stack[-1] < -a:
                stack.pop()
            elif stack[-1] == -a:
                stack.pop()
                alive = False
            else:
                alive = False
        if alive:
            stack.append(a)
    return stack

print(asteroidCollision([8, -8, 5, -10]))

easy

A. [5, -10]

B. [-10]

C. [8, 5, -10]

D. []

4. Consider the following buggy code for asteroid collision. Which line contains the subtle bug that causes incorrect behavior on equal size asteroids?

def asteroidCollision(asteroids):
    stack = []
    for a in asteroids:
        alive = True
        while alive and stack and stack[-1] > 0 and a < 0:
            if stack[-1] < -a:
                stack.pop()
            elif stack[-1] == -a:
                alive = False
            else:
                alive = False
        if alive:
            stack.append(a)
    return stack

medium

A. Line with 'stack.pop()' inside 'if stack[-1] < -a:'

B. Line with 'while alive and stack and stack[-1] > 0 and a < 0:' condition

C. Line with 'alive = False' inside 'elif stack[-1] == -a:'

D. Line with 'stack.append(a)' after the while loop

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Implement Stack Using Queues

Practice

Solution

Step 1: Trace collision between 8 and -8

Step 2: Process 5 and then -10

Final Answer:

Quick Check:

Solution

Step 1: Trace right boundary computation for i=2 (height=5)

Step 2: Trace i=1 (height=1)

Step 3: Trace i=0 (height=2)

Final Answer:

Quick Check:

Solution

Step 1: Trace push(3)

Step 2: Trace push(5)

Step 3: Trace push(2)

Step 4: Trace pop()

Step 5: getMin()

Final Answer:

Quick Check:

Solution

Step 1: Identify behavior on equal size asteroids

Step 2: Check code for equal size case

Final Answer:

Quick Check:

Solution

Step 1: Analyze stack operations on nums2

Step 2: Analyze mapping and lookup for nums1

Final Answer:

Quick Check:

Ready to prove it?