☕ DSA Java Articles

Topics › Stacks and Queues › Learning

Implement Stack using Arrays

Easy TUF ID 390 A2ZSDE

Java source ↗ Edit this article ↗

Problem

Design a stack of integers whose storage is a plain array. A stack is a last in, first out container: the element you push most recently is the one pop removes and top reports. Support these operations:

Constraints: up to 10^5 operations, values fit in a 32-bit int. pop and top on an empty stack are errors. Some versions ask you to return -1 in that case; the code here throws NoSuchElementException, which is what java.util does and is harder to ignore by accident. A fixed-capacity stack must also reject a push when it is full (stack overflow).

Example 1

push(1), push(2), push(3), top(), pop(), pop(), size(), isEmpty()
output: 3, 3, 2, 1, false          // 3 was pushed last, so it comes out first

Example 2

push(-5), pop(), push(7), push(7), pop(), push(-5), top(), size()
output: -5, 7, -5, 2               // duplicates and negatives need no special treatment

Both implementations below satisfy this small interface, which is what lets one test script drive them all:

interface IntStack {
    void push(int x);
    int pop();
    int top();
    boolean isEmpty();
    int size();
}

Approach 1: Fixed-capacity array

Intuition. A stack only ever changes at one end. If we keep the elements in data[0 .. topIndex], with data[0] the oldest and data[topIndex] the newest, then every operation touches only data[topIndex] and the integer topIndex. Nothing ever has to move. Using -1 to mean “empty” makes size() simply topIndex + 1 and lets push write to data[++topIndex] without a special case for the first element.

Algorithm.

  1. Allocate data = new int[capacity] and set topIndex = -1.
  2. push(x): if topIndex == capacity - 1 the stack is full, throw. Otherwise increment topIndex and store x there.
  3. pop(): if topIndex == -1 throw. Otherwise return data[topIndex] and decrement topIndex.
  4. top(): same check, return data[topIndex] without decrementing.
  5. isEmpty() is topIndex == -1; size() is topIndex + 1.
static class FixedArrayStack implements IntStack {
    private final int[] data;
    private int topIndex = -1;               // index of the current top, -1 when empty

    FixedArrayStack(int capacity) {
        data = new int[capacity];
    }

    public void push(int x) {
        if (topIndex == data.length - 1) throw new IllegalStateException("stack overflow");
        data[++topIndex] = x;
    }

    public int pop() {
        if (topIndex == -1) throw new NoSuchElementException("stack underflow");
        return data[topIndex--];
    }

    public int top() {
        if (topIndex == -1) throw new NoSuchElementException("stack is empty");
        return data[topIndex];
    }

    public boolean isEmpty() {
        return topIndex == -1;
    }

    public int size() {
        return topIndex + 1;
    }
}

Dry run on example 1 with capacity 3:

operation data (used part) topIndex returns
push(1) [1] 0  
push(2) [1, 2] 1  
push(3) [1, 2, 3] 2  
top() [1, 2, 3] 2 3
pop() [1, 2] 1 3
pop() [1] 0 2
size() [1] 0 1
isEmpty() [1] 0 false

Notice that pop does not erase data[2]; the stale 3 is simply outside the used range and will be overwritten by the next push. That is why the stack needs no clearing step.

Complexity. Time O(1) for every operation: each one does a constant amount of index arithmetic and one array access. Space O(capacity), allocated once up front, whether or not it is used.

The weakness is the fixed capacity. Too small and a legitimate push fails; too large and memory is wasted. Both problems disappear with the next approach.

Approach 2: Growable array

Intuition. Start with a tiny array and, when a push finds it full, allocate one twice as large and copy the elements over. Copying costs O(n), but it happens only after n cheap pushes have filled the array, so the total work for n pushes is n + (1 + 2 + 4 + ... + n) < 3n. Spread over the n pushes that is a constant per push, which is what amortised O(1) means. java.util.ArrayList and ArrayDeque grow exactly this way.

To give memory back, shrink when the stack becomes sparse. The threshold matters: if we halved as soon as the array was half full, a push-pop-push-pop sequence right at the boundary would copy the array on every operation. Halving only when a quarter is in use leaves a wide buffer, so after any resize the array is exactly half full and at least n/2 operations must happen before the next one.

Algorithm.

  1. Start with data = new int[2] and topIndex = -1.
  2. push(x): if the array is full, replace it with Arrays.copyOf(data, 2 * data.length). Then store as before.
  3. pop(): read and decrement as before. If the remaining size is at most a quarter of the capacity (and the capacity is above the minimum), replace the array with a copy of half the length.
  4. top, isEmpty and size are unchanged.
static class DynamicArrayStack implements IntStack {
    private int[] data = new int[2];
    private int topIndex = -1;

    public void push(int x) {
        if (topIndex == data.length - 1) data = Arrays.copyOf(data, data.length * 2);
        data[++topIndex] = x;
    }

    public int pop() {
        if (topIndex == -1) throw new NoSuchElementException("stack underflow");
        int x = data[topIndex--];
        if (data.length > 2 && topIndex + 1 <= data.length / 4) data = Arrays.copyOf(data, data.length / 2);
        return x;
    }

    public int top() {
        if (topIndex == -1) throw new NoSuchElementException("stack is empty");
        return data[topIndex];
    }

    public boolean isEmpty() {
        return topIndex == -1;
    }

    public int size() {
        return topIndex + 1;
    }

    int capacity() {
        return data.length;
    }
}

Complexity. Time amortised O(1) per operation, by the doubling argument above; a single push or pop can still take O(n) when it triggers a copy. Space O(n) where n is the number of elements currently stored: the array is never more than four times the size, and never less than it.

The test in the Java file pushes 0 .. 999, checks that the capacity is 1024, pops down to 100 elements and checks that the capacity has fallen to 256: halving at 256 elements (capacity 1024 → 512) and again at 128 (512 → 256), but not at 100 because 100 > 256 / 4.

Edge cases and pitfalls