Stacks in C — Detailed Lesson | Ananta Code Academy

📚 What is a Stack?

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle — the element inserted last is the one removed first. Think of a stack of plates: you always add a new plate on top, and you always pick up from the top. You cannot access the plate at the bottom without removing all the plates above it first.

In C, a stack is most commonly implemented using a fixed-size array with an integer variable called top that always holds the index of the topmost element. When the stack is empty, top = -1. Every push increments top and writes to arr[top]. Every pop reads from arr[top] and decrements top.

Stacks are used everywhere in computer science: function call management (the call stack), expression evaluation, bracket matching, undo/redo, backtracking algorithms, depth-first search, and syntax parsing in compilers.

push(val)

void push(Stack*, int)

Add element to the top. Check for overflow first. O(1).

pop()

int pop(Stack*)

Remove and return top element. Check for underflow first. O(1).

peek()

int peek(Stack*)

Return top element without removing it. O(1).

isEmpty()

int isEmpty(Stack*)

Returns 1 if top == -1 (empty), 0 otherwise. O(1).

isFull()

int isFull(Stack*)

Returns 1 if top == MAX-1 (full), 0 otherwise. O(1).

size()

int size(Stack*)

Returns top + 1 — the number of elements currently in the stack. O(1).

LIFO — last in, first out: push and pop always happen at the TOP

After push 10

10

·

← top=0

After push 20

10

20

·

← top=1

After push 30

10

20

30

·

← top=2

pop() → 30

10

20

·

← top=1, 30 returned

pop() → 20

10

·

← top=0, 20 returned

pop() → 10

·

← top=-1, stack empty

array memory layout — top pointer tracks the live boundary

arr[0..MAX-1]

10

20

30

40

·

← top = 3 (outline = top)

push formula

arr[++top] = val

← increment THEN write

pop formula

val = arr[top--]

← read THEN decrement

overflow cond.

top == MAX - 1

← no more room

underflow cond.

top == -1

← nothing to pop

All stack operations are O(1) — constant time regardless of how many elements are in the stack. There are no loops, no searching, no shifting. This is what makes stacks so powerful: they give you very fast access to the most recently added element at all times.

1

🏗️ Complete Array Stack — Every Operation Demonstrated

Build a full stack with push, pop, peek, isEmpty, isFull, size, display — then stress-test every edge case

Array Stack

This program builds a complete, production-quality array stack in C. The stack is implemented as a struct containing the data array and the top index. All six operations are implemented as separate functions that take a pointer to the struct. The main function demonstrates every operation — normal pushes, overflow detection, pop-all, underflow detection, and a visual display of the stack contents after every meaningful change. Every edge case is tested so you can see exactly what happens in each scenario.

stack_complete.c

C

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

#define MAX 6

/* ── Stack structure ── */
typedef struct {
    int data[MAX];
    int top;         /* index of topmost element; -1 = empty */
} Stack;

/* ── Initialise ── */
void initStack(Stack *s) {
    s->top = -1;
    printf("Stack initialised (capacity = %d)\n", MAX);
}

/* ── Predicates ── */
int isEmpty(Stack *s) { return s->top == -1; }
int isFull (Stack *s) { return s->top == MAX - 1; }
int size   (Stack *s) { return s->top + 1; }

/* ── Push: add element to top ── */
int push(Stack *s, int val) {
    if (isFull(s)) {
        printf("  OVERFLOW  — cannot push(%d), stack is full!\n", val);
        return 0;
    }
    s->data[++s->top] = val;
    printf("  push(%2d)  top=%d  size=%d\n",
           val, s->top, size(s));
    return 1;
}

/* ── Pop: remove and return top element ── */
int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("  UNDERFLOW — cannot pop, stack is empty!\n");
        return -1;
    }
    int val = s->data[s->top--];
    printf("  pop()  -> %2d  top=%d  size=%d\n",
           val, s->top, size(s));
    return val;
}

/* ── Peek: read top without removing ── */
int peek(Stack *s) {
    if (isEmpty(s)) {
        printf("  peek() — stack is empty!\n");
        return -1;
    }
    printf("  peek() -> %d  (top stays at %d)\n",
           s->data[s->top], s->top);
    return s->data[s->top];
}

