🦄 Moonbeam Queue: Two-Stack Queue

Difficulty: Intermediate Tags: queue, stack, design, amortized-analysis Series: Data Structures I

Problem

In the mystical realm, moonbeams follow a strict FIFO (First-In-First-Out) order. However, you only have access to magical stacks (LIFO structures). Your challenge is to implement a queue using only two stacks.

Implement a queue that supports the following operations: - push(x): Add element x to the back of the queue - pop(): Remove and return the front element - peek(): Return the front element without removing it - empty(): Return whether the queue is empty

Given a sequence of operations, execute them and return the outputs for pop, peek, and empty operations (push returns nothing).

Real-World Application

Two-stack queue implementations appear in: - Interview questions - classic data structure design problem - System design - understanding amortized time complexity - Functional programming - immutable data structure implementations - Message queues - buffer management with limited primitives - Undo/redo systems - managing operation histories - Browser history - back/forward navigation

Input

data = {
    'ops': list  # List of operations [op_name, ...args]
}

Operations format: - ['push', x] - Push integer x to queue - ['pop'] - Remove and return front element - ['peek'] - Return front element - ['empty'] - Return True if empty, False otherwise

Output

list[Any]  # Results from pop, peek, and empty operations

Constraints

• 1 ≤ number of operations ≤ 100,000
• Operations are valid (no pop/peek on empty queue)
• Must achieve amortized O(1) for all operations

Examples

Example 1: Basic Operations

Input:

{
    'ops': [
        ['push', 1],
        ['push', 2],
        ['peek'],
        ['pop'],
        ['empty']
    ]
}

Output: [1, 1, False]

Explanation: 1. push(1) - Queue: [1] 2. push(2) - Queue: [1, 2] 3. peek() - Returns 1 (front element), Queue: [1, 2] 4. pop() - Returns 1, Queue: [2] 5. empty() - Returns False (queue has element 2)

Output: [1, 1, False] (peek, pop, empty results)

Example 2: Mixed Operations

Input:

{
    'ops': [
        ['push', 10],
        ['push', 11],
        ['pop'],
        ['peek'],
        ['empty']
    ]
}

Output: [10, 11, False]

Explanation: 1. push(10) - Queue: [10] 2. push(11) - Queue: [10, 11] 3. pop() - Returns 10, Queue: [11] 4. peek() - Returns 11 (front element) 5. empty() - Returns False

Example 3: Empty Queue

Input:

{
    'ops': [
        ['push', 5],
        ['pop'],
        ['empty']
    ]
}

Output: [5, True]

Explanation: 1. push(5) - Queue: [5] 2. pop() - Returns 5, Queue: [] 3. empty() - Returns True (queue is now empty)

What You'll Learn

• How to simulate a queue using two stacks
• Amortized time complexity analysis
• When and how to transfer elements between stacks
• Data structure design with limited primitives

Why This Matters

This is one of the most famous interview questions that tests: - Understanding of data structure properties (FIFO vs LIFO) - Ability to design efficient solutions with constraints - Knowledge of amortized analysis - Creative problem-solving skills

Starter Code

def challenge_function(data):
    """
    Implement a queue using two stacks.

    Args:
        data: dict with key 'ops' - list of operations

    Returns:
        list: Results from pop, peek, and empty operations
    """
    # Your implementation here
    pass