C Data Structures: Stacks & Queues — Array vs Linked List Implementations Masterclass

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

#define STACK_MAX 100

typedef struct {
    int data[STACK_MAX];
    int top;         /* Index of top element; -1 = empty */
} Stack;

void  stack_init(Stack *s)       { s->top = -1; }
bool  stack_empty(const Stack *s){ return s->top == -1; }
bool  stack_full(const Stack *s) { return s->top == STACK_MAX - 1; }

bool  stack_push(Stack *s, int v) {
    if (stack_full(s)) return false;
    s->data[++s->top] = v;
    return true;
}

bool stack_pop(Stack *s, int *out) {
    if (stack_empty(s)) return false;
    *out = s->data[s->top--];
    return true;
}

int stack_peek(const Stack *s) { return s->data[s->top]; }

/* Application: Check balanced brackets */
bool is_balanced(const char *expr) {
    Stack s; stack_init(&s);
    for (int i = 0; expr[i]; i++) {
        if (expr[i]=='('||expr[i]=='['||expr[i]=='{') {
            stack_push(&s, expr[i]);
        } else if (expr[i]==')'||expr[i]==']'||expr[i]=='}') {
            if (stack_empty(&s)) return false;
            int top; stack_pop(&s, &top);
            if ((expr[i]==')' && top!='(')||
                (expr[i]==']' && top!='[')||
                (expr[i]=='}' && top!='{')) return false;
        }
    }
    return stack_empty(&s);
}

int main(void) {
    printf("is_balanced(\"[(){()}]\") = %s\n", is_balanced("[(){()}]") ? "YES" : "NO");
    printf("is_balanced(\"[(])\")     = %s\n", is_balanced("[(])") ? "YES" : "NO");
    return 0;
}