Data Structure - Stack

#include <stdio.h>
#include <stdbool.h> /* bool type */

#define MAX_SIZE 100 /* Maximum capacity of the stack */

/* Stack structure: contains data array and top pointer */
struct Stack {
    int items[MAX_SIZE];  /* Array storing stack elements */
    int top;              /* Top pointer, -1 means the stack is empty */
};

/* Initialize stack: set top to -1 */
void initStack(struct Stack* s) {
    s->top = -1;
}

/* Check empty: stack is empty when top is -1 */
bool isEmpty(struct Stack* s) {
    return s->top == -1;
}

/* Check full: stack is full when top reaches capacity limit -1 */
bool isFull(struct Stack* s) {
    return s->top == MAX_SIZE - 1;
}

/* Push: place an element on top of the stack
First move top, then write the data */
void push(struct Stack* s, int value) {
    if (isFull(s)) {
        printf("Stack is full, cannot push!\n");
        return;
    }
    s->items[++s->top] = value;  /* top increments by 1 first, then assign value */
    printf("Push: %d\n", value);
}

/* Pop: remove and return the top element
First retrieve the data, then move top */
int pop(struct Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty, cannot pop!\n");
        return -1;  /* Return a special value to indicate an error */
    }
    return s->items[s->top--];  /* Return the value first, then decrement top */
}

/* Peek: does not pop, only views the top */
int peek(struct Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->items[s->top];
}

int main() {
    struct Stack s;
    initStack(&s);

    push(&s, 10);  /* Push: 10 */
    push(&s, 20);  /* Push: 20 */
    push(&s, 30);  /* Push: 30 */

    printf("Top element: %d\n", peek(&s));  /* Output: top element: 30 */

    printf("Pop: %d\n", pop(&s));        /* Output: pop: 30 (last in, first out) */
    printf("Pop: %d\n", pop(&s));        /* Output: pop: 20 */
    printf("Pop: %d\n", pop(&s));        /* Output: pop: 10 */

    if (isEmpty(&s)) {
        printf("Stack is empty\n");                /* Output: stack is empty */
    }
    return 0;
}

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

/* Linked list node */
struct Node {
    int data;
    struct Node* next;
};

/* Push: uses the linked list head as the stack top, head insertion method
Time complexity: O(1) */
struct Node* push(struct Node* top, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = top;   /* New node points to the original stack top */
    printf("Push: %d\n", value);
    return newNode;          /* New node becomes the new stack top */
}

/* Pop: remove the head node of the linked list
Time complexity: O(1) */
struct Node* pop(struct Node* top) {
    if (top == NULL) {
        printf("Stack is empty!\n");
        return NULL;
    }
    struct Node* temp = top;
    printf("Popped: %d\n", top->data);
    top = top->next;   /* Move top back */
    free(temp);         /* Free old top */
    return top;
}

/* Check if empty */
bool isEmpty(struct Node* top) {
    return top == NULL;
}

int main() {
    struct Node* stackTop = NULL;  /* Initially stack is empty */

    stackTop = push(stackTop, 100);  /* Push: 100 */
    stackTop = push(stackTop, 200);  /* Push: 200 */
    stackTop = push(stackTop, 300);  /* Push: 300 */

    printf("Top: %d\n", stackTop->data);  /* Output: Top: 300 */

    stackTop = pop(stackTop);  /* Pop: 300 */
    stackTop = pop(stackTop);  /* Pop: 200 */
    stackTop = pop(stackTop);  /* Pop: 100 */

    if (isEmpty(stackTop)) {
        printf("Stack is empty\n");      /* Output: Stack is empty */
    }
    return 0;
}