The Stack Data Structure in Java

The stack is a fundamental data structure used in computer science.  In my opinion, it is one of the easier data structures to conceptually grasp and understand. Knowing and understanding how a stack works will not only make you a better programmer, it will also help you conceptualize problems in the future. It will become a great addition to your arsenal of data structures.  The implementation details will be written in Java.

Before continuing, readers should know about the linked list data structure. If you don’t know what a linked list is, please read my post on it before proceeding.

If there are any sections that lack detail, please shoot me a message or leave a comment. Lets dive straight into the meat!

Features of the Stack Data Structure

The stack data structure is a LIFO (Last-in, first-out) data structure, meaning that the last element that was placed onto the stack is the last to go out. It is similar to a deck of cards. When playing our favorite card games (such as Poker, Big two, solitaire, etc.), the dealer often draws the card from the top of the deck. The top card is always the first to go.

stack-of-cards

Stack of cards used to visually portray the stack data structure

The methods needed to be defined by a stack are the following

  • push(T data): Inserts data onto the top of the stack.
  • pop(): Pops off (or removes) the item at the top of the stack and returns that item.
  • peek(): Returns the item at the top of the stack. Think of it as peeking to look at the top card in a deck.

Also, it is often a good idea to also implement a size() and isEmpty() method, as these methods allow consumers of our API to keep track of the status of the stack.

Real Word Examples

The most common example that every Java developer has been exposed to is the call stack. For the sake of brevity, we will abbreviate it to CS. If we create a recursive function, each time the function is called, it is will be added onto the CS.  The last method/function that is called and returned is the first that will be popped off the CS. Let me illustrate this with a simple demonstration.

public static void main(String[] args) {
    System.out.println(factorial(5));   // Returns 120
}
private static int factorial(int num) {
    if (num == 1) {
        return 1;
    }
    return num * factorial(num - 1);
}

In the example above, we are calling the factorial method recursively. A recursive function is a function that calls itself. What happens is until we reach the base case: I.E. where the function actually returns a value the function will call itself. Each time a function calls itself, the function call is added onto the CS. Once the base case is reached, the last function call is popped off the call-stack and a domino effect occurs until we return with the actual value. Since each function call has its own scope, running a recursive function can be costly, because the memory continues to pile up on the CS until the base case is reached.

Call Stack on the Debugger

Below, is the call stack as shown in my IDE of choice – Intellij IDEA. The community version is free to use, but to access all of its features, you have to use the Ultimate version, which is pay to use. It is, in my opinion, by far the best Java IDE (far better than eclipse). Note that I am not affiliated with JetBrains.  Anyway, as you can see, this function calls itself recursively, until we reach the base case where the function returns an int value of 1. The method call that returned one will be first popped off the CS.

call-stack-factorial

Running the debugger on Intellij IDEA

Above is a snapshot of the CS right before we return the base case value of one. There are 6 functions on the CS. At the top, the base case function call is present. At the bottom is the main method. When 1 is returned, the [5] method will be popped off the CS and the value 1 will be plugged into the return statement on line 8. This process will repeat until we reach the base case which returns 120. Since this is a post on the stack data structure, I will not be going into details on how recursion works. In the future, I may write a post on recursion.

  • App.java: Used for running the main method.
  • Node.java: A wrapper class for the data, containing pointer to the next node.
  • Stack.java: The stack implementation class.
  • EmptyStackException.class: Custom exception class that is thrown when consumer attempts to call the pop method on an empty stack.

Implementation in Java

In this section, we will be implementing a basic stack. Internally, we will be using a linked list data structure (you can also implement a stack using arrays). For more information on linked lists, please check out the post on linked list.

Note that in the java.util package, the stack implementation extends Vector.

Therefore, we will not create a vector class. But remember, that it is good practice to program to an interface so that we are able to switch between multiple implementation of a concept at run-time. Our implementation will consist of the following classes.

The Node Class

Just as in my previous article for the linked list, this class is simply a POJO that is used to represent the data inserted. It contains a pointer to the next node, and since we are implementing the Stack with a linked list, the final node should point to null. The data is of a generic type so that we can insert any data that we want. The code itself should be pretty self-explanatory.

/**
 * @Author Jay
 */
public class Node<T> {

    private T data;
    private Node<T> nextNode;

