Stack using dynamic array

A dynamic array stack still stores elements in one contiguous block and uses a top index, but the block grows on the heap (for example with realloc) when it runs out of room. Push and pop at the top stay O(1) in the usual case; growing is O(n) when it happens, so push is O(1) amortized if you double the capacity each resize. This page keeps top == -1 for empty and grows before push when top + 1 == capacity.

1) Representation

You still need a contiguous place for values, the top index, and how many slots are currently allocated (capacity). The storage is typically an int * (or similar) pointing at the first element of a heap-allocated array; logical “array” operations use buf[0] .. buf[top].

2) Mapping operations to the array

Push checks whether another element would exceed capacity; if so, grow (often double the capacity), then increment top and assign. Pop and peek match the fixed-array case; shrinking the buffer on pop is optional and less common in simple stacks.

3) Example in C

Below, one stack lives at file scope: a heap buffer, top, and capacity. The API uses no struct and no pointer parameters in main; stack_last holds the result of a successful peek or pop. INITIAL_CAPACITY is 1 so the second push triggers a grow in the trace tables.

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

#define INITIAL_CAPACITY 1

/* Heap-backed array: valid indices 0..top; top == -1 means empty. */
static int *stack;
static int top;
static int capacity;

/* After stack_peek or stack_pop returns 1, read the value from here. */
static int stack_last;

/* Double capacity (or start at 1); returns 0 if realloc fails. */
static int grow_stack(void) {
    int new_cap = capacity == 0 ? 1 : capacity * 2;
    int *p = realloc(stack, (size_t)new_cap * sizeof *p);
    if (p == NULL)
        return 0;
    stack = p;
    capacity = new_cap;
    return 1;
}

void stack_init(void) {
    top = -1;
    stack = malloc((size_t)INITIAL_CAPACITY * sizeof *stack);
    if (stack == NULL) {
        capacity = 0;
        return;
    }
    capacity = INITIAL_CAPACITY;
}

void stack_destroy(void) {
    free(stack);
    stack = NULL;
    top = -1;
    capacity = 0;
}

int stack_is_empty(void) {
    return top < 0;
}

/* Returns 1 on success, 0 if out of memory. */
int stack_push(int value) {
    if (top + 1 >= capacity) {
        if (!grow_stack())
            return 0;
    }
    top++;
    stack[top] = value;
    return 1;
}

/* Returns 1 on success, 0 if underflow. */
int stack_pop(void) {
    if (stack_is_empty())
        return 0;
    stack_last = stack[top];
    top--;
    return 1;
}

/* Returns 1 on success, 0 if underflow. */
int stack_peek(void) {
    if (stack_is_empty())
        return 0;
    stack_last = stack[top];
    return 1;
}

int main(void) {
    stack_init();

    stack_push(10);
    stack_push(20);

    if (stack_peek())
        printf("peek: %d\n", stack_last);

    if (stack_pop())
        printf("pop: %d\n", stack_last);

    stack_destroy();
    return 0;
}

The buffer type can be changed from int; production code often wraps these fields in a struct or uses a growable “vector” type so you can have multiple stacks.

Explanation of the program output

Here’s the explanation of the program’s output in table format. INITIAL_CAPACITY is 1, so the second push grows the buffer before storing 20.

Key points

4) Trade-offs

• Pros — No fixed compile-time cap; contiguous memory and good cache locality; push/pop still simple at the top.
• Cons — realloc may copy the whole block when growing; occasional O(n) cost; you must free the buffer; wasted capacity if you shrink rarely.

Compare with a fixed array stack when the max size is known, or a linked-list stack if you want growth without reallocating a contiguous block. Operation definitions are on Stack operations.