What's Wrong With Stack in Java and Kotlin?

This is a story about me accidentally crossing paths with the Stack API in Java and Kotlin. Whether you are a seasoned Java and/or Kotlin developer or are just beginning to test the waters. I promise you that by the end of this blog I will convince you to never touch the Stack class in Java/Kotlin even with a ten-foot poll.

Before we dive right in, let’s brush up our memory real quick so that we can enjoy the rest of the show.

What is a Stack?

In computer science, a Stack refers to a data structure for maintaining a collection of elements and it majorly supports these two operations:

push, which allows you to add an element to the collection, and
pop, which allows you to remove an element from the top of the collection.

Based on this information, we can say that it follows a LIFO (last in first out) strategy.

Next, let’s look at some common applications of stacks in real life.

Where are Stacks used?

Expression Evaluation & Conversion

We use stacks to evaluate infix, postfix and prefix expressions. Further, you can also convert from one type of expression to another using a stack.

Syntax Parsing

Compilers use a stack to parse the syntax of expressions in the source code.

Backtracking

If you are solving a problem to find a path in a maze. You can use a stack to backtrack the path if you hit a wall.

Parenthesis Checking

To validate if a parenthesis is opening and closing correctly, a Stack is pretty handy.

Now there are many more creative applications of stacks in real life but for the scope of this blog these should suffice.

Time to dive into some code.

Reverse a String

Now to keep the example simple to follow, let’s say we want to reverse a string.

Imagine we get “hello world” as the input. Our method should return “dlrow olleh“.

Here goes the code to do that

public class Main {
    public static void main(String[] args) {
        System.out.println(reverse("hello world"));
    }
    
    public static String reverse(String input) {
        Stack<Character> stack = new Stack();
        
        for (char c : input.toCharArray()) {
            stack.push(c);
        }
        
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        
        return sb.toString();
    }
    
}

Running the above code, should give you the following output

dlrow olleh

So far so good? 😎 From here on, things will only go south.

Randomly Accessing a Stack

What do you think will happen if you were to do this?

public class Main {
    public static void main(String[] args) {
    
        String input = "hello world";
        
        Stack<Character> stack = new Stack();
        
        for (char c : input.toCharArray()) {
            stack.push(c);
        }
        
        int top = stack.size() - 1;
        int bottom = 0;
        
        System.out.println("Char on top " + stack.get(top));
        System.out.println("Char at the bottom " + stack.get(bottom));
        
    }
    
}

Do you think it fail to compile?
Will it throw an exception at runtime?
Or Do you think it will execute and output the following text:
Char on top d
Char at the bottom h

Now, before you try to answer the question. Let me make it clear that, I am trying to access the elements of the Stack by their position, as if it was an Array or an ArrayList in Java.

If you picked option 3, you are ✅. In Java and Kotlin, you can randomly access elements in a Stack.

Let’s make things more interesting. By trying to iterate over this stack.

Iterating Over a Stack

If you were to try to execute this piece of code, what do you think will happen?

public class Main {
    public static void main(String[] args) {
    
        String input = "hello world";
        
        Stack<Character> stack = new Stack();
        
        for (char c : input.toCharArray()) {
            stack.push(c);
        }
        
        Iterator it = stack.iterator();
        while (it.hasNext()) {
            System.out.print(it.next());    
        }

    }
    
}

Can you say which of the two following outputs, would this execution produce?

hello world
dlrow olleh

If you picked option 1, you are ✅. Even though your intuition would tell you otherwise, Java and Kotlin would print the elements in the FIFO (first in first out) order. 🙈

Why are Stacks Misbehaving?

Java like any other language was written by human engineers. Just like we do, they also made a bad design decision. The decision was to extend Stack class with Vector class.

This is the reason why we have random access in the Java and Kotlin Stacks and a FIFO strategy based iterator.

Also, this is not something new but a very old bug, which was actually reported back in 2001. However, it was closed with the following comment:

It was an incorrect design decision to have Stack extend Vector (“is-a” rather than “has-a”). We sympathize with the submitter but cannot fix this because of compatibility.

If you are interested in the bug ticket, here it is [JDK-4475301].

Stack is a Class and not an Interface!

Unlike most of the collections including but not limited to Lists, Maps and Queues, Stack is not an interface. This means that if you use it in your code, you are committing to the implementation itself. This can bite you at some point of time in future, should you feel a need to move away from it.

Before moving further, let’s quickly recall the problems with the Stack class in Java and Kotlin.

Stacks allow random access to the elements.
Iterator of the stack follows FIFO strategy and not LIFO strategy.
Stack exists as a Class and not an Interface in Java and Kotlin.

What Should You Use Instead?

Both Java and Kotlin offer an interface called Deque. It is short for “double ended queue” and is we usually pronounce it as “deck”.

It can be serve as a LIFO (last in first out) based collection, also referred to as a Stack. In fact the official java documentation recommends this interface over the legacy Stack class.

This interface should be used in preference to the legacy Stack class.

Another consistency it brings along is that there is no random element access. The iterator also returns elements in the order from first (head) to last (tail).

So next time you encounter a problem where you want to use a Stack, remember not to use the Stack class directly but a Deque.

I was super amazed when I came across this information, especially because I have been writing Java code for over 7 years and I must confess I didn’t know this until very recently.

I am sure you and me aren’t the only ones who didn’t know this. Simply tweet this article out and tag as many people as you think may not know this and wait for their confessions 😄

For more such blogs you can follow me Twitter or connect with me on LinkedIn.