Stack: with an array and with a linked list

A stack is like plates piled on top of each other: you put a plate on the top, and when taking one you take the one on top. You can’t pull a plate from the middle. This rule is called LIFO (Last In, First Out). It looks simple, but compilers’ expression evaluation, method calls, the undo feature and parenthesis checking all work with a stack. Exam questions are of two types: finding what is printed or what is left in the stack after a sequence of operations, and writing push/pop with an array or a linked list.

Golden rules:

1. You only reach the top. push puts on the top, pop takes from the top.
2. peek looks, it doesn’t remove. When tracing, don’t confuse pop with peek.
3. In an array, top is the index of the last element. -1 in an empty stack.
4. In a linked list the top is the head of the list. Not the end.
5. pop from an empty stack = underflow, push to a full array = overflow.

Abstract data type (ADT)

A stack is an abstract data type: it says which operations exist, not how they are done. The operations:

We can implement the same ADT in two ways: with an array or with a linked list. The code that uses it sees no difference.

Stack with an array (array-based stack)

class ArrayStack {
    private int[] data;
    private int top = -1;   // index of the last element

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

    boolean isEmpty() { return top == -1; }
    boolean isFull()  { return top == data.length - 1; }
    int size()        { return top + 1; }

    void push(int x) {
        if (isFull()) throw new RuntimeException("Stack overflow");
        data[++top] = x;    // increment first, then write
    }

    int pop() {
        if (isEmpty()) throw new RuntimeException("Stack underflow");
        return data[top--]; // read first, then decrement
    }

    int peek() {
        if (isEmpty()) throw new RuntimeException("Stack underflow");
        return data[top];
    }
}

The difference between ++top and top-- is critical here. If you write data[top++] = x, the first element is written to data[-1] and you get an ArrayIndexOutOfBoundsException.

Worked example

ArrayStack s = new ArrayStack(5);
s.push(10); s.push(20); s.push(30);
System.out.println(s.pop());
System.out.println(s.peek());
s.push(40);
System.out.println(s.size() + " " + s.raw());   // raw: the raw state of the array

30
20
3 [10, 20, 40, 0, 0] top=2

push 10     [10, _, _, _, _]   top=0
push 20     [10, 20, _, _, _]  top=1
push 30     [10, 20, 30, _, _] top=2
pop → 30    [10, 20, 30, _, _] top=1   (30 is still in the array but not in the stack)
peek → 20   no change
push 40     [10, 20, 40, _, _] top=2   (written over the 30)

PITFALL · pop doesn’t erase from the array. If the exam asks “what are the contents of the array?”, the popped values are still there; they just sit above the top index. A new push writes over them.

Growing when full

Instead of a fixed capacity, when full you can open a new array of double the size and copy. That push takes O(n), but since the capacity doubles each time, this happens rarely. The total cost of n pushes is O(n), that is O(1) amortized per push. Java’s ArrayList and ArrayDeque classes work this way.

Stack with a linked list (linked stack)

Inserting at the head of a singly linked list and deleting from the head are already O(1). Top = head.

class LinkedStack {
    private static class Node {
        int data; Node next;
        Node(int d, Node n) { data = d; next = n; }
    }
    private Node top;

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

    void push(int x) { top = new Node(x, top); }

    int pop() {
        if (top == null) throw new RuntimeException("Stack underflow");
        int x = top.data;
        top = top.next;
        return x;
    }

    int peek() {
        if (top == null) throw new RuntimeException("Stack underflow");
        return top.data;
    }
}

In this implementation there is no overflow (until memory runs out). The cost is one next reference per node.

Classic jobs done with a stack

Reversing. Push the letters in order, then pop: “DATA” → “ATAD”. The order that goes into the stack is reversed on the way out.

Decimal to binary. Push the remainders of n % 2, halve n; then pop everything. 13 → 1101, 6 → 110, 32 → 100000.

static String toBinary(int n) {
    if (n == 0) return "0";
    Deque<Integer> s = new ArrayDeque<>();
    while (n > 0) { s.push(n % 2); n /= 2; }
    StringBuilder sb = new StringBuilder();
    while (!s.isEmpty()) sb.append(s.pop());
    return sb.toString();
}

Method calls. On every method call, Java puts the local variables in a stack frame; when the method ends, the frame is popped. Infinite recursion fills this stack and gives a StackOverflowError (week 10).

Other applications (parenthesis balance, infix → postfix, postfix evaluation) are the subject of next week.

Pop order questions

“1, 2, 3, 4 are pushed in order, and a pop can happen at any moment in between. Which output order is possible?” To solve it, simulate: push up to the number that needs to come out, then check whether the top is that number.

Target 3 1 4 2:
  3 needed → push 1, 2, 3 → pop 3       stack [1, 2]
  1 needed → top is 2, not 1            IMPOSSIBLE

Target 3 2 4 1:
  push 1,2,3 → pop 3 → [1,2]
  pop 2 → [1]
  push 4 → pop 4 → [1]
  pop 1                                 POSSIBLE

Short rule: after a number is popped, the numbers smaller than it that have not yet come out must come out in decreasing order.

A ready-made stack in Java

The java.util.Stack class is old (derived from Vector, synchronized, slow). In modern Java the recommended one is the Deque interface and the ArrayDeque class:

Deque<Integer> st = new ArrayDeque<>();
st.push(1); st.push(2);
st.peek();   // 2
st.pop();    // 2

On an empty ArrayDeque, pop() throws NoSuchElementException, while peek() returns null. Details in week 9.

Common mistakes

s.push(5); s.push(3);
System.out.print(s.pop() + " ");
s.push(8); s.push(1);
System.out.print(s.pop() + " ");
System.out.print(s.pop() + " ");
s.push(6);
System.out.println(s.peek());

for (int i = 1; i <= 5; i++) {
    s.push(i * 2);
    if (i % 2 == 0)
        System.out.print(s.pop() + " ");
}

push(7); push(2); push(9);
pop(); pop();
push(4);

try {
    for (int i = 1; i <= 4; i++) {
        s.push(i);
        System.out.print(i + " ");
    }
} catch (RuntimeException e) {
    System.out.println("-> " + e.getMessage());
}

int pop() {
    if (top == -1)
        throw new RuntimeException("Stack underflow");
    return data[top--];   // read first, then decrement
}

void push(int x) {
    top = new Node(x, top);
}

int pop() {
    if (top == null)
        throw new RuntimeException("Stack underflow");
    int x = top.data;
    top = top.next;
    return x;
}

static String f(String w) {
    Deque<Character> st = new ArrayDeque<>();
    for (char ch : w.toCharArray()) st.push(ch);
    StringBuilder sb = new StringBuilder();
    while (!st.isEmpty()) sb.append(st.pop());
    return sb.toString();
}

while (!s.isEmpty()) {
    int x = s.pop();
    if (x % 2 == 0) t.push(x);
}
while (!t.isEmpty())
    System.out.print(t.pop() + " ");

static String toBinary(int n) {
    if (n == 0) return "0";
    Deque<Integer> s = new ArrayDeque<>();
    while (n > 0) {
        s.push(n % 2);
        n /= 2;
    }
    StringBuilder sb = new StringBuilder();
    while (!s.isEmpty()) sb.append(s.pop());
    return sb.toString();
}

int sum = 0;
while (s.peek() != 4)
    sum += s.pop();
System.out.println(sum + " " + s.peek());