Stacks

The Basics

A stack is a LIFO sequence. Addition and removal takes place only at one end, called the top.

The operations are:

• push(x): add an item on the top
• pop: remove (and return) the item at the top
• peek: return the item at the top (without removing it)
• size: return the number of items in the stack
• isEmpty: return whether the stack has no items

Stacks are one of the most widely used collection types in computer science. A tiny fraction of their known uses:

• Stacks of plates (this is where the name came from)
• Page history in a browser
• Undo / Redo
• Most recently used lists
• Vending Machines
• Expression Evaluation
• Matching delimiters
• Navigating a maze
• Backtracking algorithms trying out different alternatives
• Map coloring
• Function calls in a running program
• Matching brackets
• Many more examples

An Interface

You should learn how to build a stack ADT from scratch, because:

• This is a really good way to learn how stacks work behind the scenes
• You need coding practice, especially with linked structures
• You might find yourself in a restrictive environment that doesn't have a collections library

Here is a Java interface:

/**
 * A small stack interface. You can (1) query the size of the stack, (2) ask
 * whether it is empty, (3) push an item, (4) pop an item, and (5) peek at the
 * top item.
 */
public interface Stack {

    /**
     * Adds the given item to the top of the stack.
     */
    void push(Object item);

    /**
     * Removes the top item from the stack and returns it.
     * 
     * @exception java.util.NoSuchElementException if the stack is empty.
     */
    Object pop();

    /**
     * Returns the top item from the stack without popping it.
     * 
     * @exception java.util.NoSuchElementException if the stack is empty.
     */
    Object peek();

    /**
     * Returns the number of items currently in the stack.
     */
    int size();

    /**
     * Returns whether the stack is empty or not.
     */
    default boolean isEmpty() {
        return size() == 0;
    }
}

Representations

When building data structures, we often find ourselves with multiple options. We often end up with some mix of arrays and links. Sometimes we use links only, sometimes arrays only. We’ll start with a linked approach.

A Linked Stack

A simple representation is to chain the elements together in a structure bounded only by the size of available memory. The stack itself will store its current size and a chain of its elements. Since we always access the top of the stack only, we can call this field top! Here are a couple pictures of linked stacks:

Once you’ve studied the pictures, the following implementation should make some sense:

import java.util.NoSuchElementException;

/**
 * An implementation of the stack interface using singly-linked nodes.
 */
public class LinkedStack implements Stack {
    private record Node(Object data, Node next) {
    }

    private Node top = null;
    private int size = 0;

    public void push(Object item) {
        top = new Node(item, top);
        size++;
    }

    public Object pop() {
        var item = peek();
        top = top.next;
        size--;
        return item;
    }

    @Override
    public boolean isEmpty() {
        // Override the default implementation for efficiency
        return top == null;
    }

    public Object peek() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return top.data;
    }

    public int size() {
        return size;
    }
}

A Bounded Array Stack

The simplest array-based approach is one that has the array bounds set on construction tine and can never grow. This approach is known as a bounded stack. It is good for security-minded applications, since no one likes to be attacked by users that use your class to fill up memory.

We store the stack elements in the array, with the size field conveniently referencing the next index to push to:

import java.util.NoSuchElementException;

/**
 * An implementation of a stack using a fixed, non-expandable array whose
 * capacity is set in its constructor. It comes with an extra method that
 * returns whether the stack is full (something that does not apply to the
 * Stack interface, since not all kinds of stacks have a size bound).
 */
public class BoundedStack implements Stack {
    private Object[] elements;
    private int size = 0;

    public BoundedStack(int capacity) {
        elements = new Object[capacity];
    }

    public void push(Object item) {
        if (isFull()) {
            throw new IllegalStateException("Cannot add to full stack");
        }
        elements[size++] = item;
    }

    public Object pop() {
        var item = peek();
        elements[--size] = null;
        return item;
    }

    public Object peek() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return elements[size - 1];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    // This is a bonus method that is not part of the interface
    public boolean isFull() {
        return size == elements.length;
    }
}

Things to note here:

• The capacity is set at creation time
• Pushes have a precondition that the stack isn't already full
• Pushing on a full stack is a state exception, not an argument exception
• When popping, we take care to nullify the newly unused slot in the array to prevent a possible memory leak

An Expandable Array Stack

You can do a little “mixing” of the array and linked approaches. Start with an array of reasonable size, then, when it fills up, reallocate a new array (of twice the size), copy the contents over, and add the new element. If the array ever gets too small, allocate a smaller array for the queue and copy into it.

Unit Testing

Here is what we need to test:

• A stack is empty on construction
• A stack has size 0 on construction
• After n > 0 pushes to an empty stack, the stack is not empty and its size is n
• If one pushes x then pops, the value popped is x.
• If one pushes x then peeks, the value returned is x, but the size stays the same
• If the size is n, then after n pops, the stack is empty and has a size 0
• Popping from an empty stack throws a NoSuchElementException
• Peeking into an empty stack throws a NoSuchElementException
• For bounded stacks only, pushing onto a full stack throws an IllegalStateException

