Implementing a Stack: Array-Based and Built-In Stacks

There are two ways to get a stack: build one yourself on top of a dynamic array, or use the built-in stack your language already ships. Both give O(1) push, pop, and peek. This page shows the from-scratch version first (so you understand the mechanics) and then the idiomatic built-in you should actually use in interviews and production.

A stack from scratch (array-based)

The trick: a dynamic array already gives O(1) append and remove-from-end. So treat the end of the array as the top of the stack. Pushing appends; popping removes the last element. No shifting, no extra memory.

#include <vector>
#include <stdexcept>
class Stack {
    std::vector<int> data;
public:
    void push(int x) { data.push_back(x); }
    int pop() {
        if (data.empty()) throw std::out_of_range("pop from empty stack");
        int x = data.back();
        data.pop_back();
        return x;
    }
    int peek() const { return data.back(); }
    bool empty() const { return data.empty(); }
    int size() const { return (int)data.size(); }
};

import java.util.*;
class Stack {
    private List<Integer> data = new ArrayList<>();
    public void push(int x) { data.add(x); }
    public int pop() {
        if (data.isEmpty()) throw new NoSuchElementException("pop from empty stack");
        return data.remove(data.size() - 1);
    }
    public int peek() { return data.get(data.size() - 1); }
    public boolean isEmpty() { return data.isEmpty(); }
    public int size() { return data.size(); }
}

class Stack {
  constructor() { this.data = []; }
  push(x) { this.data.push(x); }
  pop() {
    if (this.data.length === 0) throw new Error("pop from empty stack");
    return this.data.pop();
  }
  peek() { return this.data[this.data.length - 1]; }
  isEmpty() { return this.data.length === 0; }
  size() { return this.data.length; }
}

class Stack:
    def __init__(self):
        self._data = []
    def push(self, x):
        self._data.append(x)
    def pop(self):
        if not self._data:
            raise IndexError("pop from empty stack")
        return self._data.pop()
    def peek(self):
        return self._data[-1]
    def is_empty(self):
        return not self._data
    def size(self):
        return len(self._data)

Because the underlying array grows by doubling, append is amortized O(1) — see dynamic arrays for why. Every other operation is exact O(1).

Gotcha: Always check for empty before pop/peek. Popping an empty stack is the single most common stack bug — decide whether you throw, return a sentinel, or return a status flag, and do it consistently.

Using the built-in stack

In practice you rarely hand-roll a stack. Each language gives you a ready one — use it.

#include <stack>
std::stack<int> s;   // backed by std::deque by default
s.push(10);
s.push(20);
int t = s.top();     // 20 (peek)
s.pop();             // removes 20 (returns void!)
bool e = s.empty();

import java.util.*;
// Prefer ArrayDeque over the legacy synchronized Stack class.
Deque<Integer> s = new ArrayDeque<>();
s.push(10);
s.push(20);
int t = s.peek();    // 20
s.pop();             // removes and returns 20
boolean e = s.isEmpty();

// A plain array IS the idiomatic JS stack.
const s = [];
s.push(10);
s.push(20);
const t = s[s.length - 1]; // 20 (peek)
s.pop();                   // removes and returns 20
const e = s.length === 0;

# A plain list IS the idiomatic Python stack.
s = []
s.append(10)
s.append(20)
t = s[-1]   # 20 (peek)
s.pop()     # removes and returns 20
e = not s

Language notes: In C++ std::stack::pop() returns void — read top() first, then pop(). In Java, avoid the old java.util.Stack (it’s synchronized and slow); use ArrayDeque. In JS and Python the native array/list already behaves as a stack, so a wrapper class is rarely worth it.

Array vs linked-list backing

You can also build a stack from a linked list, pushing/popping at the head. Comparison:

Backing        push/pop   peek   memory overhead   cache friendliness
Dynamic array  O(1)*      O(1)   low               high (contiguous)
Linked list    O(1)       O(1)   per-node pointer  lower
* amortized; occasional O(n) resize

The array version is almost always faster in practice thanks to contiguous memory. Use the linked-list version only when you must avoid resize pauses or need stable element addresses.

When to roll your own

Use the built-in unless an interviewer explicitly asks you to implement a stack, or you need custom behavior (e.g. a stack that also tracks its minimum in O(1) — a classic problem on the exercises page).

Next: put stacks to work in stack applications.