Implementing a Stack in Apex

Apex collections comprise of Set, List and Map types and really nothing else. If you come from a Java or .Net background this must seem quite limiting at first given the variety of collections they support. However, in a metadata driven platform such as force.com you shouldn't have to worry about the nuances of a HashMap versus a Hashtable -- you just use a Map data structure and it is automatically optimized for you by the platform. As much as I like the simplicity of the force.com Apex programming I do miss some of the collection types that I have gotten used to in Java such as TreeMap, TreeSet and Stacks which can simplify the programming quite a bit.

Recently there was a need to implement a trigger logic which although could have been done using a List, was more appropriate for the use of a Stack. So I wrote a basic Stack class and sure enough it made the rest of the implementation a lot cleaner. There are really only three basic operations for a Stack -- push() to add an item on to the stack, pop() to remove the most recent (top most) item from the stack and peek() to take a look at the top most item without removing it from the stack. We can also add a size() method to return the number of items currently in the stack and an isEmpty() method to check if the stack is empty. You could optionally implement an iterator to iterate through the Stack but that is left as an exercise for the reader (no, you can't simply expose the List iterator :).

So here is the classic Stack implemented in Apex using the List.

public class Stack {
    private List<Object> items {get; set;}
    
    public Stack() {
        this.items = new List<Object>();
    }
    
    public Integer size() {
        return this.items.size();
    }

    public Boolean isEmpty() {
        return size() == 0;
    }
        
    public void push(Object itemToPush) {
        this.items.add(itemToPush);
    }
    
    public Object pop() {
        if (isEmpty()) {
            throw new StackUnderflowException();
        }
        
        return this.items.remove(size() - 1);
    }
    
    public Object peek() {
        if (isEmpty()) {
            throw new StackUnderflowException();
        }
        
        return this.items.get(size() - 1);
    }    
}

If we try to peek or pop from an empty stack, we would get an StackUnderflowException, which is a custom exception class: 

public class StackUnderflowException extends Exception {

    /* Custom exception */

}

That's pretty much it! Now you can use it for all sorts of LIFO (Last In First Out) type functions such as evaluating expressions or parsing a syntax tree. 

Stack s = new Stack();

s.push(10.0);

s.push(5.0);

s.push('+');

while (!s.isEmpty()) {

    Object o = s.pop();

    if (String.valueOf(o) == '+') {

        Double d1 = Double.valueOf(s.pop());

        Double d2 = Double.valueOf(s.pop());

        Double result = d1 + d2;

        System.Debug(d1 + ' + ' + d2 + ' = ' + result);

    } 

}

It should print:

5.0 + 10.0 = 15.0

Happy Stacking!