Array-Based Stack Implementation

Every array has a finite size. No matter how large you allocate, there's always a capacity limit. This raises a fundamental question for array-based stacks: What happens when you push onto a full stack?

This question divides stack implementations into two camps:

1. Static (fixed-capacity) stacks: Accept the limit and fail when exceeded
2. Dynamic (auto-resizing) stacks: Grow the underlying array when needed

Both approaches are valid, each with distinct trade-offs. Understanding these trade-offs is essential for making informed engineering decisions about which implementation suits your use case.

This page explores both approaches in depth, introduces the powerful concept of amortized analysis for understanding dynamic array costs, and provides clear guidance for choosing between them.

A static stack uses a fixed-size array allocated once at construction. The capacity never changes.

Structure:

class StaticStack {
    private array: Element[];
    private top: number = 0;
    private readonly capacity: number;
    
    constructor(capacity: number) {
        this.capacity = capacity;
        this.array = new Array(capacity);
    }
}

The overflow problem:

When top reaches capacity, the next push cannot proceed. The stack is full:

capacity = 4
top = 4 (next push would go to index 4, but array only has indices 0-3)
array: [10][20][30][40]
                     ↑
                   FULL - no more room

Handling overflow:

There are several strategies for handling this condition:

1. Throw an exception: Clear signal that capacity was exceeded
2. Return a failure indicator: Boolean return value or error code
3. Silently ignore: Dangerous—caller doesn't know the push failed
4. Crash/assert: Appropriate for debugging, not production

When static stacks are appropriate:

1. Known maximum size: If you can guarantee the stack will never exceed n elements, a static stack of capacity n is optimal.

2. Real-time systems: Dynamic resizing introduces unpredictable latency (the occasional O(n) resize). Real-time systems that require bounded latency prefer static allocation.

3. Embedded systems: Limited memory environments often pre-allocate all resources at startup. Dynamic allocation is avoided or prohibited.

4. Performance-critical inner loops: When every nanosecond matters, avoiding resize checks and potential allocations helps.

5. Memory-constrained environments: You know exactly how much memory the stack uses—no surprises.

A dynamic stack automatically increases its capacity when full. Instead of failing on overflow, it allocates a larger array, copies existing elements, and continues.

The resize operation:

void push(Element x) {
    if (top >= capacity) {
        resize(capacity * 2);  // Double the capacity
    }
    array[top++] = x;
}

void resize(int newCapacity) {
    Element[] newArray = new Element[newCapacity];
    for (int i = 0; i < top; i++) {
        newArray[i] = array[i];  // Copy all elements
    }
    array = newArray;
    capacity = newCapacity;
}

Visual representation:

Before resize (full, capacity = 4):
array: [10][20][30][40]   top = 4

push(50) triggers resize:

New array (capacity = 8):
newArray: [10][20][30][40][ _ ][ _ ][ _ ][ _ ]

After copying and push:
array: [10][20][30][40][50][ _ ][ _ ][ _ ]   top = 5, capacity = 8

Why doubling?

The key insight is that by doubling the capacity each time (rather than adding a fixed amount), we ensure that expensive resizes happen exponentially less often:

After n pushes, we've done ~log₂(n) resizes, copying 1 + 2 + 4 + ... + n/2 ≈ n total elements. Spread over n pushes, that's n/n = 1 copy per push on average!

Amortized analysis is a technique for analyzing the average cost per operation over a sequence of operations, even when individual operations have varying costs.

For dynamic stacks, single push operations can be:

• O(1): Most pushes (when no resize needed)
• O(n): Occasional pushes (when resize triggers)

The question is: what's the average cost when we consider a long sequence of pushes?

The accounting method:

Imagine each push "pays" 3 units of work:

• 1 unit for the actual push operation
• 2 units "saved" for future resizing

When we resize from n to 2n:

• We need to copy n elements (n units of work)
• We have n elements in the stack, each having "saved" 2 units = 2n units saved
• Cost: n, Budget: 2n → We can afford it with n units left over!

Since every operation pays a constant (3 units), the amortized cost is O(1).

Mathematical proof:

Let's prove push is O(1) amortized with doubling:

Claim: n push operations on an initially empty dynamic stack cost O(n) total, giving O(1) amortized per push.

Proof:

Total work = (work for pushes) + (work for resizes)

• Work for n pushes: n × O(1) = O(n)

• Work for resizes: We resize when pushing element 1, 2, 3, 5, 9, 17, ... (powers of 2 + 1)

  • At size 1: copy 0 elements
  • At size 2: copy 1 element
  • At size 4: copy 2 elements
  • At size 8: copy 4 elements
  • ...
  • At size n: copy n/2 elements

  Total copies = 0 + 1 + 2 + 4 + 8 + ... + n/2 = n - 1 = O(n)

Total work = O(n) + O(n) = O(n)

Amortized cost per push = O(n) / n = O(1) ∎

Why not add a constant?

If we add a constant k slots each resize, the analysis changes:

• Resize at: k, 2k, 3k, ..., n/k times
• Work per resize: k, 2k, 3k, ...
• Total work: k + 2k + 3k + ... = k × (1 + 2 + 3 + ... + n/k) = O(n²/k) = O(n²)

This makes push O(n) amortized—unacceptable for large stacks.

Resizing up is half the story. What about when elements are popped? Should we shrink the array to reclaim memory?

