Stacks: Last In, First Out

A pile of plates

You put clean plates on top of the pile and take plates from the top. The last plate put down is the first one picked up: Last In, First Out (LIFO). That's a stack.

Build one with an array

class MyStack {
    private int[] items = new int[100];
    private int top = 0;                  // number of items = next free slot

    void push(int x) { items[top++] = x; }
    int pop()        { return items[--top]; }
    int peek()       { return items[top - 1]; }
    boolean isEmpty() { return top == 0; }
}

public class Main {
    public static void main(String[] args) {
        MyStack plates = new MyStack();
        plates.push(1);
        plates.push(2);
        plates.push(3);
        System.out.println("top plate: " + plates.peek());
        while (!plates.isEmpty()) {
            System.out.println("take " + plates.pop());
        }
    }
}

Output

top plate: 3
take 3
take 2
take 1

A stack is just an array where you only ever touch the end – that's why every operation is O(1).

Java's version: ArrayDeque

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        ArrayDeque<String> history = new ArrayDeque<String>();
        history.push("home");
        history.push("search");
        history.push("product");
        System.out.println("now on: " + history.peek());
        history.pop();                                     // the Back button
        System.out.println("back to: " + history.peek());
        System.out.println(history.size() + " pages in history");
    }
}

Output

now on: product
back to: search
2 pages in history

Tip: Java also has an old Stack class, but the Java docs recommend ArrayDeque: it's faster.

Common mistake: Calling pop() on an empty ArrayDeque throws NoSuchElementException. Check isEmpty() first.