Implement a stack using an array

• Array-backed stack – stores elements in a backing array with a top index pointing at the current top element.
• top = -1 – represents an empty stack; the number of elements is always top + 1.
• Push – increments top and writes a[top] = value. O(1).
• Pop – reads a[top], nulls the slot, decrements top, returns the value. O(1).
• Peek – reads a[top] without changing top. O(1).
• Resize – when full, double the array and copy elements, giving amortized O(1) push.

What is an array-backed stack?

A stack is a last-in, first-out (LIFO) data structure. An array-backed stack stores elements in a fixed-size or resizable array and uses a top index to track the current top element. The two pieces of state are the backing array and the top index. An empty stack has top = -1.

How do push, pop, and peek work?

• Push first checks if the array is full. If full, it resizes. Then it increments top and stores the new element at a[top].
• Pop checks if the stack is empty (top == -1); popping empty must throw. Otherwise it reads a[top], nulls that slot, decrements top, and returns the value.
• Peek checks if empty, then returns a[top] without changing top.

How do you implement it? (with code)

package com.bank.service;

import java.math.BigDecimal;
import java.util.EmptyStackException;
import java.util.Arrays;

public class TransactionStack {

    private BigDecimal[] items;
    private int top;

    public TransactionStack(int initialCapacity) {
        this.items = new BigDecimal[initialCapacity];
        this.top = -1;
    }

    public void push(BigDecimal amount) {
        if (top + 1 == items.length) {
            items = Arrays.copyOf(items, items.length * 2);
        }
        items[++top] = amount;
    }

    public BigDecimal pop() {
        if (top == -1) {
            throw new EmptyStackException();
        }
        BigDecimal value = items[top];
        items[top] = null;  // help garbage collection
        top--;
        return value;
    }

    public BigDecimal peek() {
        if (top == -1) {
            throw new EmptyStackException();
        }
        return items[top];
    }

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

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

    public static void main(String[] args) {
        TransactionStack stack = new TransactionStack(4);
        stack.push(new BigDecimal("5000"));
        stack.push(new BigDecimal("12000"));
        stack.push(new BigDecimal("7500"));

        System.out.println("Peek: " + stack.peek());
        System.out.println("Pop: " + stack.pop());
        System.out.println("Size: " + stack.size());
    }
}

Peek: 7500
Pop: 7500
Size: 2

Why double the array on resize?

Doubling on resize gives amortized O(1) push. Although an individual resize costs O(n) to copy all elements, it happens rarely enough (after 1, 2, 4, 8, 16... pushes) that the average push cost stays constant. The total copy cost for n pushes is 1 + 2 + 4 + ... + n = 2n - 1 = O(n), so amortized cost per push is O(1).

Why null out the slot on pop?

If you do not null the slot, the array still holds a reference to the popped object, preventing the garbage collector from reclaiming it. This is a memory leak in long-lived stacks, sometimes called a loitering reference.

// Wrong: memory leak
public BigDecimal pop() {
    return items[top--];  // stale reference remains at items[top+1]
}

// Correct: null out
public BigDecimal pop() {
    BigDecimal val = items[top];
    items[top] = null;
    top--;
    return val;
}

How is this different from a fixed-capacity stack?

A fixed-capacity stack refuses to resize and throws an overflow exception when full. This is the right choice when you want a hard bound on memory, such as a limited undo buffer.

| Variant | On full push | Memory behavior |
|---|---|---|
| Resizable (doubling) | Grow the array | Unbounded growth |
| Fixed-capacity | Throw exception | Hard memory bound |

What are the edge cases?

• Pop on empty – throw EmptyStackException.
• Peek on empty – throw EmptyStackException.
• Push beyond capacity – resize (or throw for fixed-capacity).
• Single element – push and pop work; top goes from -1 to 0 and back.

How is this different from using a LinkedList as a stack?

| Aspect | Array stack | LinkedList stack |
|---|---|---|
| Memory layout | Contiguous, cache-friendly | Scattered nodes |
| Per-element overhead | None (just the slot) | Node object + pointer |
| Resize cost | Occasional O(n) copy | None (always O(1)) |
| Random access | O(1) by index | O(n) |

The array stack is more cache-friendly and has lower per-element overhead, which makes it the default choice for most use cases.

What should a senior engineer know?

In production, Pankaj at the National Bank of India would choose between resizable and fixed-capacity based on the requirement. A fixed-capacity stack for a session undo buffer limits memory per session. A resizable stack for a general-purpose utility grows as needed. The amortized O(1) analysis using the doubling argument is the standard proof interviewers expect.

What are common interview follow-up questions?

• Can you implement a min-stack? – Add a parallel stack tracking the running minimum.
• What about thread safety? – Use synchronized or a lock; Java's java.util.Stack is synchronized but deprecated in favor of Deque.
• What about shrinking? – Halve the array when it drops below 1/4 full to avoid thrashing.