Array-Based Stack Implementation
The most common way to build a stack. An array stack uses a contiguous block of memory and a top pointer to track the current element in O(1) time.
How an Array Stack Works
An array stack stores elements in a regular array. A variable called top tracks the index of the most recently pushed element. When the stack is empty, top is set to -1. When you push an element, top increments and the element is placed at that index. When you pop, the element at top is removed and top decrements.
Array Stack: top = 2
index: 0 1 2 3 4
Elements at indices 0 through 2 are active. The element at index 2 (70) is the top.
Fixed-Size vs Dynamic Arrays
Fixed-Size Array Stack
The array is allocated once with a fixed capacity (for example, 1000 elements). Push fails with a stack overflow when the array is full.
- Simple to implement
- No memory reallocation
- Risk of stack overflow
- Best when you know the maximum size
Dynamic Array Stack
The array starts with an initial capacity. When it fills up, a new array (usually double the size) is allocated and elements are copied over.
- Grows as needed
- No overflow risk (until memory runs out)
- Occasional O(n) resize cost
- Amortized O(1) per push
The Top Pointer
The top pointer is the key to making array stack operations O(1). Without it, you would need to scan the entire array to find the last element.
In its simplest form, top is an integer index. It has three states:
- -1: The stack is empty. No elements have been pushed.
- 0 to capacity - 1: The stack has elements. The element at index
topis the topmost element. - capacity: The stack is full (in a fixed-size implementation). This signals overflow.
Some implementations track size separately instead of using -1 for empty. In that case, top points to the next available slot rather than the current top element. Both approaches are valid; they just shift the index by one.
Push on an Array Stack
Push adds an element at position top + 1 and then increments top.
top + 1 == capacity. If true and the array is fixed-size, signal overflow.top = top + 1.array[top].// Push in C
void push(int stack[], int *top, int capacity, int value) {
if (*top + 1 == capacity) return; // overflow
stack[++(*top)] = value;
}Pop from an Array Stack
Pop reads the element at array[top], decrements top, and returns the value.
top == -1. If true, the stack is empty (underflow).array[top] in a temporary variable.top = top - 1.// Pop in C
int pop(int stack[], int *top) {
if (*top == -1) return -1; // underflow
return stack[(*top)--];
}Peek and isEmpty
Peek returns array[top] without modifying top. isEmpty checks if top == -1. Both are O(1) operations with no side effects.
int peek(int stack[], int top) {
if (top == -1) return -1;
return stack[top];
}
int isEmpty(int top) {
return top == -1;
}Stack Overflow in Fixed Arrays
When a fixed-size array stack reaches its capacity, any push attempt causes overflow. There are several strategies for handling this:
Dynamic Array Resizing
Dynamic arrays solve the fixed-size limitation by growing when needed. The standard strategy is to double the capacity each time the array fills up.
Here is why doubling works. If you start with capacity 1 and double on each resize, the total cost of copying all elements so far is 1 + 2 + 4 + 8 + ... + n, which is less than 2n. This means the total work across all resizes is O(n), making the amortized cost per push O(1).
If you grew by a smaller factor (like 1.5x), the math still works out to amortized O(1), but you resize more often. Doubling is the most common choice because it minimizes the number of resizes.
Code Implementations
C (Fixed-Size Array Stack)
#include <stdio.h>
#define MAX 100
typedef struct {
int data[MAX];
int top;
} Stack;
void init(Stack *s) { s->top = -1; }
int isEmpty(Stack *s) { return s->top == -1; }
void push(Stack *s, int val) {
if (s->top == MAX - 1) {
printf("Overflow\n");
return;
}
s->data[++s->top] = val;
}
int pop(Stack *s) {
if (s->top == -1) {
printf("Underflow\n");
return -1;
}
return s->data[s->top--];
}
int peek(Stack *s) {
if (s->top == -1) return -1;
return s->data[s->top];
}C++ (Dynamic Array with std::vector)
#include <vector>
#include <stdexcept>
template <typename T>
class ArrayStack {
std::vector<T> arr;
public:
void push(const T& val) { arr.push_back(val); }
T pop() {
if (arr.empty()) throw std::runtime_error("Underflow");
T val = arr.back();
arr.pop_back();
return val;
}
T peek() const {
if (arr.empty()) throw std::runtime_error("Empty");
return arr.back();
}
bool isEmpty() const { return arr.empty(); }
int size() const { return arr.size(); }
};Java (Dynamic Array Stack)
import java.util.ArrayList;
import java.util.List;
public class ArrayStack<T> {
private List<T> data = new ArrayList<>();
public void push(T val) {
data.add(val);
}
public T pop() {
if (data.isEmpty()) throw new RuntimeException("Underflow");
return data.remove(data.size() - 1);
}
public T peek() {
if (data.isEmpty()) throw new RuntimeException("Empty");
return data.get(data.size() - 1);
}
public boolean isEmpty() { return data.isEmpty(); }
public int size() { return data.size(); }
}Python
class ArrayStack:
def __init__(self):
self._data = []
def push(self, val):
self._data.append(val)
def pop(self):
if not self._data:
raise IndexError("Stack underflow")
return self._data.pop()
def peek(self):
if not self._data:
raise IndexError("Stack is empty")
return self._data[-1]
def is_empty(self):
return len(self._data) == 0
def size(self):
return len(self._data)JavaScript
class ArrayStack {
constructor() {
this._data = [];
}
push(val) {
this._data.push(val);
}
pop() {
if (this._data.length === 0) {
throw new Error("Stack underflow");
}
return this._data.pop();
}
peek() {
if (this._data.length === 0) {
throw new Error("Stack is empty");
}
return this._data[this._data.length - 1];
}
isEmpty() {
return this._data.length === 0;
}
size() {
return this._data.length;
}
}When to Use an Array Stack
Array stacks are the default choice for most situations. Use an array stack when:
- You know the maximum number of elements (use fixed-size).
- You want the fastest possible push and pop (array stacks have the best cache performance).
- You are working in a systems language like C or C++ where heap allocation is expensive.
- You are implementing a stack for competitive programming where speed matters.
Frequently Asked Questions
What is the difference between a fixed-size array stack and a dynamic array stack?
A fixed-size array stack has a predetermined maximum capacity set at creation. A dynamic array stack starts with an initial capacity and doubles it when full, providing amortized O(1) push operations without a hard limit.
Why is the top pointer important in an array stack?
The top pointer tells you where the next push should go and where the next pop should read from. Without it you would need to scan the entire array to find the last element, making push and pop O(n) instead of O(1).
What happens when a dynamic array stack resizes?
When a dynamic array is full, a new array twice the size is allocated, all existing elements are copied to the new array, and the old array is freed. This copy costs O(n) but happens so rarely that the amortized cost per push is still O(1).
Is an array stack better than a linked list stack?
Array stacks are generally better for performance because they use contiguous memory which is cache-friendly. Linked list stacks are better when you cannot predict the maximum size and want to avoid resizing overhead. For most applications, an array stack is the better default choice.
How do I implement an array stack in Python?
In Python, a regular list works as an array stack. Use list.append() for push, list.pop() for pop, and list[-1] for peek. Python lists are dynamic arrays under the hood, so they handle resizing automatically.