Step 6 of 6

A stack on an array

A stack is a collection with two operations: push adds an item on top, pop removes the top item. The last item in is the first out (LIFO), like a pile of plates. Stacks are everywhere: the call stack that holds function frames, undo history, and parsing nested brackets.

You could build one from a linked list (push and pop at the front), but the simplest version uses an array plus a counter:

typedef struct {
    int items[64];
    int top;        /* how many items are stored; also the next free index */
} Stack;

• The items live in items[0] to items[top - 1], and the top of the stack is items[top - 1].
• push: store at items[top], then increment top.
• pop: decrement top, then return items[top].
• Empty when top == 0; full when top == 64.

#include <stdio.h>

typedef struct {
    char items[32];
    int top;
} CharStack;

int balanced(const char *s) {
    CharStack st = {.top = 0};
    for (; *s; s++) {
        if (*s == '(') {
            if (st.top == 32) return 0;
            st.items[st.top++] = '(';
        } else if (*s == ')') {
            if (st.top == 0) return 0;
            st.top--;
        }
    }
    return st.top == 0;
}

int main(void) {
    printf("%d %d %d\n", balanced("(a(b)c)"), balanced("(()"), balanced(")("));
    return 0;
}

1 0 0

This checks whether parentheses are balanced: push on (, pop on ). A ) with nothing to pop, or anything left over at the end, means unbalanced. Note st.items[st.top++] = '(': it stores at the current top and then increments, which is push in one line.

Always check capacity before pushing into a fixed array; writing items[64] would overflow.

Your turn: implement push (return 0 if full, 1 if ok) and pop (return the top item and remove it; the caller guarantees the stack isn't empty).

Previous: Reverse a linked list