Array-Based Stack Implementation

In the previous modules, we explored the stack as an abstract data type (ADT)—a conceptual model defined purely by its operations and behavior. We understood that a stack enforces the LIFO (Last-In, First-Out) principle: the most recently added element is always the first to be removed.

But understanding the concept of a stack is only half the journey. Now comes the crucial engineering question: How do we actually build one?

The answer lies in one of the most fundamental data structures we already know: the array. In this module, we'll discover why arrays provide an almost perfect substrate for implementing stacks, and how this implementation leverages the strengths of contiguous memory storage.

When we consider how to implement a stack, we need a data structure that can efficiently support the stack's core operations:

• Push: Add an element to the top
• Pop: Remove and return the element from the top
• Peek: View the top element without removing it
• isEmpty: Check if the stack is empty

Both push and pop modify only one end of the collection—the "top" of the stack. This single-ended access pattern is a crucial insight that leads us directly to arrays.

Arrays excel at end operations:

Recall from our study of arrays that accessing or modifying the last element of an array is an O(1) operation. If we have an array of size n with elements occupying indices 0 through n-1, we can:

• Read the last element with array[n-1] in constant time
• Write to the position after the last element with array[n] = value in constant time
• "Remove" the last element conceptually by decrementing our count in constant time

This is exactly what stack operations require: constant-time modification at one end.

Every core stack operation maps to an O(1) array operation. No other common data structure provides this combination of simplicity and efficiency for stack semantics. This is why array-based stacks are ubiquitous in production systems, libraries, and language runtimes.

Visualizing how a stack maps onto an array is crucial for building correct implementations. Let's develop a clear mental model.

The traditional stack visualization shows elements stacked vertically, like a pile of plates:

    [top]  →  3
              2
              1
    [bottom] → 0 (first element pushed)

The array visualization lays elements horizontally:

    index:    0    1    2    3    4    5    6    7
    array:  [ 0 ][ 1 ][ 2 ][ 3 ][   ][   ][   ][   ]
                              ↑
                             top (next push goes here)

When we "rotate" the stack 90 degrees, the bottom of the stack becomes index 0, and the top of the stack corresponds to the highest occupied index. This mental rotation is essential: the top of the stack lives at the end of the occupied portion of the array.

Both conventions are valid and widely used. The "next empty slot" convention (right column) is slightly more common in production code because it makes size() trivially equal to top, and the empty check is slightly more intuitive (top == 0 vs top == -1). However, both are logically equivalent, and understanding both prepares you for any codebase you encounter.

Beyond time complexity, we must consider space complexity and memory efficiency. Array-based stacks have distinct memory characteristics that make them highly efficient for most use cases.

Contiguous memory allocation:

Arrays store elements in contiguous memory locations. For an array-based stack, this means:

• No per-element overhead: Unlike linked structures, arrays don't store pointers with each element. A stack of integers stores only integers, not integers plus pointers.
• Cache-friendly access: When the CPU loads memory, it fetches entire cache lines (typically 64 bytes). Contiguous storage means accessing one element likely pre-loads nearby elements into cache, speeding up subsequent accesses.
• Predictable memory footprint: The memory used is simply capacity × element_size, making it easy to reason about and budget for.

The memory efficiency equation:

For most applications, the memory efficiency of array stacks outweighs their constraints:

1. Stack sizes are often bounded or predictable (function call stacks, expression evaluation, undo operations)
2. The 3x memory savings compared to linked lists is substantial at scale
3. Cache efficiency translates to real-world performance gains that don't show in O(n) analysis

This is why the default stack implementations in most standard libraries (Java's ArrayDeque, C++'s std::stack with std::deque, Python's list) use array-based or hybrid array-based storage.

Let's walk through a sequence of stack operations to solidify the mental model. We'll use an array of capacity 8 and track each operation's effect on both the array contents and the top pointer.

Initial State:

capacity: 8
top: 0 (using "next empty slot" convention)
array: [ _ ][ _ ][ _ ][ _ ][ _ ][ _ ][ _ ][ _ ]
         0    1    2    3    4    5    6    7

The underscore _ represents an empty (uninitialized or previous) slot. The top pointer at 0 indicates the stack is empty.

Robust implementations are built on clear invariants—conditions that must always be true. For an array-based stack, we establish the following contract:

Core Invariants (using "next empty slot" convention):

1. 0 <= top <= capacity always
2. Elements at indices [0, top-1] are valid stack elements
3. Elements at indices [top, capacity-1] are either garbage or uninitialized
4. top == 0 if and only if the stack is empty
5. top == capacity if and only if the stack is full (for fixed-capacity stacks)

These invariants guide both implementation and debugging. If any invariant is violated, the stack is in an invalid state.

Why invariants matter:

Consider what happens without proper invariant checking:

• Push without bounds check: Array index out of bounds, crash, or memory corruption
• Pop on empty stack: Returns garbage data, or array index -1 access (undefined behavior)
• No top tracking: Lost track of stack contents, can't determine size or emptiness

Every reliable system enforces these invariants. They're not optional safety features—they're the foundation of correct behavior.

Before fully committing to arrays, let's consider why alternative data structures are less suitable for stack implementation.

Linked Lists:

We'll study linked list-based stacks in the next module, but briefly: while linked lists offer O(1) push and pop at the head, they incur significant overhead:

• Per-element pointer storage (8 bytes on 64-bit systems)
• Poor cache locality due to scattered memory allocation
• Increased allocation overhead (one allocation per push)

Linked lists make sense when the stack size is highly unpredictable or when you need to avoid the occasional O(n) resize cost. For most use cases, arrays win.

Doubly Linked Lists:

Adds even more overhead (two pointers per element) with no benefit for stack operations. Stacks never need backward traversal, so the extra pointer is pure waste.

Trees or Other Structures:

Completely misaligned with stack semantics. Trees excel at hierarchical relationships and fast search—neither of which stacks require. Using a tree for a stack would be like using a bulldozer to push a shopping cart.

Most programming languages provide built-in or standard library support for stack-like operations on arrays. Understanding these implementations helps you leverage existing tools effectively.

JavaScript/TypeScript:

const stack = [];
stack.push(10);      // Add to end
stack.push(20);
const top = stack.pop();  // Remove from end
console.log(stack[stack.length - 1]);  // Peek

JavaScript arrays are dynamic and directly support push/pop on the end.

Python:

stack = []
stack.append(10)     # Push
stack.append(20)
top = stack.pop()    # Pop
print(stack[-1])     # Peek

Python lists are dynamic arrays; append() and pop() operate on the right end.

Java:

Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);      // Push
stack.push(20);
int top = stack.pop();   // Pop
int peek = stack.peek(); // Peek

While Java has a Stack class, it's legacy. Prefer ArrayDeque which is array-based and faster.

C++:

std::stack<int> s;
s.push(10);
s.push(20);
int top = s.top();  // Peek
s.pop();            // Pop (doesn't return in C++)

The default underlying container is std::deque, which is a sequence of arrays.

We've established a comprehensive understanding of why arrays are the ideal substrate for stack implementation. Let's consolidate the key insights:

What's next:

Now that we understand why arrays work for stacks, we need to dive into how to manage the critical piece of state that makes it all work: the top pointer. The next page explores top pointer management in detail—initialization, update rules, and common pitfalls that lead to bugs.