Stacks

A stack is a linear data structure that follows LIFO order: Last In, First Out. The last value inserted is the first value removed.

Think of a stack as a pile of plates. You add a new plate on the top, and you also remove from the top. You do not remove from the middle.

Why Do We Need Stacks?

A stack is useful when a program must remember work in reverse order. The most recent item is usually the most urgent item to handle next.

Without a stack, we would often need extra logic to search for the “latest unfinished thing.” A stack gives that rule directly:

latest inserted item -> first item removed

That rule appears in many computing problems:

• A function call must return to the most recent caller.
• An undo command must reverse the most recent action first.
• A parser must match the most recently opened bracket first.
• A backtracking algorithm must return to the most recent decision point.

The stack is not mainly about storing many values. Arrays and linked lists can already store many values. The stack is about controlling access order.

Real-Life Uses

• Pile of plates: the last plate placed on top is the first plate removed.
• Stack of books: removing from the top is natural; removing from the middle disturbs the stack.
• Undo history: the most recent change is undone first.
• Browser back button: the most recently visited previous page is opened first.
• Call center script rollback: the last completed step is usually the first one reversed when correcting a mistake.

Computer Uses

• Function call stack: every function call stores local variables, parameters, return address, and saved state.
• Recursion: recursive calls work because each call gets its own stack frame.
• Expression evaluation: postfix expressions and many calculators use stacks for operands.
• Syntax checking: compilers use stacks to check brackets, scopes, and nested structures.
• Depth-first search: DFS stores the most recently discovered path first.
• Backtracking: maze solving, puzzle solving, and recursive search use stack-like behavior.
• Undo/redo systems: editors, IDEs, drawing tools, and spreadsheets store recent operations in stacks.

The two fundamental operations are:

• push(x): add x to the top
• pop(): remove and return the top value

Other useful operations are:

• peek(): read the top value without removing it
• is_empty(): check whether the stack has no values
• is_full(): check whether a fixed array stack has no free space
• display(): print the stack for learning/debugging

The core invariant is simple: only the top is directly accessible. If an operation needs access to the bottom or middle, it is no longer a stack operation.

As an abstract data type, a stack usually exposes only push, pop, peek, is_empty, and sometimes size. Hiding the internal representation is part of the point. A caller should not care whether the stack is backed by an array, a linked list, or a fixed memory pool.

Operation Trace

Start with an empty stack:

top
---
empty

Apply:

push(10), push(20), push(30), pop(), push(40)

The logical stack becomes:

top -> 40
       20
       10

The removed value was 30.

Array Stack: Fixed Size

The easiest implementation uses a fixed-size array and a global integer top.

This version uses the beginner-friendly convention:

• top == -1 means the stack is empty.
• top == SIZE - 1 means the stack is full.
• stack[top] is the current top element.

index: 0   1   2   3   4
data:  10  20  30
top = 2

Array Stack: Function-by-Function

#include <stdio.h>

#define SIZE 5

int stack[SIZE];
int top = -1;

#include <stdio.h> allows the program to use printf.

#define SIZE 5 fixes the maximum number of stack elements. Because this is an array implementation, the stack cannot grow beyond this limit.

int stack[SIZE]; stores the actual stack values.

int top = -1; tracks the current top position. The value -1 means no valid array index exists yet, so the stack is empty.

void push(int value) {
    if (top == SIZE - 1) {
        printf("Stack Overflow\n");
    } else {
        top++;
        stack[top] = value;
        printf("%d pushed into stack\n", value);
    }
}

push(value) inserts a new value at the top. It first checks whether top == SIZE - 1. If true, the array is full. Otherwise, it increases top and stores the new value at stack[top].

The order of the two update lines matters:

top++;
stack[top] = value;

At the beginning, top is -1, which is not a valid array index. The function must increase top first, so the first pushed value goes to index 0.

Example:

Before push(10): top = -1
After top++:     top = 0
Store value:     stack[0] = 10

If the overflow check is skipped, pushing into a full stack writes outside the array. That is a serious memory error in C.

void pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
    } else {
        printf("%d popped from stack\n", stack[top]);
        top--;
    }
}

pop() removes the top value. It first checks whether the stack is empty. If not, it prints stack[top] and decreases top.

The value is printed before top-- because stack[top] is the current top element. After decreasing top, the old value is no longer considered part of the stack.

