C Stack: Push, Pop, Peek

A stack is LIFO — last in, first out. Push adds to the top; pop removes from the top; peek inspects without removing. Implemented as an array with a top index.

Stacks are everywhere in computing — function calls, undo stacks, expression evaluation, depth-first search. The implementation is simple: an array plus an index that tracks the top.

The basic shape

#include <stdio.h>

#define MAX 10

typedef struct {
  int items[MAX];
  int top;
} Stack;

void init(Stack *s) {
  s->top = -1;
}

int is_empty(Stack *s) {
  return s->top == -1;
}

int is_full(Stack *s) {
  return s->top == MAX - 1;
}

void push(Stack *s, int value) {
  if (is_full(s)) {
    printf("Stack overflow!\n");
    return;
  }
  s->items[++s->top] = value;
}

int pop(Stack *s) {
  if (is_empty(s)) {
    printf("Stack underflow!\n");
    return -1;
  }
  return s->items[s->top--];
}

int peek(Stack *s) {
  if (is_empty(s)) return -1;
  return s->items[s->top];
}

The Stack struct

typedef struct {
  int items[MAX];
  int top;
} Stack;

• items — fixed-size array storage.
• top — index of the topmost element. -1 means empty (no valid index).

top = -1 initially. push first increments, then assigns: items[++top] = value. pop returns then decrements: items[top--].

init — reset the stack

void init(Stack *s) {
  s->top = -1;
}

We don't zero items — they're treated as garbage until pushed. Only top matters for "empty" checks.

push and pop — the core

void push(Stack *s, int value) {
  if (is_full(s)) return;
  s->items[++s->top] = value;
}

int pop(Stack *s) {
  if (is_empty(s)) return -1;
  return s->items[s->top--];
}

Pre-increment in push: ++top first, then items[top] gets the new value. Post-decrement in pop: read items[top], then top--.

These are O(1) — single array access plus an increment.

peek — inspect without removing

int peek(Stack *s) {
  if (is_empty(s)) return -1;
  return s->items[s->top];
}

Returns the top item without changing top. Useful for "is the next operation valid given what's on top?" checks.

is_empty / is_full

Distinguish "stack has values" from "stack is fresh." Without these checks, pop or push on the wrong state corrupts memory.

int is_empty(Stack *s) { return s->top == -1; }
int is_full(Stack *s) { return s->top == MAX - 1; }

Returning -1 vs better error handling

Returning -1 from pop is a signal that the stack was empty. But what if -1 is a valid value?

For typed stacks, return a status code separately:

int pop(Stack *s, int *out) {
  if (is_empty(s)) return -1;   // error code
  *out = s->items[s->top--];
  return 0;   // success
}

int value;
if (pop(&stack, &value) == 0) {
  // use value
}

Cleaner than mixing data and error in the return.

Dynamic-size stack

For a stack that can grow:

typedef struct {
  int *items;
  int top;
  int capacity;
} DynStack;

void init(DynStack *s, int initial_capacity) {
  s->items = malloc(initial_capacity * sizeof(int));
  s->top = -1;
  s->capacity = initial_capacity;
}

void push(DynStack *s, int value) {
  if (s->top + 1 == s->capacity) {
    s->capacity *= 2;
    s->items = realloc(s->items, s->capacity * sizeof(int));
  }
  s->items[++s->top] = value;
}

Doubles capacity when full. Episode 56 explores this dynamic-array pattern in depth.

Stack via linked list

Alternative implementation:

typedef struct StackNode {
  int data;
  struct StackNode *next;
} StackNode;

typedef struct {
  StackNode *top;
} Stack;

void push(Stack *s, int value) {
  StackNode *n = malloc(sizeof(*n));
  n->data = value;
  n->next = s->top;
  s->top = n;
}

int pop(Stack *s) {
  if (s->top == NULL) return -1;
  StackNode *n = s->top;
  int value = n->data;
  s->top = n->next;
  free(n);
  return value;
}

Each push allocates; each pop frees. No fixed capacity. Slightly slower per operation than the array form (malloc/free overhead).

Real uses of stacks

Function call stack. Every function call pushes a frame; return pops. Recursion runs on this.

Expression evaluation. Shunting-yard algorithm uses two stacks (operators + values) to convert infix to postfix and evaluate.

Depth-first search. Maintain a stack of "to visit" nodes; pop, process, push neighbors.

Undo/redo. Each action pushes onto an undo stack; redo pops from one and pushes onto the other.

Parsing. Match parentheses by pushing on '(' and popping on ')'.

int balanced(const char *s) {
  Stack stack;
  init(&stack);
  for (; *s; s++) {
    if (*s == '(') push(&stack, *s);
    else if (*s == ')') {
      if (is_empty(&stack)) return 0;
      pop(&stack);
    }
  }
  return is_empty(&stack);
}

Classic interview problem.

Common mistakes

Forgetting the bounds check. push without is_full overflows the array. Catastrophic.

Mixed pre/post increment. items[top++] writes at current top then increments — so first push goes to index 0 (with top starting at 0), but then the next push tries to read items[0] again. Be consistent: items[++top] = ... (pre-increment) or top++; items[top] = ....

Confusing peek with pop. Peek doesn't remove; pop does.

Treating "stack" data structure as same as "the stack" (memory region). Different concepts; only related by FIFO/LIFO.

No init call. Stack s; without init(&s) leaves top as garbage. Always init.

Off-by-one in linked-list version. Pushing/popping from head is the LIFO behavior; tail-based would be FIFO (queue).

What's next

Episode 47: queue — enqueue, dequeue, circular array. FIFO instead of LIFO.

Recap

Stack = LIFO. top index tracks the last-pushed element (-1 for empty). push increments top then writes; pop reads then decrements; peek reads without changing. All O(1). Always check is_full before push, is_empty before pop. For dynamic size, use a growing array (with realloc) or linked list. Real uses: function calls, expression eval, depth-first search, undo, parenthesis matching.

Next episode: queue.