1. Requirement

• Define the push function: Adds a node to the top of the stack
• Define the stack_at function: Returns the value of the n-th element from the top of the stack.

2. Solution

• The push function: Create a new Node, Node.next is old linked list, increase size by 1. New linked list starts with newly created node.
• The stack_at function: if n = 0, return value of the first element in list. If n > 0, use recursion with n-1 and pointer to next element.

3. Souce code

func push(stack: Node*, value: felt) -> (stack: Node*) {
    alloc_locals;
    local new_node: Node;
    // Fix and uncomment below.
    assert new_node.next = stack;
    assert new_node.value = value;
    assert new_node.size = stack.size + 1;

    let (__fp__, _) = get_fp_and_pc();
    return (stack=&new_node);
}

func stack_at(stack: Node*, n: felt) -> (value: felt) {
    if (n == 0) {
        return (value = stack.value);
    }

    return stack_at(stack.next, n - 1);
}

My answer to the challenge

//
// Add the missing code so that main() runs successfully.

from starkware.cairo.common.registers import get_fp_and_pc

struct Node {
    // A pointer to the next node in the stack.
    next: Node*,

    // The value of the node.
    value: felt,

    // The number of elements in the stack.
    size: felt,
}

// Returns an empty stack.
func empty_stack() -> (stack: Node*) {
    alloc_locals;
    local new_node: Node;
    assert new_node.next = cast(0, Node*);
    assert new_node.value = 0;
    assert new_node.size = 0;

    // The usage of get_fp_and_pc() here is necessary in order
    // to access the address of a local variable (&new_node).
    // You can read more about get_fp_and_pc() [here](https://cairo-lang.org/docs/how_cairo_works/functions.html#retrieving-registers).
    let (local __fp__, _) = get_fp_and_pc();
    return (stack=&new_node);
}

// Adds a node to the top of the stack.
// Returns the updated stack (since Cairo is immutable, you can still use the
// old copy of the stack).
func push(stack: Node*, value: felt) -> (stack: Node*) {
    alloc_locals;
    local new_node: Node;
    // Fix and uncomment below.
    assert new_node.next = stack;
    assert new_node.value = value;
    assert new_node.size = stack.size +1;

    let (__fp__, _) = get_fp_and_pc();
    return (stack=&new_node);
}

// Removes the top element of the stack.
// Returns the updated stack and the element that was removed.
func pop(stack: Node*) -> (stack: Node*, value: felt) {
    return (stack=stack.next, value=stack.value);
}

// Returns the value of the n-th element from the top of the stack.
func stack_at(stack: Node*, n: felt) -> (value: felt) {
    alloc_locals;
    if (n == 0) {
        return (value = stack.value);
    }

    // Add your code here.
    let (local val) = stack_at(stack=stack.next, n=n - 1);
    return (value=val);

}

func main() -> () {
    alloc_locals;
    // Start with an empty stack.
    let (stack) = empty_stack();
    // Push 1, 10, 100.
    let (stack) = push(stack, 1);
    let (stack) = push(stack, 10);
    let (local stack) = push(stack, 100);

    // Check the size of the stack.
    assert stack.size = 3;

    // Query the stack at indices 0, 1 and 2.
    let (value) = stack_at(stack, 0);
    assert value = 100;
    let (value) = stack_at(stack, 1);
    assert value = 10;
    let (value) = stack_at(stack, 2);
    assert value = 1;

    // Pop the top 2 values (100 and 10) and push 1000.
    let (stack, value) = pop(stack);
    assert value = 100;
    let (stack, value) = pop(stack);
    assert value = 10;
    let (local stack) = push(stack, 1000);

    // Query the stack at indices 0 and 1.
    let (value) = stack_at(stack, 0);
    assert value = 1000;
    let (value) = stack_at(stack, 1);
    assert value = 1;

    return ();
}

Solution

// In this challenge you're going to implement a stack using a linked list.
//
// Add the missing code so that main() runs successfully.

from starkware.cairo.common.registers import get_fp_and_pc

struct Node {
    // A pointer to the next node in the stack.
    next: Node*,

    // The value of the node.
    value: felt,

    // The number of elements in the stack.
    size: felt,
}

// Returns an empty stack.
func empty_stack() -> (stack: Node*) {
    alloc_locals;
    local new_node: Node;
    assert new_node.next = cast(0, Node*);
    assert new_node.value = 0;
    assert new_node.size = 0;

    // The usage of get_fp_and_pc() here is necessary in order
    // to access the address of a local variable (&new_node).
    // You can read more about get_fp_and_pc() [here](https://cairo-lang.org/docs/how_cairo_works/functions.html#retrieving-registers).
    let (local __fp__, _) = get_fp_and_pc();
    return (stack=&new_node);
}

// Adds a node to the top of the stack.
// Returns the updated stack (since Cairo is immutable, you can still use the
// old copy of the stack).
func push(stack: Node*, value: felt) -> (stack: Node*) {
    alloc_locals;
    local new_node: Node;
    assert new_node.next = stack;
    assert new_node.value = value;
    assert new_node.size = stack.size+1;

    let (__fp__, _) = get_fp_and_pc();
    return (stack=&new_node);
}

// Removes the top element of the stack.
// Returns the updated stack and the element that was removed.
func pop(stack: Node*) -> (stack: Node*, value: felt) {
    return (stack=stack.next, value=stack.value);
}

// Returns the value of the n-th element from the top of the stack.
func stack_at(stack: Node*, n: felt) -> (value: felt) {
alloc_locals;
    if (n == 0) {
        return (value=stack.value);
  }
    let (local val) = stack_at(stack=stack.next, n=n - 1);
    return (value=val);
}

func main() -> () {
    alloc_locals;
    // Start with an empty stack.
    let (stack) = empty_stack();
    // Push 1, 10, 100.
    let (stack) = push(stack, 1);
    let (stack) = push(stack, 10);
    let (local stack) = push(stack, 100);

    // Check the size of the stack.
    assert stack.size = 3;

    // Query the stack at indices 0, 1 and 2.
    let (value) = stack_at(stack, 0);
    assert value = 100;
    let (value) = stack_at(stack, 1);
    assert value = 10;
    let (value) = stack_at(stack, 2);
    assert value = 1;

    // Pop the top 2 values (100 and 10) and push 1000.
    let (stack, value) = pop(stack);
    assert value = 100;
    let (stack, value) = pop(stack);
    assert value = 10;
    let (local stack) = push(stack, 1000);

    // Query the stack at indices 0 and 1.
    let (value) = stack_at(stack, 0);
    assert value = 1000;
    let (value) = stack_at(stack, 1);
    assert value = 1;

    return ();
}