Array-Based Stack Implementation

The array-based stack is celebrated for its efficiency—specifically, the guarantee that push and pop operations execute in O(1) time. But what exactly makes this possible? Why doesn't the time grow as the stack grows?

Understanding the mechanics behind this constant-time performance is more than academic curiosity. It's the foundation for knowing when this guarantee holds, when it might be violated, and how to design systems that depend on it.

In this page, we'll rigorously examine each operation, trace through the exact steps the computer performs, and prove that they're truly O(1). We'll also explore edge cases and scenarios where the guarantee might be compromised.

Before diving into the specifics, let's cement our understanding of O(1) complexity:

Definition: An operation is O(1), or "constant time," if the number of fundamental steps required to complete it does not depend on the input size (in this case, the number of elements in the stack).

The "1" in O(1) doesn't mean exactly one step—it means a bounded constant number of steps. An operation that always takes exactly 7 steps is O(1). An operation that takes between 3 and 15 steps (but never more, regardless of input size) is still O(1).

The critical insight: For push and pop to be O(1), the execution time must be the same whether:

• The stack has 1 element or 1 million elements
• It's the 1st push or the 10,000th push
• The array capacity is 10 or 10,000,000

If any of these factors affected the running time proportionally, we would not have O(1) complexity.

Let's dissect the push operation completely, counting every fundamental operation:

Push implementation (Convention B):

void push(Element x) {
    if (top >= capacity) throw StackOverflowException();
    array[top] = x;
    top = top + 1;
}

Step-by-step breakdown:

1. Compare top with capacity (1 comparison operation)
2. Branch decision (1 branch operation)
3. Calculate array address: base_address + (top × element_size) (1-2 arithmetic operations)
4. Store element at calculated address (1 memory write)
5. Calculate new top: top + 1 (1 arithmetic operation)
6. Store new top (1 memory write or register operation)

Total: 6-8 fundamental operations

Crucially, notice what's not in this list:

• No loop iterating over existing elements
• No searching through the array
• No copying of elements
• No operations that depend on the current size of the stack

Whether the stack has 5 or 5 million elements, push executes exactly these same 6-8 operations.

The optimized version:

Compilers often optimize this code further. The increment-and-assign pattern array[top++] = x typically compiles to:

1. Load top into a register
2. Use top as index for memory write
3. Increment register
4. Store register back to top

This is as efficient as it gets—a handful of CPU instructions that execute in nanoseconds.

Now let's apply the same rigorous analysis to the pop operation:

Pop implementation (Convention B):

Element pop() {
    if (top <= 0) throw EmptyStackException();
    top = top - 1;
    return array[top];
}

Step-by-step breakdown:

1. Compare top with 0 (1 comparison operation)
2. Branch decision (1 branch operation)
3. Calculate new top: top - 1 (1 arithmetic operation)
4. Store new top (1 memory write or register operation)
5. Calculate array address: base_address + (new_top × element_size) (1-2 arithmetic operations)
6. Load element from array (1 memory read)
7. Return element (1 return operation)

Total: 7-9 fundamental operations

Again, no loops, no iteration over existing elements, no dependency on stack size. Pop is conclusively O(1).

For completeness, let's verify that the remaining stack operations are also O(1):

Peek (Convention B):

Element peek() {
    if (top <= 0) throw EmptyStackException();
    return array[top - 1];
}

Operations: 1 comparison + 1 subtraction + 1 address calculation + 1 memory read = O(1)

isEmpty:

boolean isEmpty() {
    return top == 0;
}

Operations: 1 comparison + 1 return = O(1)

isFull (for fixed-capacity stacks):

boolean isFull() {
    return top == capacity;
}

Operations: 1 comparison + 1 return = O(1)

Size (Convention B):

int size() {
    return top;
}

Operations: 1 return = O(1)

With Convention A, size would be return top + 1; — still just 2 operations, still O(1).