/* ── Display: print stack top-to-bottom ── */
void display(Stack *s) {
    if (isEmpty(s)) {
        printf("  [stack is empty]\n");
        return;
    }
    printf("  Stack (TOP -> BOTTOM): ");
    for (int i = s->top; i >= 0; i--)
        printf("| %d ", s->data[i]);
    printf("|\n");
}

int main() {
    Stack s;
    initStack(&s);

    /* 1. Normal pushes */
    printf("\n--- Push 6 elements ---\n");
    push(&s, 10);
    push(&s, 25);
    push(&s, 38);
    push(&s, 47);
    push(&s, 56);
    push(&s, 62);
    display(&s);

    /* 2. Overflow */
    printf("\n--- Overflow test ---\n");
    push(&s, 99);

    /* 3. Peek */
    printf("\n--- Peek ---\n");
    peek(&s);

    /* 4. Size and full/empty status */
    printf("\n--- Status ---\n");
    printf("  size()    = %d\n", size(&s));
    printf("  isEmpty() = %d\n", isEmpty(&s));
    printf("  isFull()  = %d\n", isFull(&s));

    /* 5. Pop three elements */
    printf("\n--- Pop 3 elements ---\n");
    pop(&s);
    pop(&s);
    pop(&s);
    display(&s);

    /* 6. Push more after pop (reuse space) */
    printf("\n--- Push 2 more after pop ---\n");
    push(&s, 71);
    push(&s, 85);
    display(&s);

    /* 7. Drain the stack completely */
    printf("\n--- Drain all elements ---\n");
    while (!isEmpty(&s)) pop(&s);
    display(&s);

    /* 8. Underflow */
    printf("\n--- Underflow test ---\n");
    pop(&s);
    peek(&s);

    printf("\n=== Done ===\n");
    return 0;
}

output

Stack initialised (capacity = 6)

--- Push 6 elements ---
  push(10)  top=0  size=1
  push(25)  top=1  size=2
  push(38)  top=2  size=3
  push(47)  top=3  size=4
  push(56)  top=4  size=5
  push(62)  top=5  size=6
  Stack (TOP -> BOTTOM): | 62 | 56 | 47 | 38 | 25 | 10 |

--- Overflow test ---
  OVERFLOW  — cannot push(99), stack is full!

--- Peek ---
  peek() -> 62  (top stays at 5)

--- Status ---
  size()    = 6
  isEmpty() = 0
  isFull()  = 1

--- Pop 3 elements ---
  pop()  -> 62  top=4  size=5
  pop()  -> 56  top=3  size=4
  pop()  -> 47  top=2  size=3
  Stack (TOP -> BOTTOM): | 38 | 25 | 10 |

--- Push 2 more after pop ---
  push(71)  top=3  size=4
  push(85)  top=4  size=5
  Stack (TOP -> BOTTOM): | 85 | 71 | 38 | 25 | 10 |

--- Drain all elements ---
  pop()  -> 85  top=3  size=4
  pop()  -> 71  top=2  size=3
  pop()  -> 38  top=1  size=2
  pop()  -> 25  top=0  size=1
  pop()  -> 10  top=-1 size=0
  [stack is empty]

--- Underflow test ---
  UNDERFLOW — cannot pop, stack is empty!
  peek() — stack is empty!

=== Done ===

array layout at key moments — top pointer is the live boundary

After 6 pushes

10

25

38

47

56

62

← top=5, FULL

After 3 pops

10

25

38

47*

56*

62*

← stale bytes ignored, top=2

After 2 pushes

10

25

38

71

85

·

← top=4, reused slots

After drain

·

← top=-1, EMPTY

Pop does not erase memory. When you pop an element, top is decremented but the old value still sits in the array — it is just invisible to the stack logic because nothing looks past top. When you push again, the new value simply overwrites that slot. This is why stack operations are O(1) — there is zero cleanup work.

Return a sentinel value from pop on underflow. Returning -1 for an empty-stack pop is a common convention. The caller should always check isEmpty() before calling pop(), or check that the return value is not the sentinel. A safer design in production code uses a boolean output parameter or a tagged return struct instead of a magic number.

2

↩️ Undo / Redo Text Editor — Two Stacks Working Together

Every action is pushed onto the undo stack; undo moves it to the redo stack; redo moves it back — classic two-stack pattern

Real-World App

