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 task

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).

Challenge 2

push and pop are written for you. Add int peek(const Stack *s), which returns the top item without removing it, int is_empty(const Stack *s), and int size(const Stack *s).

Challenge 3

Use the stack to check brackets. Write int balanced(const char *s) that returns 1 if every (, [ and { in s is closed by the matching bracket in the right order, and 0 otherwise. Other characters are ignored. "a[b(c)]{}" is balanced, "([)]" is not.

Previous: Reverse a linked list