🦄 Stablehorn Stack: Implement Stack

Difficulty: Beginner Tags: stack, data-structures, design, arrays, LIFO Series: CS 101: Fundamentals

Problem

The Stablehorn's stable uses a Last-In-First-Out structure. Implement a stack data structure with fundamental operations.

Implement a stack (LIFO - Last In First Out) that supports: - push(x) - Add element x to top of stack - pop() - Remove and return top element - top() - Return top element without removing - empty() - Return true if stack is empty

Given a sequence of operations, return results for pop, top, and empty operations in order.

Real-World Application

Stacks are fundamental in: - Function call stack - managing function calls and returns - Undo/redo operations - text editors, graphics software - Browser history - back button navigation - Expression evaluation - parsing mathematical expressions - Syntax parsing - compilers, interpreters - Depth-first search - graph traversal algorithms - Backtracking - maze solving, puzzle solving - Memory management - stack memory allocation

Input

data = {
    'ops': List[List]  # List of operations
}

Operations format: - ['push', x] - Push value x onto stack - ['pop'] - Pop and return top value - ['top'] - Return top value - ['empty'] - Return whether stack is empty

Output

List[Any]  # Results of pop, top, and empty operations (in order)

Constraints

• 1 ≤ operations ≤ 100,000
• O(1) amortized time per operation
• Pop/top will not be called on empty stack
• Push operations don't produce output

Examples

Example 1: Basic Stack Operations

Input:

{
    'ops': [
        ['push', 1],
        ['push', 2],
        ['top'],       # Returns 2
        ['pop'],       # Returns 2
        ['empty']      # Returns False
    ]
}

Output: [2, 2, False]

Explanation: 1. push(1) - Stack: [1] 2. push(2) - Stack: [1, 2] 3. top() → 2 - Stack: [1, 2] (no change) 4. pop() → 2 - Stack: [1] 5. empty() → False - Stack still has 1 element

Example 2: Multiple Operations

Input:

{
    'ops': [
        ['push', 5],
        ['top'],       # Returns 5
        ['push', 7],
        ['pop'],       # Returns 7
        ['top']        # Returns 5
    ]
}

Output: [5, 7, 5]

Explanation: 1. push(5) - Stack: [5] 2. top() → 5 - Stack: [5] 3. push(7) - Stack: [5, 7] 4. pop() → 7 - Stack: [5] 5. top() → 5 - Stack: [5]

Example 3: Push and Pop Sequence

Input:

{
    'ops': [
        ['push', 1],
        ['push', 2],
        ['push', 3],
        ['pop'],       # Returns 3
        ['pop'],       # Returns 2
        ['pop'],       # Returns 1
        ['empty']      # Returns True
    ]
}

Output: [3, 2, 1, True]

Explanation: - Push 1, 2, 3 → Stack: [1, 2, 3] - Pop three times returns 3, 2, 1 (LIFO order) - Stack is now empty → True

Example 4: Checking Empty

Input:

{
    'ops': [
        ['empty'],     # Returns True
        ['push', 10],
        ['empty'],     # Returns False
        ['pop'],       # Returns 10
        ['empty']      # Returns True
    ]
}

Output: [True, False, 10, True]

What You'll Learn

• Implementing Abstract Data Types (ADTs)
• LIFO (Last-In-First-Out) principle
• Managing return values for different operations
• Using arrays/lists as underlying storage
• O(1) amortized operations

Why This Matters

Stack is a fundamental data structure that: - Tests understanding of LIFO principle - Appears in countless algorithms - Is basis for many interview questions - Demonstrates ADT implementation skills

Starter Code

def challenge_function(data):
    """
    Implement stack with push, pop, top, empty operations.

    Args:
        data: dict with key:
            - 'ops' (List[List]): list of operations
              ['push', x], ['pop'], ['top'], or ['empty']

    Returns:
        List[Any]: results of pop, top, and empty operations
    """
    # Your implementation here
    pass