Example:

stack: 10 20 30
top = 2

pop prints stack[2] = 30
top becomes 1

logical stack: 10 20

The old value may still physically remain in the array, but it is ignored because top no longer points to it. In stack logic, the active part of the array is from index 0 to top.

void peek() {
    if (top == -1) {
        printf("Stack is empty\n");
    } else {
        printf("Top element: %d\n", stack[top]);
    }
}

peek() shows the top value without removing it. Notice that top does not change in this function.

Use peek() when a program needs to inspect the next item but is not ready to delete it. For example, an expression parser may check the top operator before deciding whether to pop it.

If peek() changed top, it would become a pop() operation. That is why the function only reads stack[top].

void displayStack() {
    if (top == -1) {
        printf("Stack is empty\n");
    } else {
        printf("Stack elements: ");
        for (int i = top; i >= 0; i--) {
            printf("%d ", stack[i]);
        }
        printf("\n");
    }
}

displayStack() prints from top down to index 0, because stack order is top-to-bottom.

This display order is chosen for teaching. It shows the element that would be popped first at the left side of the output.

For example, after push(10), push(20), push(30), display prints:

30 20 10

That does not mean the array stores 30 at index 0. The array stores 10, 20, 30; the display function simply prints from top to bottom.

int main() {
    push(10);
    push(20);
    push(30);

    displayStack();
    peek();
    pop();

    displayStack();

    return 0;
}

main() tests the stack operations in sequence. After pushing 10, 20, and 30, the top value is 30.

The purpose of main() here is not to solve a separate problem. It is a small driver program that proves the operations work:

• push adds values.
• displayStack shows the current stack.
• peek reads the top value.
• pop removes the top value.
• displayStack confirms the new state.

Array Stack: Full Code

#include <stdio.h>

#define SIZE 5

int stack[SIZE];
int top = -1;

void push(int value) {
    if (top == SIZE - 1) {
        printf("Stack Overflow\n");
    } else {
        top++;
        stack[top] = value;
        printf("%d pushed into stack\n", value);
    }
}

void pop() {
    if (top == -1) {
        printf("Stack Underflow\n");
    } else {
        printf("%d popped from stack\n", stack[top]);
        top--;
    }
}

void peek() {
    if (top == -1) {
        printf("Stack is empty\n");
    } else {
        printf("Top element: %d\n", stack[top]);
    }
}

void displayStack() {
    if (top == -1) {
        printf("Stack is empty\n");
    } else {
        printf("Stack elements: ");
        for (int i = top; i >= 0; i--) {
            printf("%d ", stack[i]);
        }
        printf("\n");
    }
}

int main() {
    push(10);
    push(20);
    push(30);

    displayStack();
    peek();
    pop();

    displayStack();

    return 0;
}

This version prints the popped value directly. If another algorithm needs to use the popped value, change pop to return an int or use an output parameter.

Multiple Array Stacks

The global version is best for learning one stack. If a program needs multiple stacks, global variables are not enough because all operations would use the same stack array and the same top.

For multiple stacks, place the array and top inside a struct:

#include <stdio.h>

#define SIZE 5

typedef struct {
    int data[SIZE];
    int top;
} Stack;

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

void push(Stack *s, int value) {
    if (s->top == SIZE - 1) {
        printf("Stack Overflow\n");
    } else {
        s->top++;
        s->data[s->top] = value;
    }
}

void pop(Stack *s) {
    if (s->top == -1) {
        printf("Stack Underflow\n");
    } else {
        printf("%d popped\n", s->data[s->top]);
        s->top--;
    }
}

Now each stack has its own storage and top:

Stack undoStack;
Stack redoStack;

initStack(&undoStack);
initStack(&redoStack);

push(&undoStack, 10);
push(&redoStack, 99);

Use the global version when teaching the idea. Use the struct version when a program needs more than one stack.

Overflow and Underflow

Overflow happens when push is called on a full fixed-capacity stack.

if top == SIZE - 1, no more array slots are available

Underflow happens when pop is called on an empty stack.

if top == -1, there is no value to remove

Good stack code checks both conditions before accessing the array.

Array Stack: Dynamic Size

A fixed array is easy to learn, but its capacity is limited. A dynamic array stack grows when it becomes full.

The idea is:

