Stack

Data Structures O(1) push/pop O(n)

LIFO container: push and pop happen at the same end, so the last element in is the first one out.

27← top

Pick an operation to walk through the code.

Invariant`top` indexes the most recently pushed item — the only one that can be removed.

stack.c

#define MAX 100
 
typedef struct {
    int items[MAX];
    int top;          /* -1 when empty */
} Stack;
 
void push(Stack *s, int value) {
    if (s->top == MAX - 1) return;   /* overflow */
    s->items[++s->top] = value;
}
 
int pop(Stack *s) {
    if (s->top == -1) return -1;     /* underflow */
    return s->items[s->top--];
}
 
int peek(const Stack *s) {
    return s->items[s->top];
}

How Stack works

Last in, first out. Push and pop touch only the top, so both are constant-time; nothing below the top is ever inspected.

When to use it

Undo histories, call stacks, matching brackets, DFS, expression evaluation.