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.

Everyday LIFO

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

Software Stacks

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

Stack Trace

Use the stack below before reading the implementation. Push until the fixed capacity is full, pop until it is empty, and observe that only one end ever changes.

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 fixed-array version uses the current-top 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(void) {
    push(10);
    push(20);
    push(30);

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

    displayStack();

    return 0;
}

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

The purpose of main(void) 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(void) {
    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(void) 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.

Undo History

An undo system normally uses two stacks. Performing an action stores a command capable of reversing it on the undo stack. Undo pops the newest command, applies its inverse, and pushes the command onto the redo stack. Redo performs the mirror operation. If the user undoes work and then performs a new action, the old redo stack is cleared because that former future no longer follows the current state.

Command records often own strings, snapshots, or other allocated payloads. Popping transfers that ownership to the caller or to the opposite stack; clearing or destroying a stack must release every payload it still owns. Merely setting an array stack’s size to zero is insufficient when its inactive records own resources.

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.

For { a * [b + (c - d)] }, the stack changes only when a delimiter appears:

A closing token is valid only when the stack is non-empty and its top has the corresponding type. Reaching the end with remaining openings is also an error; avoiding an early mismatch alone is not sufficient.

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.

Stack Costs

Choosing Stacks

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

Stack Hazards

• 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

Stack Practice

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 next-free convention: top == 0 means empty, data[top - 1] is the current top item, push writes before incrementing, and pop decrements before reading.
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.

Stack Contract

The stack abstraction should expose behavior rather than its array index or node links:

push(value)       add one value at the top
pop(out)          remove the top value into out
peek(out)         copy the top value without removal
is_empty()        report whether no values are stored
size()            report the number of stored values

pop and peek should report failure on an empty stack without changing state. Printing an underflow message inside the data structure couples it to one user interface; returning a status lets a caller print, retry, propagate the error, or take another action.

For an array stack whose field records the number of elements, the invariant is:

0 <= size <= capacity
indices [0, size) contain values from bottom to top
the top is data[size - 1] when size > 0
data[size] is the next free slot when size < capacity

For a linked stack:

size == 0 if and only if top == NULL
following next from top reaches exactly size nodes
the first reachable node is the logical top

These conventions avoid ambiguity about whether a variable named top means the current top index or the next free index.

Dynamic Stack

A dynamic array stack retains the locality of array storage while growing geometrically. This complete program reports allocation and underflow failures through return values:

#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} DynamicStack;

static bool dynamic_stack_valid(const DynamicStack *stack) {
    if (stack == NULL || stack->size > stack->capacity) {
        return false;
    }
    if (stack->capacity == 0) {
        return stack->data == NULL;
    }
    return stack->data != NULL;
}

static void dynamic_stack_init(DynamicStack *stack) {
    stack->data = NULL;
    stack->size = 0;
    stack->capacity = 0;
}

static void dynamic_stack_destroy(DynamicStack *stack) {
    free(stack->data);
    dynamic_stack_init(stack);
}

static bool dynamic_stack_reserve(DynamicStack *stack, size_t capacity) {
    if (capacity <= stack->capacity) {
        return true;
    }
    if (capacity > SIZE_MAX / sizeof *stack->data) {
        return false;
    }

    int *new_data = realloc(stack->data,
                            capacity * sizeof *stack->data);
    if (new_data == NULL) {
        return false;
    }

    stack->data = new_data;
    stack->capacity = capacity;
    return true;
}

static bool dynamic_stack_push(DynamicStack *stack, int value) {
    assert(dynamic_stack_valid(stack));
    if (stack->size == stack->capacity) {
        size_t next = stack->capacity == 0 ? 8 : stack->capacity * 2;
        if (next < stack->capacity ||
            !dynamic_stack_reserve(stack, next)) {
            return false;
        }
    }

    stack->data[stack->size] = value;
    stack->size++;
    assert(dynamic_stack_valid(stack));
    return true;
}

static bool dynamic_stack_pop(DynamicStack *stack, int *out) {
    assert(dynamic_stack_valid(stack));
    if (stack->size == 0 || out == NULL) {
        return false;
    }

    *out = stack->data[stack->size - 1];
    stack->size--;
    assert(dynamic_stack_valid(stack));
    return true;
}

static bool dynamic_stack_peek(const DynamicStack *stack, int *out) {
    assert(dynamic_stack_valid(stack));
    if (stack->size == 0 || out == NULL) {
        return false;
    }

    *out = stack->data[stack->size - 1];
    return true;
}

int main(void) {
    DynamicStack stack;
    dynamic_stack_init(&stack);

    if (!dynamic_stack_push(&stack, 10) ||
        !dynamic_stack_push(&stack, 20) ||
        !dynamic_stack_push(&stack, 30)) {
        dynamic_stack_destroy(&stack);
        return EXIT_FAILURE;
    }

    int value;
    if (dynamic_stack_peek(&stack, &value)) {
        printf("top=%d\n", value);
    }
    while (dynamic_stack_pop(&stack, &value)) {
        printf("%d ", value);
    }
    printf("\n");

    dynamic_stack_destroy(&stack);
    return EXIT_SUCCESS;
}

Most pushes write one slot and cost O(1). A growing push copies O(n) values. Across a long sequence of pushes, doubling keeps total copying linear, so push is amortized O(1). It is not strict worst-case O(1); fixed storage is preferable when every operation needs a hard latency bound.

The stack normally retains capacity after pop. Shrinking on every pop can alternate allocation and copying when usage hovers near a boundary.

Prefix Evaluation

Prefix notation places an operator before its operands:

+ 5 * 2 3

This means 5 + (2 * 3). Evaluate prefix from right to left:

1. Push every operand.
2. When an operator appears, pop the left operand first and the right operand second.
3. Compute left operator right and push the result.
4. After all tokens, exactly one result must remain.

token from right    stack
3                   [3]
2                   [3, 2]
*                   [6]
5                   [6, 5]
+                   [11]

Operand order is the mirror of postfix processing. In postfix scanned left to right, the first popped value is the right operand. In prefix scanned right to left, the first popped value is the left operand.

A real evaluator tokenizes multi-digit and signed numbers before stack processing. The characters -12 may form one negative operand, while - by itself may be a binary operator.

Prefix Conversion

Infix-to-prefix conversion must preserve precedence, associativity, and parentheses. One reliable method uses a stack of partial expressions:

1. Read operands and push their expression representation.
2. Keep operators on an operator stack using the same precedence rules as infix-to-postfix conversion.
3. When an operator becomes ready, pop its right expression, then its left expression.
4. Form operator left right and push the combined expression.

For (a + b) * c:

left expression:  + a b
right expression: c
combined prefix:  * + a b c

Exponentiation and other right-associative operators need different equal-precedence handling from left-associative subtraction or division. Right-associative means that a ^ b ^ c groups as a ^ (b ^ c); left-associative subtraction groups a - b - c as (a - b) - c. Parentheses control when operators become ready; they do not appear in the final prefix form.

Expression Validity

An expression processor should reject more than mismatched parentheses. Invalid states include:

• a closing delimiter with no stored opener;
• a closing delimiter whose type differs from the top opener;
• an operator with too few operands;
• extra operands remaining after the final operator;
• an unknown token;
• division by zero;
• numeric overflow under the evaluator’s chosen arithmetic rules.

The final stack state is part of validation. One result means a complete expression; zero or several values mean the token sequence was incomplete or malformed.

Batch Push

Pushing several values raises a useful failure question. Suppose a dynamic stack contains [10, 20] and the caller requests [30, 40, 50]. If growth fails after two separate pushes, should the result be [10, 20, 30, 40], or should the stack remain [10, 20]?

Both contracts are possible:

partial contract: push until one value fails; report how many succeeded
atomic contract:  either push every value or change nothing

For an atomic batch of plain integers, calculate the required final size, reserve enough space once, and only then copy values and publish the new size. Check both addition and byte-count overflow before allocation:

static bool dynamic_stack_push_all(DynamicStack *stack,
                                   const int values[], size_t count) {
    assert(dynamic_stack_valid(stack));
    if ((values == NULL && count != 0) ||
        count > SIZE_MAX - stack->size) {
        return false;
    }

    size_t needed = stack->size + count;
    if (needed > stack->capacity) {
        size_t capacity = stack->capacity == 0 ? 8 : stack->capacity;
        while (capacity < needed) {
            if (capacity > SIZE_MAX / 2) {
                capacity = needed;
                break;
            }
            capacity *= 2;
        }
        if (!dynamic_stack_reserve(stack, capacity)) {
            return false;
        }
    }

    for (size_t i = 0; i < count; i++) {
        stack->data[stack->size + i] = values[i];
    }
    stack->size = needed;
    assert(dynamic_stack_valid(stack));
    return true;
}

If values may point inside stack->data, a successful reserve can relocate the allocation and invalidate it. The API must forbid that overlap or take a source snapshot before reserving, just as a vector bulk insertion does. Even a simple LIFO container needs clear alias and failure contracts when operations become bulk operations.

Frame Records

Replacing recursion with an explicit stack requires storing everything a suspended call needs, not merely its input value. For a binary-tree postorder traversal, a frame might contain:

typedef struct {
    const TreeNode *node;
    unsigned char phase;
} TraversalFrame;

phase acts like the hidden instruction position inside the recursive function:

0: left child has not been processed
1: left is complete; right has not been processed
2: both children are complete; process this node

For a parser, the frame may instead need an expected closing token, partial result, and source position. For a search with choices, it may need the next alternative to try. A correct explicit stack is therefore a stack of continuation state: the information required to resume suspended work exactly where it stopped.

This viewpoint helps debug iterative conversions. If the iterative form cannot decide what to do after popping a frame, some state that recursion kept implicitly is missing from the record.

Explicit stacks offer controllable capacity and heap allocation, but they do not remove the underlying space requirement. A depth-h process still needs O(h) frames. The benefit is that overflow can be checked and reported instead of abruptly exhausting the language runtime’s call stack.

History Bounds

An undo stack often needs a memory limit. Simply rejecting a new action when the stack is full preserves ordinary stack semantics but may be inconvenient. Dropping the oldest action accepts the newest history at the price of becoming a different bounded structure.

capacity 3, oldest to newest: [A, B, C]
record D: destroy A, retain [B, C, D]

An array that shifts [B, C] left on every overflow pays O(n) per new action. A circular buffer stores the oldest position and overwrites it in O(1), while exposing push/pop only at the logical newest end. Internally it resembles a deque even though its public use is a bounded history stack.

When records own payloads, overwriting must call the discarded record’s destructor first. Undoing transfers the newest record to the redo stack; performing a new action clears and destroys the redo records. If pushing onto redo can fail, define whether the action remains undone, is restored to undo, or uses pre-reserved capacity so the transfer cannot fail midway.

The lesson is not that every stack should be circular. It is that capacity policy changes observable behavior and may justify a different internal representation.

Stack Oracles

A fixed test array plus an integer size is a simple reference model. Generate pushes, pops, and peeks, apply them to both implementations, and compare status, returned value, size, and the complete bottom-to-top sequence after every step.

Bias tests toward empty, singleton, exactly full, one beyond full, and each dynamic growth boundary. For record stacks, use payload objects with counters so tests prove that every owned object is destroyed exactly once. Force allocation failure during node creation, array growth, and atomic batch push; the previous top and every existing value must remain unchanged under the stated contract.

Application tests need their own invariants. A delimiter checker should report the first mismatch position. An evaluator should end with exactly one value. Undo and redo stacks should never simultaneously own the same command record. These checks test the meaning layered above LIFO order rather than assuming correct push/pop makes the whole application correct.

Stack Representations

Fixed storage is the right choice when a hard maximum and predictable latency matter. A dynamic array is the usual general-purpose representation because it is compact and allocation is occasional. A linked stack is useful when stable nodes or incremental allocation matter more than locality. “A linked stack cannot overflow” is inaccurate: it has no fixed structural capacity, but push still fails when memory cannot be allocated.

Stack Testing

Test empty pop and peek, the first push, the singleton-to-empty transition, exact fixed capacity, one push beyond capacity, dynamic growth at several boundaries, and repeated push/pop cycles. For linked storage, verify that every popped node is released and that allocation failure preserves the former top. Expression tests should include reversed subtraction/division operands, mismatched delimiter types, too few operands, extra operands, unknown tokens, division by zero, and a valid result equal to an ordinary sentinel-like value such as -1.

Stack Challenges

Operand Order

1. Explain why postfix evaluation computes left operator right even though it pops right first.

Prefix Trace

2. Trace both the value stack and every operand order while evaluating - + 12 5 * 3 4 as prefix.

Stack Applications

3. Extend the dynamic stack with clear, size, and peek, then test allocation failure and empty operations.
4. Implement balanced-delimiter checking that reports the position and expected type of the first mismatch.
5. Tokenize and evaluate postfix expressions containing multi-digit signed integers.
6. Implement prefix evaluation and test subtraction and division cases that reveal reversed operands.

Command Ownership

7. Store command records in undo and redo stacks, including ownership and cleanup of command payloads.

Expression Conversion

8. Convert infix expressions to both postfix and prefix while handling unary minus, parentheses, and a right-associative exponent operator.

Specialized Stacks

9. Maintain the current minimum in constant time while preserving constant-time push and pop.
10. Implement an explicit stack of frames that replaces a recursive tree traversal and records exactly the state each suspended call needs.
11. Store dynamically allocated command payloads in undo and redo stacks, then test transfer, clear, and failure ownership.
12. Design a bounded history stack that overwrites its oldest record when full and explain why its behavior differs from an ordinary stack contract.