The naive approach (don't do this):

void pop() {
    if (top <= 0) throw EmptyStackException();
    Element x = array[--top];
    if (top == capacity / 2) {
        resize(capacity / 2);  // Shrink when half empty
    }
    return x;
}

The thrashing problem:

Imagine the stack has capacity 8 and 4 elements. We're right at the threshold:

1. push(5) → capacity stays 8, top = 5
2. pop() → top = 4, top == capacity/2, RESIZE to 4
3. push(5) → top = 5 >= capacity = 4, RESIZE to 8
4. pop() → top = 4 == capacity/2 = 4, RESIZE to 4
5. push(5) → RESIZE to 8...

Every pair of operations triggers resizing! This is called thrashing and destroys performance.

The correct shrinking strategy:

void pop() {
    if (top <= 0) throw EmptyStackException();
    Element x = array[--top];
    // Shrink when quarter full (not half full!)
    if (top > 0 && top == capacity / 4) {
        resize(capacity / 2);
    }
    return x;
}

Why quarter-full works:

After shrinking, the array is half full. To trigger a grow, we need to push until full (double the current size). To trigger another shrink, we need to pop until quarter-full (half the current size). Either way, we do many operations before the next resize.

Invariant with correct resizing:

• After a resize, array is 25%-50% full
• Need at least n/2 operations before next resize
• Amortized cost remains O(1)

Dynamic resizing affects memory usage in important ways:

Space overhead with doubling:

When using the doubling strategy, up to 50% of allocated memory might be unused:

After pushing element n (where n = 2^k + 1 for some k):
  Capacity: 2^(k+1)
  Used: 2^k + 1
  Wasted: 2^(k+1) - 2^k - 1 ≈ 50%

For a stack of 1,000,001 elements, capacity is 2,097,152 → ~50% wasted.

Reducing wasted space:

1. Use 1.5× growth factor: Reduces max waste to ~33%, still O(1) amortized
2. Shrink aggressively: Reclaim memory when usage drops
3. Right-size on construction: If you know approximate size, start there
4. Use Java-style ArrayList: Grows by 50%, good balance
5. Accept the trade-off: 50% extra memory for O(1) operations is often worthwhile

Memory allocation considerations:

1. Allocation overhead: Each resize calls the memory allocator. Modern allocators are optimized, but allocation has overhead (metadata, fragmentation, system calls).

2. Copying cost: Resizing copies all elements. For large elements (objects with many fields), this is expensive. For primitives or pointers, it's fast.

3. Reference types: In garbage-collected languages, the old array becomes garbage after resize. GC must eventually reclaim it, adding latency.

4. Realloc optimization: Some languages/allocators can extend an allocation in-place without copying (C's realloc). This optimization is allocator-dependent and not guaranteed.

Choosing between static and dynamic stacks requires understanding your requirements. Here's a comprehensive comparison:

Let's examine how different languages and libraries handle this:

JavaScript Arrays (dynamic):

const stack = [];
stack.push(1);  // Dynamic growth, O(1) amortized
stack.push(2);
stack.pop();    // No auto-shrink (manual if needed)

JavaScript arrays grow automatically. V8 (Chrome's engine) uses complex heuristics for growth, typically 1.5x or 2x.

Python Lists (dynamic):

stack = []
stack.append(1)  # Over-allocates for efficiency
stack.append(2)
stack.pop()      # No auto-shrink

Python's list over-allocates using a formula that grows roughly 12.5% at small sizes and tends toward the golden ratio at larger sizes.

Java ArrayDeque (dynamic):

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);  // Grows by doubling
stack.push(2);
stack.pop();    // No auto-shrink

ArrayDeque doubles capacity when full. It's the recommended stack implementation in Java (not the legacy Stack class).

C++ std::stack (configurable):

std::stack<int> s;  // Default: std::deque (hybrid)
std::stack<int, std::vector<int>> sv;  // Vector-backed

C++ lets you choose the underlying container. std::vector grows by 1.5x or 2x (implementation-defined).

Custom implementation with configurable strategy:

class FlexibleStack<T> {
    private array: T[];
    private top: number = 0;
    private capacity: number;
    private readonly growthFactor: number;
    private readonly shrinkThreshold: number;
    
    constructor(
        initialCapacity: number = 16,
        growthFactor: number = 2,
        shrinkThreshold: number = 0.25
    ) {
        this.capacity = initialCapacity;
        this.growthFactor = growthFactor;
        this.shrinkThreshold = shrinkThreshold;
        this.array = new Array(initialCapacity);
    }
    
    push(element: T): void {
        if (this.top >= this.capacity) {
            this.resize(Math.floor(this.capacity * this.growthFactor));
        }
        this.array[this.top++] = element;
    }
    
    pop(): T | undefined {
        if (this.top <= 0) return undefined;
        const element = this.array[--this.top];
        this.array[this.top] = undefined as any;  // Prevent memory leak
        
        // Shrink if below threshold and not too small
        if (this.top < this.capacity * this.shrinkThreshold && 
            this.capacity > 16) {
            this.resize(Math.floor(this.capacity / this.growthFactor));
        }
        return element;
    }
}

This implementation allows customization while maintaining correct amortized behavior.

We've thoroughly explored how array-based stacks handle the fundamental constraint of finite array capacity. Both static and dynamic approaches have their place, and understanding when to use each is essential engineering knowledge.

Module Complete!

Congratulations! You've now mastered array-based stack implementation from the ground up:

1. Page 1: Why arrays are ideal for stacks
2. Page 2: Top pointer management and conventions
3. Page 3: O(1) complexity proof for push/pop
4. Page 4: Overflow handling with static and dynamic approaches

You can now implement stacks in any language with complete understanding of the underlying mechanics, trade-offs, and best practices. In the next module, we'll explore how linked lists provide an alternative implementation with different characteristics.