Array-Based Stack Implementation
You'll learn how to build a working stack data structure using an array and a top pointer.
The Core Idea
Imagine a stack of plates where you always add or remove from the top. To implement this in code, we use an array to hold the elements and an integer variable (often called top) that tracks which array position is currently the "top" of the stack.
The array provides the storage space, while top tells us where the next push should go or which element to pop. When the stack is empty, top might be -1 (indicating no valid elements). Each time you push, you increment top and store the new element at that index. Each time you pop, you return the element at top and decrement it.
Fixed vs Dynamic Array
You can implement this with:
- A fixed-size array: Set a maximum capacity upfront (e.g., 100 elements). Simple but limited.
- A dynamic array: Resize when full (like doubling capacity). More flexible but requires handling memory reallocation.
How It Works
- Push: Increment
top, then place the element atarray[top] - Pop: Return
array[top], then decrementtop - Peek: Return
array[top]without changingtop - IsEmpty: Check if
top == -1 - Size: Return
top + 1(since we started counting at zero)
The Power of the Top Pointer
The top pointer is your guide. It always points to the most recently added element (or indicates emptiness). You never need to search through the array—every operation happens at one predictable location.
Key Takeaway: An array-based stack uses a simple array for storage and a top pointer to track position, making push and pop efficient O(1) operations with direct index access.