#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Define a node using typedef
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Define a stack structure (optional wrapper)
typedef struct Stack {
    Node* top;
} Stack;

// Initialize the stack
void initStack(Stack* stack) {
    stack->top = NULL;
}

// Create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Push operation
void push(Stack* stack, int data) {
    Node* newNode = createNode(data);
    newNode->next = stack->top;
    stack->top = newNode;
    printf("Pushed %d onto stack.\n", data);
}

// Check if stack is empty
bool isEmpty(Stack* stack) {
    return stack->top == NULL;
}

// Pop operation
int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow! Cannot pop.\n");
        return -1;
    }
    Node* temp = stack->top;
    int poppedValue = temp->data;
    stack->top = temp->next;
    free(temp);
    printf("Popped %d from stack.\n", poppedValue);
    return poppedValue;
}

// Peek (view top element)
int peek(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty.\n");
        return -1;
    }
    return stack->top->data;
}

// Display the stack
void display(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty.\n");
        return;
    }
    printf("Stack (top → bottom): ");
    Node* temp = stack->top;
    while (temp) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// Free all stack nodes
void clearStack(Stack* stack) {
    Node* temp = stack->top;
    while (temp) {
        Node* next = temp->next;
        free(temp);
        temp = next;
    }
    stack->top = NULL;
}

// Main function to test
int main() {
    Stack stack;
    initStack(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    display(&stack);

    printf("Top element: %d\n", peek(&stack));

    pop(&stack);
    display(&stack);

    pop(&stack);
    pop(&stack);
    pop(&stack); // underflow

    clearStack(&stack);
    return 0;
}