if size == capacity:
    allocate a bigger array
    copy old values into it
    continue push

This makes push amortized O(1). Most pushes are constant time, but a resize occasionally costs O(n).

Linked Stack

A linked-list stack stores the top at the head of a singly linked list.

Why the head? Because inserting and deleting at the head are both O(1).

This version uses the same style as the linked-list chapter: functions return the updated top pointer.

Linked Stack: Function-by-Function

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

stdio.h is needed for printf. stdlib.h is needed for malloc and free.

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

Each node stores one stack value. data stores the value, and next points to the node below it.

Node *createNode(int data) {
    Node *newNode = malloc(sizeof(Node));

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return NULL;
    }

    newNode->data = data;
    newNode->next = NULL;

    return newNode;
}

createNode(data) creates one new node. It allocates memory, stores the data, sets next to NULL, and returns the new node address.

This function keeps node creation in one place. Without it, every insertion function would need to repeat the same malloc, error check, data assignment, and next initialization.

The newNode == NULL check is important. If memory allocation fails and the program still tries to use newNode->data, the program may crash.

Node *push(Node *top, int data) {
    Node *newNode = createNode(data);

    if (newNode == NULL) {
        return top;
    }

    newNode->next = top;
    top = newNode;

    return top;
}

push(top, data) inserts a new node at the top. The new node points to the old top, then the new node becomes the updated top. The caller must write top = push(top, data);.

The key pointer change is:

newNode->next = top;
top = newNode;

This preserves the old stack below the new node. If top = newNode were done first, the program would lose the address of the old top unless it had been saved somewhere else.

Example:

Before push(30):
top -> 20 -> 10 -> NULL

After newNode->next = top:
30 -> 20 -> 10 -> NULL

After top = newNode:
top -> 30 -> 20 -> 10 -> NULL

Node *pop(Node *top) {
    if (top == NULL) {
        printf("Stack Underflow\n");
        return NULL;
    }

    Node *temp = top;
    printf("%d popped\n", temp->data);

    top = top->next;
    free(temp);

    return top;
}

pop(top) removes the first node. It saves the current top in temp, moves top to the next node, frees the removed node, and returns the updated top.

The temporary pointer is necessary:

Node *temp = top;
top = top->next;
free(temp);

If the code moved top first without saving the old node, the program would lose the address of the node that must be freed. That creates a memory leak.

The function returns top because removing the first node changes the starting point of the stack. The caller must store the returned value.

void peekStack(Node *top) {
    if (top == NULL) {
        printf("Stack is empty\n");
    } else {
        printf("Top element: %d\n", top->data);
    }
}

peekStack(top) prints the top node’s data without changing the stack.

This is the linked-list version of array peek(). It reads top->data but does not move top and does not free any node.

void displayStack(Node *top) {
    if (top == NULL) {
        printf("Stack is empty\n");
        return;
    }

    Node *current = top;

    printf("Stack: ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }

    printf("\n");
}

displayStack(top) traverses from top to bottom and prints each node.

The traversal uses a separate pointer named current, not top. That matters because displayStack should inspect the stack, not destroy it.

Node *current = top;

If the function moved top directly, the caller’s stack could be lost in designs where top is passed by address. Using current is the safe habit.

void freeStack(Node *top) {
    while (top != NULL) {
        Node *temp = top;
        top = top->next;
        free(temp);
    }
}

freeStack(top) releases all remaining nodes before the program ends.

This is not a stack operation from the abstract data type; it is memory cleanup for C programs. Every node created by malloc should eventually be released by free.

int main(void) {
    Node *top = NULL;

    top = push(top, 10);
    top = push(top, 20);
    top = push(top, 30);

    displayStack(top);
    peekStack(top);

    top = pop(top);

    displayStack(top);
    freeStack(top);

    return 0;
}

main() creates an empty linked stack using Node *top = NULL, pushes three values, peeks, pops once, displays again, and frees the remaining nodes.

Linked Stack: Full Code

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

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

Node *createNode(int data) {
    Node *newNode = malloc(sizeof(Node));

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return NULL;
    }

    newNode->data = data;
    newNode->next = NULL;

    return newNode;
}

Node *push(Node *top, int data) {
    Node *newNode = createNode(data);

    if (newNode == NULL) {
        return top;
    }

    newNode->next = top;
    top = newNode;

    return top;
}