Now that we've proven push and pop are O(1), let's understand the deeper reasons why this is achievable:

1. Random Access Memory Architecture

Modern computers use random access memory (RAM), where accessing any byte costs the same as accessing any other byte (ignoring cache effects). Array indexing exploits this: array[i] costs the same whether i is 0 or 1,000,000.

If we used sequential-access memory (like magnetic tape), accessing element n would require reading through elements 0 through n-1 first—making access O(n).

2. Contiguous Allocation

Arrays store elements contiguously, so address calculation is pure arithmetic:

address = base + (index × element_size)

If elements were scattered in memory, we'd need to follow pointers—which linked lists do—adding indirection overhead.

3. Single-Point Access

Stacks only access one location: the top. We don't need to search or iterate. If stacks allowed access to arbitrary positions, we'd need to traverse, breaking O(1).

4. Pointer-Based State

The top pointer gives us O(1) access to the boundary between "filled" and "empty" portions of the array. Without this pointer, we'd have to scan the array to find where elements end—an O(n) operation.

Understanding when O(1) might be violated helps you maintain performance guarantees in real systems:

1. Dynamic Array Resizing

With dynamic arrays, push occasionally triggers a resize—copying all n elements to a new array. This individual push takes O(n). However, with proper resizing strategy (doubling), this averages out to O(1) amortized (we'll cover this in the next page).

2. Memory Allocation Overhead

If your language allocates new memory for each push (some naive implementations), memory allocation might not be O(1). Modern allocators are typically O(1), but worst-case might involve system calls or garbage collection.

3. Cache Effects

While not changing asymptotic complexity, cache misses can dramatically affect real-world performance. A cold cache miss might take 100x longer than a cache hit. Arrays help here because of spatial locality, but large stacks might exceed cache size.

4. Virtual Memory Paging

Accessing memory not in physical RAM causes a page fault—an expensive operation (millions of CPU cycles). Very large stacks might trigger paging, though this isn't a complexity change but a constant-factor penalty.

5. Synchronization Overhead

In concurrent stacks, locks or atomic operations add constant overhead. While still O(1), the constant might be significantly larger than the unsynchronized version. Lock contention could even introduce waiting time proportional to the number of threads (though not to stack size).

While Big-O analysis is essential, let's ground our understanding with practical numbers:

Theoretical operation counts:

*Assuming push doesn't trigger resize and memory is already allocated.

The "~5 ns" is approximate for modern hardware. The key observation: the time doesn't change as the stack grows—that's the essence of O(1).

Contrast with O(n) operations:

If push were O(n) (requiring traversal), times would look like:

The difference is dramatic at scale. A system doing 1 million pushes:

• O(1): 1,000,000 × 5 ns = 5 ms total
• O(n): 1 + 2 + 3 + ... + 1,000,000 = ~500 billion ns = ~500 seconds!

Memory access patterns:

Beyond operation count, memory access patterns affect real performance:

1. Push/Pop locality: Consecutive push/pop operations access the same memory region repeatedly, keeping it in CPU cache. Cache hit rates approach 100%.

2. Stack working set: If your stack stays within L1 cache size (~32KB), operations execute at L1 speeds (~1ns). L2 (~256KB) adds ~10ns latency. L3 (~8MB) adds ~40ns. Main memory adds ~100ns.

3. Hot path optimization: Since push/pop are so frequent, modern CPUs and compilers heavily optimize these patterns. Branch prediction nearly always succeeds (the full/empty checks rarely fail in normal operation).

We've rigorously established that push and pop achieve constant-time complexity. This guarantee is the foundation of the stack's utility in performance-critical applications.

What's next:

We've proven O(1) for fixed-capacity stacks. But what happens when the stack fills up? The next page explores the critical topic of handling overflow: static arrays with fixed capacity versus dynamic arrays with automatic resizing. We'll introduce amortized analysis to understand why dynamic arrays maintain O(1) amortized push even with occasional O(n) resizing.