    public Node(T data) {
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getNextNode() {
        return nextNode;
    }

    public void setNextNode(Node<T> nextNode) {
        this.nextNode = nextNode;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

The Stack Class

The general meat of the stack implementation If you have read my post on linked-lists, the code below will feel familiar. The stack class in its entirety is posted below. Please let me know if I am missing out on key details. The next couple of sub-sections will cover the key parts of a stack’s operations. The source code can be found here.

The Push() Method Explained

The push Method is one the fundamental methods of this data data structure. Without this method, the stack would lose all meaning as a LIFO data structure. Therefore, since it is so important, we will cover in detail how the push method works in the implementation above.  Essentially, the push method can be broken down into the following steps

  1. Create new node with new data. This is required in both cases below.
  2. Check if the stack is empty
    • If it is empty, simply append the new node and set it as the lastItem.
    • Otherwise, do the following steps
      1. Create the reference to the last item. This will be the second last element after the push method is executed. I.E.
        Node<T> prevLastItem = lastItem;
      2. Set the new node as the last item. I.E.
        lastItem = new Node<T>(newlyAddedData);
        • E.g. If “B” is added to a stack of size 1 with element “A” as the last item, before the add it will look like this: “A” –> null.
        • After adding “B”, it becomes the new last item.
      3. Set new last item’s next node to point to the previous last item created in step 1.

For the visual learners, I have provided a flow diagram illustrating how the push() method should work.

stack-push-flow-chart

Push() method flow diagram

Copyright © thecodingdelight.com

The Pop() Method Explained

The pop method works in the opposite way from the push method. It removes the last item from the stack and returns the value. If the audience has experience coding in JavaScript, it is very similar to how to built-in array’s pop() method works. Below are the steps on how the pop() method works in our implementation.

  1. Check if items exists (I.E. lastItem == null)
    • If it is empty, throw EmptyStackException.
    • Otherwise do the following
      1. Decrement the size of the stack.
      2. Check if a second last element exists. In another words, check if there are more than one items
        • If there are more than one items, point last item reference of the instance to the previous last item. E.g. If we are dealing with “A” –> “B” with B being the lastItem the following will happen:
          lastItem will point from B to A. Since nothing is pointing at B, it will be garbage collected.
        • Otherwise, simply set lastItem to null. This will remove the one and only item from the stack.
stack-pop-flow-chart-revised

Pop method float diagram Copyright © thecodingdelight.com

The Peek() Method Explained

The peek method is very simple: all we need to do is create a public method that returns the data to the item at the top of the stack. Although the API documentation is available for checkup when we forget what methods does, there is an easy way remember what peek() does. Think of it as peeking at the top card of a deck. When we play most card games such as poker, we usually want to know what the next card is. If we want to cheat, we do so by peeking at the top card, without burning/removing the stack from the deck. The peek method does exactly that! It returns the data at the top of the stack without removing it :).

Finally Testing the Implementation: App.class

Finally, all we need to do is to test the stack by running it on the main() method. If you want multiple implementations of the stack, you can do so by creating a Stack interface.

Remember to include the key methods that define a stack in your contract/interface. Just remember that this is not the only way to implement a stack, but only one way out of the many.

public static void main(String[] args) {

    Stack<Integer> numbers = new Stack<>();

    numbers.push(1);
    numbers.push(2);
    numbers.push(3);
    numbers.push(4);
    numbers.push(5);

    System.out.println("Size: " + numbers.size());

    numbers.print();

    System.out.println("Popping off the last element: " + numbers.pop() +
            ". Size is now: " + numbers.size());

    numbers.print();

    numbers.push(100);

    System.out.println("Popping off the last element: " + numbers.pop() +
            ". Size is now: " + numbers.size());

    numbers.pop();  // Popping off 4
    numbers.pop();  // Popping off 3
    numbers.pop();  // Popping off 2
    numbers.pop();  // Popping off 1

    // Throw Custom Exception
    try {
        numbers.pop();
    } catch (EmptyStackException e) {
        System.out.println(e.getMessage());
    }

    System.out.println("----------------------------------------------");

    Integer[] arrayOfNumbers = {10,9,8,7,6,5,4};
    // Initialize stack by passing array of numbers
    numbers = new Stack<>(arrayOfNumbers);

    numbers.print();

    System.out.println("The last element is: " + numbers.peek());

}

Source code

Click here for the source code. Once again, thanks for reading!

About the Author Jay

I am a programmer currently living in Seoul, South Korea. I created this blog as an outlet to express what I know / have been learning in text form for retaining knowledge and also to hopefully help the wider community. I am passionate about data structures and algorithms. The back-end and databases is where my heart is at.

follow me on:
1 Shares