The undo/redo pattern is one of the most famous real-world applications of stacks. Two stacks work together: the undo stack holds the history of actions performed, and the redo stack holds actions that were undone. When the user performs a new action, it is pushed onto the undo stack and the redo stack is cleared. When the user undoes, the top of the undo stack is popped and pushed onto the redo stack. When the user redoes, the top of the redo stack is popped and pushed back onto the undo stack. This program simulates a simple text editor with five actions: TYPE, DELETE, FORMAT, INSERT, and PASTE.

undo_redo.c

C

#include <stdio.h>
#include <string.h>

#define MAX   10
#define DLEN  40

/* ── Action struct — what was done ── */
typedef struct {
    char type[12];   /* "TYPE", "DELETE", etc. */
    char data[DLEN];  /* the text involved      */
} Action;

/* ── Action Stack ── */
typedef struct {
    Action items[MAX];
    int    top;
} AStack;

void   as_init (AStack *s)            { s->top = -1; }
int    as_empty(AStack *s)            { return s->top == -1; }
int    as_full (AStack *s)            { return s->top == MAX-1; }
void   as_push (AStack *s, Action a)  { if(!as_full(s)) s->items[++s->top]=a; }
Action as_pop  (AStack *s)            { return s->items[s->top--]; }
Action as_peek (AStack *s)            { return s->items[s->top]; }

/* ── Pretty-print a stack ── */
void showStack(const char *name, AStack *s) {
    printf("  %-12s[ ", name);
    for (int i = 0; i <= s->top; i++)
        printf("%s:%s ", s->items[i].type, s->items[i].data);
    printf("%s]\n", s->top == -1 ? "(empty) " : "");
}

/* ── Editor operations ── */

void doAction(AStack *undo, AStack *redo,
              const char *type, const char *data) {
    Action a;
    strncpy(a.type, type, 11);
    strncpy(a.data, data, DLEN-1);
    /* New action clears the redo stack */
    as_init(redo);
    as_push(undo, a);
    printf("  ACTION   %s \"%s\"\n", type, data);
}

void doUndo(AStack *undo, AStack *redo) {
    if (as_empty(undo)) {
        printf("  UNDO     nothing to undo!\n");
        return;
    }
    Action a = as_pop(undo);
    as_push(redo, a);
    printf("  UNDO  <- %s \"%s\"  (moved to redo)\n",
           a.type, a.data);
}

void doRedo(AStack *undo, AStack *redo) {
    if (as_empty(redo)) {
        printf("  REDO     nothing to redo!\n");
        return;
    }
    Action a = as_pop(redo);
    as_push(undo, a);
    printf("  REDO  -> %s \"%s\"  (moved to undo)\n",
           a.type, a.data);
}

void status(AStack *undo, AStack *redo) {
    showStack("Undo stack:", undo);
    showStack("Redo stack:", redo);
    printf("\n");
}

int main() {
    AStack undo, redo;
    as_init(&undo); as_init(&redo);

    printf("=== Text Editor — Undo / Redo Demo ===\n\n");

    /* Perform 5 actions */
    printf("--- Perform 5 actions ---\n");
    doAction(&undo, &redo, "TYPE",   "Hello");
    doAction(&undo, &redo, "TYPE",   "World");
    doAction(&undo, &redo, "FORMAT", "Bold");
    doAction(&undo, &redo, "INSERT", "Image");
    doAction(&undo, &redo, "DELETE", "World");
    status(&undo, &redo);

    /* Undo 3 times */
    printf("--- Undo 3 times ---\n");
    doUndo(&undo, &redo);
    doUndo(&undo, &redo);
    doUndo(&undo, &redo);
    status(&undo, &redo);

    /* Redo 2 times */
    printf("--- Redo 2 times ---\n");
    doRedo(&undo, &redo);
    doRedo(&undo, &redo);
    status(&undo, &redo);

    /* New action clears redo */
    printf("--- New action (clears redo stack) ---\n");
    doAction(&undo, &redo, "PASTE", "Ananta");
    status(&undo, &redo);

    /* Try to redo after new action */
    printf("--- Try redo after new action ---\n");
    doRedo(&undo, &redo);

    /* Undo everything */
    printf("\n--- Undo everything ---\n");
    while (!as_empty(&undo)) doUndo(&undo, &redo);
    doUndo(&undo, &redo);   /* one more — should warn */
    status(&undo, &redo);
    return 0;
}