We really have three classes to test, but the test cases share a bunch of things in common; the common tests can go in a base class.

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertTrue;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertThrows;

import java.util.NoSuchElementException;

/**
 * Base test for any class that implements the Stack interface.
 */
public abstract class StackTest {

    /**
     * The stack to use in all the tests: set this in subclasses.
     */
    protected Stack s;

    @Test
    public void testNewStackIsEmpty() {
        assertTrue(s.isEmpty());
        assertEquals(0, s.size());
    }

    @Test
    public void testPushesToEmptyStack() {
        int numberOfPushes = 8;
        for (var i = 0; i < numberOfPushes; i++) {
            s.push("zzz");
        }
        assertFalse(s.isEmpty());
        assertEquals(numberOfPushes, s.size());
    }

    @Test
    public void testPushThenPop() {
        var message = "hello";
        s.push(message);
        assertEquals(message, s.pop());
    }

    @Test
    public void testPushThenPeek() {
        var message = "hello";
        s.push(message);
        var size = s.size();
        assertEquals(message, s.peek());
        assertEquals(size, s.size());
    }

    @Test
    public void testPoppingDownToEmpty() {
        int numberOfPushes = 8;
        for (var i = 0; i < numberOfPushes; i++) {
            s.push("zzz");
        }
        for (var i = 0; i < numberOfPushes; i++) {
            s.pop();
        }
        assertTrue(s.isEmpty());
        assertEquals(0, s.size());
    }

    @Test
    public void testPopOnEmptyStackThrows() {
        assertTrue(s.isEmpty());
        assertThrows(NoSuchElementException.class, () -> s.pop());
    }

    @Test
    public void testPeekIntoEmptyStackThrows() {
        assertTrue(s.isEmpty());
        assertThrows(NoSuchElementException.class, () -> s.peek());
    }
}

The concrete test classes instantiate the specific kind of stack. Because they are subclasses of the base test class, they inherit all of the the common test cases for free! The linked stack test has nothing to add to the base test:

import org.junit.jupiter.api.BeforeEach;

public class LinkedStackTest extends StackTest {

    @BeforeEach
    public void makeLinkedStack() {
        s = new LinkedStack();
    }
}

Bounded stacks have that extra functionality (fullness) that must be tested:

import org.junit.jupiter.api.Test;
import org.junit.jupiter.api.BeforeEach;
import static org.junit.jupiter.api.Assertions.assertTrue;
import static org.junit.jupiter.api.Assertions.assertFalse;
import static org.junit.jupiter.api.Assertions.assertThrows;

public class BoundedStackTest extends StackTest {
    private static final int CAPACITY = 100;

    @BeforeEach
    public void makeBoundedStack() {
        s = new BoundedStack(CAPACITY);
    }

    @Test
    public void testPushToFullStack() {
        for (var i = 0; i < CAPACITY; i++) {
            s.push("abc");
        }
        assertThrows(IllegalStateException.class, () -> s.push("abc"));
    }

    @Test
    public void testIsFull() {
        for (var i = 0; i < CAPACITY; i++) {
            s.push("abc");
            assertFalse(s.isEmpty());
        }
        assertTrue(((BoundedStack) s).isFull());
    }
}

An Application of Stacks

If you have job interviews in your future, you’re likely familiar with LeetCode. Let’s look at Leet Code Problem 20 (Valid Parentheses).

“Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if (1) open brackets must be closed by the same type of brackets and (2) open brackets must be closed in the correct order.”

To solve this problem, we need to keep track of the opening brackets we have seen but not yet matched. As we see them, we stack them up, and as we match them, we check them off in reverse order. So given an input string like {{[]}()}[], we would proceed as follows:

Input   Op        Stack
{       push      {
{       push      {{
[       push      {{[
]       pop       {{
}       pop       {
(       push      {(
)       pop       {
}       pop
[       push      [
]       pop

If we start with an empty stack and finish with an empty stack, the string is valid. Here’s the algorithm:

public class ValidBracketChecker {

    public static boolean validBrackets(String s) {
        var stack = new LinkedStack();
        try {
            for (var c : s.toCharArray()) {
                if (c == '(' || c == '[' || c == '{') {
                    stack.push(String.valueOf(c));
                } else if (c == '}' && !stack.pop().equals("{")) {
                    return false;
                } else if (c == ']' && !stack.pop().equals("[")) {
                    return false;
                } else if (c == ')' && !stack.pop().equals("(")) {
                    return false;
                }
            }
            // If there is anything left over on the stack after running
            // through the whole string, we have "unclosed" brackets
            return stack.isEmpty();
        } catch (Exception e) {
            return false;
        }
    }

    public static void main(String[] args) {
        System.out.println(validBrackets(args[0]));
    }
}

Summary