Implement Stack from Scratch

The problem, simply

Build your own stack. A stack is a pile where the last thing you put on is the first thing you take off.

It must support five actions:

• push(x): put x on top.
• pop(): take the top thing off and give it back.
• peek(): look at the top thing without taking it.
• isEmpty(): say if the pile has nothing in it.
• size(): say how many things are in the pile.

Every action should take the same tiny amount of time, no matter how tall the pile is.

A story to remember it

Picture it

Examples

Way 1: the simple way

Use a row of boxes, an array, with a fixed size. Keep one number, top, that says where the last filled box is. An empty pile has top = -1.

1. To push: move top up by one, then write the value into arr[top].
2. To pop: read arr[top], then move top down by one.
3. To peek: read arr[top] and do not move anything.
4. The pile is empty when top == -1, and full when top == capacity - 1.

class ArrayStack {
    private final int[] arr;
    private int top = -1;              // -1 means the pile is empty

    ArrayStack(int capacity) {
        arr = new int[capacity];
    }

    void push(int x) {
        if (top == arr.length - 1) throw new RuntimeException("stack overflow");
        arr[++top] = x;                // move up, then write
    }

    int pop() {
        if (isEmpty()) throw new RuntimeException("stack underflow");
        return arr[top--];             // read, then move down
    }

    int peek() {
        if (isEmpty()) throw new RuntimeException("stack is empty");
        return arr[top];
    }

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

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

How long it takes: every action touches one box, O(1). Extra room: the whole array is made at the start, O(capacity), even if you only use two boxes. And if you guessed the size too small, pushes start failing.

Way 2: the clever way

Make the pile out of a chain of boxes, a linked list. Each box holds one value and an arrow to the box under it. We keep a finger called head on the top box.

1. To push: make a new box, point its arrow at the old top, and move head to the new box.
2. To pop: remember the value in the head box, then move head down to the next box.
3. To peek: read the head box.
4. Keep a counter for size(), so we never walk the chain to count.

The chain grows one box at a time, so it never gets full, and it never wastes boxes.

class LinkedStack {
    private static class Node {
        int val;
        Node next;                     // the box under this one
        Node(int val, Node next) { this.val = val; this.next = next; }
    }

    private Node head;                 // the top box, null when empty
    private int count;

    void push(int x) {
        head = new Node(x, head);      // new box points at the old top
        count++;
    }

    int pop() {
        if (head == null) throw new RuntimeException("stack underflow");
        int val = head.val;
        head = head.next;              // slide the top down one box
        count--;
        return val;
    }

    int peek() {
        if (head == null) throw new RuntimeException("stack is empty");
        return head.val;
    }

    boolean isEmpty() { return head == null; }

    int size() { return count; }
}

How long it takes: push, pop and peek each change one or two arrows, O(1). Extra room: one box per value, O(n), and the chain only grows as much as it needs. Each box also pays for one arrow, so it uses a bit more memory per value than an array.

Watch out for

• Popping or peeking on an empty pile. Check first and throw, or return a clear signal.
• Off by one with top. If top starts at -1, use arr[++top] = x for push and arr[top--] for pop. If top starts at 0 (meaning "next free box"), both change.
• For a stack of objects in an array, set arr[top] = null after popping. Otherwise the array keeps the old object alive and the garbage collector cannot free it.
• In Java, prefer ArrayDeque over the old Stack class. Stack extends Vector and locks on every call, which is slow.

What interviewers ask next

• Can the array version grow? Yes. When it is full, make a new array twice as big and copy everything over. One push may cost O(n), but spread over all pushes it is O(1) each, called amortized.
• Why double and not add 10 boxes each time? Adding a fixed amount means copying happens every few pushes, which adds up to O(n^2) total. Doubling keeps the total copying under 2n.
• Array or linked list, which is faster in practice? The array, usually. Its boxes sit next to each other in memory, so the processor reads them quickly. The list chases arrows around memory.
• Make it work for any type. Use generics, class Stack<T>, and an Object[] inside that you cast back to T.
• How would you also get the smallest value in O(1)? Keep a second pile of "smallest so far" values. That is the "min stack" problem.

Remember this

Grown-up words: the pile of plates is a stack, last in first out is LIFO, the row of boxes is an array, the chain of boxes is a singly linked list, taking from an empty pile is underflow, pushing onto a full array is overflow, and doubling the array is a dynamic array with amortized O(1) push.