output

=== Text Editor — Undo / Redo Demo ===

--- Perform 5 actions ---
  ACTION   TYPE "Hello"
  ACTION   TYPE "World"
  ACTION   FORMAT "Bold"
  ACTION   INSERT "Image"
  ACTION   DELETE "World"
  Undo stack: [ TYPE:Hello TYPE:World FORMAT:Bold INSERT:Image DELETE:World ]
  Redo stack: [ (empty) ]

--- Undo 3 times ---
  UNDO  <- DELETE "World"  (moved to redo)
  UNDO  <- INSERT "Image"  (moved to redo)
  UNDO  <- FORMAT "Bold"   (moved to redo)
  Undo stack: [ TYPE:Hello TYPE:World ]
  Redo stack: [ DELETE:World INSERT:Image FORMAT:Bold ]

--- Redo 2 times ---
  REDO  -> FORMAT "Bold"   (moved to undo)
  REDO  -> INSERT "Image"  (moved to undo)
  Undo stack: [ TYPE:Hello TYPE:World FORMAT:Bold INSERT:Image ]
  Redo stack: [ DELETE:World ]

--- New action (clears redo stack) ---
  ACTION   PASTE "Ananta"
  Undo stack: [ TYPE:Hello TYPE:World FORMAT:Bold INSERT:Image PASTE:Ananta ]
  Redo stack: [ (empty) ]

--- Try redo after new action ---
  REDO     nothing to redo!

--- Undo everything ---
  UNDO  <- PASTE "Ananta"  (moved to redo)
  UNDO  <- INSERT "Image"  (moved to redo)
  UNDO  <- FORMAT "Bold"   (moved to redo)
  UNDO  <- TYPE "World"    (moved to redo)
  UNDO  <- TYPE "Hello"    (moved to redo)
  UNDO     nothing to undo!
  Undo stack: [ (empty) ]
  Redo stack: [ PASTE:Ananta INSERT:Image FORMAT:Bold TYPE:World TYPE:Hello ]

two-stack undo/redo state machine — how the stacks change at each step

Initial

Undo: empty

Redo: empty

5 actions done

Undo: [Hi|Wld|Fmt|Ins|Del] ←TOP

Redo: empty

After 3 undos

Undo: [Hi|Wld] ←TOP

Redo: [Del|Ins|Fmt] ←TOP

← 3 moved right

After 2 redos

Undo: [Hi|Wld|Fmt|Ins] ←TOP

Redo: [Del]

← 2 moved back

New action

Undo: [Hi|Wld|Fmt|Ins|Paste] ←TOP

Redo: CLEARED

← redo always wiped

The two-stack undo/redo pattern is used in every text editor, drawing app, and IDE. VS Code, Microsoft Word, Photoshop, and virtually every application with Ctrl+Z / Ctrl+Y uses exactly this approach. The key insight: undo pops from the undo stack and pushes to redo; redo does the reverse; a new action resets the redo stack so you cannot redo after making a new change.

New actions must clear the redo stack. If you type "Hello", undo it, then type "World", pressing Redo should do nothing — "Hello" is no longer a valid future state. Failing to clear the redo stack on new actions is a common bug that causes users to redo an action that logically should not exist anymore.

A stack is a LIFO structure — Last In, First Out. You can only add or remove elements from the top. All operations (push, pop, peek, isEmpty, isFull, size) are O(1).
Initialise with top = -1. Push uses arr[++top] = val — increment first, then write. Pop uses val = arr[top--] — read first, then decrement.
Always guard against overflow (top == MAX-1) before push, and underflow (top == -1) before pop. Skipping these guards causes silent buffer overflows or reading garbage values.
Pop does not erase memory — it only moves top down. The old value stays in the array until overwritten by a future push. The stack logic ignores anything past top.
Real-world use — Undo/Redo: perform action → push to undo stack, clear redo. Undo → pop from undo, push to redo. Redo → pop from redo, push to undo. New action always clears redo.
Other classic stack applications: bracket matching (push opens, pop on close), postfix evaluation (push numbers, pop two on operator), function call management (call stack), DFS graph traversal, and compiler syntax parsing.

Stacks in C —Deep Dive

📚 What is a Stack?

Stacks in C —
Deep Dive