Node *pop(Node *top) {
    if (top == NULL) {
        printf("Stack Underflow\n");
        return NULL;
    }

    Node *temp = top;
    printf("%d popped\n", temp->data);

    top = top->next;
    free(temp);

    return top;
}

void peekStack(Node *top) {
    if (top == NULL) {
        printf("Stack is empty\n");
    } else {
        printf("Top element: %d\n", top->data);
    }
}

void displayStack(Node *top) {
    if (top == NULL) {
        printf("Stack is empty\n");
        return;
    }

    Node *current = top;

    printf("Stack: ");
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }

    printf("\n");
}

void freeStack(Node *top) {
    while (top != NULL) {
        Node *temp = top;
        top = top->next;
        free(temp);
    }
}

int main(void) {
    Node *top = NULL;

    top = push(top, 10);
    top = push(top, 20);
    top = push(top, 30);

    displayStack(top);
    peekStack(top);

    top = pop(top);

    displayStack(top);
    freeStack(top);

    return 0;
}

This version has strict O(1) push and pop with no resizing. The trade-off is that every value needs a separately allocated node and one extra pointer.

Multiple Linked Stacks

For linked stacks, each stack only needs its own top pointer:

Node *undoTop = NULL;
Node *redoTop = NULL;

undoTop = push(undoTop, 10);
redoTop = push(redoTop, 99);

undoTop = pop(undoTop);

The nodes reachable from undoTop form one stack. The nodes reachable from redoTop form another stack.

Array vs Linked Stack

Call Stack

Function calls are managed with a stack. Each active function call has a stack frame containing parameters, local variables, return address, and saved registers. Recursion works because every recursive call receives its own frame.

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Calling factorial(5) pushes frames for 5, 4, 3, 2, and 1. The base case returns first, then frames pop in reverse order. Deep recursion can overflow the call stack, which is why iterative versions or explicit stacks are sometimes required.

Balanced Parentheses

A stack checks whether delimiters are properly nested.

The idea is:

1. Read the expression from left to right.
2. Push every opening bracket: (, {, [.
3. When a closing bracket appears, pop the most recent opening bracket.
4. If the pair does not match, the expression is invalid.
5. At the end, the stack must be empty.

The algorithm works because the most recent unclosed opener must be the first one closed. For a full balanced-parentheses program, pop should return the popped bracket instead of only printing it.

Postfix Evaluation

Postfix notation writes the operator after its operands: 3 4 2 * + means 3 + (4 * 2). A stack evaluates postfix expressions in one left-to-right scan.

The idea is:

1. If the token is an operand, push it.
2. If the token is an operator, pop two operands.
3. Apply the operator.
4. Push the result back.
5. After the full expression is processed, the final answer is on the top of the stack.

The order of popping matters for subtraction and division: the first popped value is the right operand.

Infix Conversion

The shunting-yard algorithm uses a stack to hold operators until it is safe to output them. Higher-precedence operators leave the stack before lower-precedence ones.

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

The full parser must also handle parentheses and multi-digit numbers, but the central invariant is simple: the operator stack contains operations whose left operand has been seen but whose right side is not ready to emit yet.

Costs

When to Use a Stack

• managing function calls
• undo and redo histories
• DFS and backtracking
• syntax parsing
• expression evaluation
• reversing sequences
• converting recursive algorithms to iterative algorithms

Pitfalls

• Popping before checking whether the stack is empty
• Confusing top as next free slot vs current top index
• Forgetting to free linked-list nodes after popping or at program end
• Forgetting that a - b and a / b require operand order
• Exposing array internals and letting callers bypass stack rules
• Using recursion without considering call-stack depth

Exercises

1. Trace this sequence on an empty stack: push(5), push(8), pop(), push(2), push(9), pop(). Show the final stack and the popped values.
2. Rewrite the fixed-array stack using the other convention: top == -1 means empty and data[top] is the current top item.
3. Add a linked_stack_size function that counts the number of nodes.
4. Explain why inserting into the middle of the linked list would violate the stack abstraction.
5. Use a stack to check whether {[()()]} is balanced.
6. Implement both stack versions and test push, pop, peek, underflow, and empty checks.
7. Trace the stack contents while evaluating 5 1 2 + 4 * + 3 -.
8. Explain why stack operations are not suitable for searching the middle element.