Stack Data Structure in Java

What is a Stack?

There are many different types of data structures that can be used in programming, a stack being one. What is a stack? A stack is a last in first out type of data structure, also known as LIFO. Think of a stack like you are stacking books on a table, one on top of the other. When you go to remove books from the stack, you would take the top book of first, which is also the last book that you added to the stack. This process can also be referred to as a first in last out process, known as FILO, but the LIFO way of addressing a stack is more common in programming.

In programming, adding a new plate to the stack is called pushing. You push items on to the stack. To remove an item from the stack, this is called popping, so you pop an item off of the stack.

Where are Stacks Used in Programming?

You might be thinking to yourself, when would I use a stack in programming?

Web Browser Back Button
Undo Function in Word Processors
Syntax Validation in Programming IDE’s

A very common example of a stack is a web browser back button implementation. Every page you visit is pushed on to the stack. Whenever you press the back button to go backwards one page, the topmost element in the stack is popped off. This is very similar to the undo function that exists any many applications such as a word processor or image editing application. Another application is in a programming editor, the ability to check that you have a closing brace for all of your opening braces for example, this is another implementation of a stack data structure.

Visual Example of a Stack Data Structure

Let’s go through a visual example of a stack data structure so our understanding can be clear. In the graphic below, we first see an empty stack, then object 1 pushed on to the stack, followed by pushing object 2 and object 3. In the last part of the graphic, we see an object being popped from the stack, in this case, it’s object 3 since it was the last to be added. This is how the LIFO stack data structure operates.

Stack Data Structure Example of Push and Pop

How to Implement a Stack Data Structure

Now that we understand what a stack is and how it operates, your next question may be how do we implement a stack data structure in programming?

Many programming languages today already provide built into structures for Stacks. In Java this is provided in the package java.util.stack. This make implementing a stack in our code much easier than coding our own solution. To understand how a stack works in code though, we are providing an example using a linked list implementation in Java. We have a node class which forms objects that represents items on the stack, along with pointers and a stack class that keeps track of the current top node so it can be easily accessed.

Stack Using Linked List in Java

If you happen to be using Manjaro Linux as I am, you can follow this guide from the credibleDEV for Installing Java for VScode on Manjaro Linux.

// Node class, next pointer and value variable to hold the data
class Node {
    Node next;
    int value;
}

// Stack class which initializes the initial empty state of the stack and defines the push/pop methods
class Stack {

    // Declare top and size for tracking the current top node and the stack size
    private Node top;
    private int size;
    
    public Stack() {
        // Initialize empty stack, top=null, size=0
        this.top = null;
        this.size = 0;
    }
    
    // Push a new value onto the stack
    public void push(int value) {
        // Create a new node
        Node node = new Node();
        
        if (node != null) {
        
            // Set the value of the new node = value passed into push
            node.value = value;
            
            // Set the pointer for next on the new node to point to the node that is currently in the top position
            node.next = top;
            
            // Set the top pointer value to point to the new node which is now at the top
            top = node;
            
            // Increase node size counter
            this.size++;
        }
    }
        
    // Remove the top node from the stack
    public void pop() {
        // Verify the stack is not empty
        if (this.top != null) {
        
            System.out.println("Removing top entry, value of: " + this.top.value);
            
            // Reduce the stack size counter by 1
            this.size--;
            
            // Set the top node pointer to the next item in the stack
            this.top = (this.top).next;
        } else {
            // Catch the case that the pop method is called on an empty stack
            System.out.println("Stack empty, nothing to remove");
        }
    }

}
   
// Main Program class
class Main {
    public static void main(String[] args) {
    
        // Initialize a new stack instance called stack
        Stack stack = new Stack();
        
        // Push items 1,2,3 onto the stack
        stack.push(1);
        stack.push(2);
        stack.push(3);
        
        // Pop items 3,2,1 from the stack
        stack.pop();
        stack.pop();
        stack.pop();
    }
}

adamwhiles dot com