A dynamic stack grows its storage automatically when full by creating a bigger array and copying items over.
Analogy: Imagine a stack of plates on a small tray. When the tray is full, you get a bigger tray and move all plates there so you can keep stacking more.
Stack array: [1, 2, 3, _, _]
Top index: ↑3 (points to next free slot)
Capacity: 5
Dry Run Walkthrough
Input: Push values 1, 2, 3, 4, 5, 6 onto an initially empty stack with capacity 4
Goal: Show how the stack resizes when pushing the 5th element and continues pushing
#include <stdio.h>#include <stdlib.h>
typedef struct {
int *array;
int top;
int capacity;
} DynamicStack;
DynamicStack *createStack(int capacity) {
DynamicStack *stack = malloc(sizeof(DynamicStack));
stack->capacity = capacity;
stack->top = 0;
stack->array = malloc(sizeof(int) * capacity);
return stack;
}
void resizeStack(DynamicStack *stack) {
int newCapacity = stack->capacity * 2;
int *newArray = malloc(sizeof(int) * newCapacity);
for (int i = 0; i < stack->top; i++) {
newArray[i] = stack->array[i]; // copy old elements
}
free(stack->array);
stack->array = newArray;
stack->capacity = newCapacity;
}
void push(DynamicStack *stack, int value) {
if (stack->top == stack->capacity) {
resizeStack(stack); // resize when full
}
stack->array[stack->top] = value;
stack->top++;
}
int pop(DynamicStack *stack) {
if (stack->top == 0) {
printf("Stack is empty\n");
return -1; // error value
}
stack->top--;
return stack->array[stack->top];
}
void printStack(DynamicStack *stack) {
for (int i = 0; i < stack->top; i++) {
printf("%d", stack->array[i]);
if (i < stack->top - 1) printf(" -> ");
}
printf(" -> null\n");
}
int main() {
DynamicStack *stack = createStack(4);
push(stack, 1);
push(stack, 2);
push(stack, 3);
push(stack, 4);
push(stack, 5); // triggers resize
push(stack, 6);
printStack(stack);
free(stack->array);
free(stack);
return0;
}
if (stack->top == stack->capacity) { resizeStack(stack); }
resize stack array when full to double capacity
stack->array[stack->top] = value; stack->top++;
add new element at top index and increment top
for (int i = 0; i < stack->top; i++) { newArray[i] = stack->array[i]; }
copy old elements to new larger array
OutputSuccess
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Complexity Analysis
Time: O(n) for resizing steps because copying all elements; O(1) amortized for push otherwise
Space: O(n) for the array storing n elements
vs Alternative: Compared to fixed size stack, dynamic stack avoids overflow by resizing but uses extra time during resize
Edge Cases
Push on empty stack
Stack adds element at index 0 without resizing
DSA C
if (stack->top == stack->capacity) { resizeStack(stack); }
Push exactly at capacity triggers resize
Stack doubles capacity and copies elements before adding new one
DSA C
if (stack->top == stack->capacity) { resizeStack(stack); }
Pop from empty stack
Prints 'Stack is empty' and returns -1
DSA C
if (stack->top == 0) { printf("Stack is empty\n"); return -1; }
When to Use This Pattern
When you need a stack that can grow beyond a fixed size without errors, use a dynamic stack with resizing to handle unknown or large input sizes.
Common Mistakes
Mistake: Not resizing the array when full causes overflow or memory errors Fix: Check if top equals capacity before push and resize array by copying elements to a bigger array
Summary
It implements a stack that grows automatically by resizing its array when full.
Use it when you want a stack but don't know the maximum number of elements in advance.
The key insight is to double the array size and copy elements to avoid overflow while keeping push efficient on average.
