How to Implement Stack data structure in Java? Example Tutorial

The stack is one of the popular data structures which supports LIFO (Last In First OUT) operation. Due to the LIFO advantage, you can use a stack data structure to convert a recursive algorithm to an iterative one. The stack data structure is very easy to implement using an array or linked list, but you don't have to implement it on your own because Java already provides a Stack implementation in java.util.Stack class. This class is a subclass of the Vector class and you should use it whenever you need Stack for your production code, there is no point in inventing the wheel again when the focus is on developing your application.

At the same time, as a programmer and coder, you should also know how to implement your own stack by using a basic data structure like an array or linked list.

It's very important for a programmer to learn how to implement various data structures in his favorite programming language e.g. binary search tree, linked list, Stack, or Queue. They are also a popular coding interview question and you may encounter them when you do your next job interview.

Here we are implementing Stack in Java only from a coding interview perspective, if you ever need to use a Stack in your real-world Java application you should use the one from java.util package or from some third-party library like Eclipse Collections, GS collection, FastUtil, or Trove. They provide the high-performance implementation of various collection classes in Java.

Also, basic knowledge of essential data structure is also very important and that's why I suggest all Java programmers join a comprehensive Data Structure and Algorithms course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to fill the gaps in your understanding.

How to implement Your Own Stack in Java using an array? Example

Stack has following interface and supports operations like push(), pop(), contains(), clear() and size(). The pop() method will always return the last element added.

Since Java provides Generics to ensure type-safety, it's recommended to use Generics whenever you write a container class i.e. a class that holds objects of other classes e.g. this Stack class which can hold any type of object like String or Integer etc. 

While using this class you just need to tell the class which kind of object will be stored and the compiler will ensure that no other type of object will be stored in this stack.

I have used Generics here to show how you can write type-safe classes in Java, but if you need a refresher you can read this article before trying the code example given in this article.

Now, let's come to the crux of this example, the logic you need to build around array to implement various Stack operations like push, pop, contains, size, isEmpty, and clear. Since we are using array data structure to implement Stack, we will use an array to store all elements. 

Since the size of the array needs to be declared at the time of creating the array, we'll use a default capacity of 10. The user can also create Stack of any capacity by providing value in the constructor.


One of the key differences between array and Stack, the former is a static data structure where size cannot be changed once declared but Stack is a dynamic data structure, it can resize itself, but we are not implementing the same resize logic here to keep the program simple. 

You can check the code of Stack.java to see how it resize itself. It uses ensureCapacity() method to create a new array with 1.5 capacity when the threshold is breached, similar to the load factor of HashMap. After creating a new array, it just copies content from the old array to the new array.

Coming back to the implementation of Stack, the size(), clear() and isEmpty() implementation is straight forward. We keep a variable size, which is incremented when an element is added i.e. pushed into Stack, and decrement it when an element is removed i.e. popped from Stack. 

The value of the size variable is returned by the size() method and it shows how many elements are present in Stack.

Many programmers make a mistake here by returning the length of the array, which is incorrect because the length of the array is actually the capacity of Stack. The stack could be full or empty. So don't return the length of the array from the size() method. Similarly, the isEmpty() method will return true if the size is zero.

The implementation of the clear() method is a little bit tricky, some programmers make the container array is null but clear is supposed to clean the Stack so that we can reuse the same array. So instead of just declaring array = null, you should iterate over the array until the size and mark every element as null. You don't need to iterate the array until length, just iterating until the size is enough because the rest of the elements are already null.

Now, let's implement two of the most important operations from the array, the push() and pop() operations. The first thing, push() method does is it checks if Stack is full or not. If Stack is full i.e. size == length then it resizes the stack by creating another array of 1.5 times of original size and copying the content of the old array into a new array. 

I have used Arrays.copyOf() method to reduce the size of the array. This method copies the specified array, truncating or padding with nulls (if necessary) so the copy has the specified length.

If we have space, then we just store the element in the current index and increases the size. It's worth checking the clever use of the postfix ++ operator here, which first stores the element at the current slot and then increment the value. So, at the start, the size is 0 hence the first element will be stored at 0th index in array and size will become 1.

On the other hand, the pop() operation first checks if the array is empty, if it is empty then it returns null, otherwise it first reduces the size and then returns the value from the top of the stack i.e. current index. 

Instead of using postfix operator, here I have used prefix -- operator because size is always 1 more than the current index of the array. For example, if there is one element in the array then size is 1 but the index of the element is 0, hence we first reduce the size and then retrieve the value from the array.

One of the key things you should be aware of here is of memory leak caused by keeping a reference of already popped-out elements in Stack as shown in Effective Java. 

To prevent that we are assigning null to the current slot in the array e.g. array[size] == null. 

This will ensure that array is not keeping any reference to the object and if that is only referenced then object is now eligible for garbage collection.

One more thing you can do in the pop() method is to reduce the size of the array if it's too big. We reduce the size of the array if it is larger than the capacity but keep it 1.5 times of size to provide enough headroom for growth.

Finally, you can implement the contains() method by doing a linear search in Java. This method should return true if an element passed to this method exists in the Stack otherwise false. 

It simply iterates through the array using enhanced for loop and compares each element of Stack to the given object, if they equal using equals() method then it returns true.

Java Program to implement Generic Stack using Array

Here is one example of implementing Stack using an array in Java. In our example, we have three classes, first, the interface IStack to define operation supported by Stack implementation, second, the ArrayStack which implements this interface and support all operation by storing elements in the array, and third, the StackDemo class, which is our test class to demonstrate how you can use this Stack class in your Java program.

You can save these classes in separate files e.g. IStack.java, ArrayStack.java, and StackDemo.java or you can combine them in one class as I have done. Just remember that when you store them in separate files, the name of the file must be the same as the name of the public class.

StackDemo.java

import java.util.Arrays;

/**
 * Java program to test our Stack implementation. In this program
 * we add couple of elements and then print the Stack.
 *
 * @author Javin Paul
 */
public class StackDemo {

    public static void main(String[] args) {
        IStack<Integer> stackOfInteger = new ArrayStack<>();
        stackOfInteger.push(10);
        stackOfInteger.push(20);

        System.out.println("Stack of Integers : " + stackOfInteger);
    }
}

beck.java

/**
 * An interface to represent Stack data structure. We need to name it to
 * something other than Stack because there is already a class named Stack in
 * java.util package.
 * 
 * @author WINDOWS 8
 *
 * @param <T>
 */
interface IStack<T> {
    public boolean push(T value);

    public T pop();

    public boolean contains(T value);

    public int size();

    public void clear();

    public boolean isEmpty();

}

ArrayStack.java

/**
 * An implementation of Stack in Java using array. This class is generic,
 * so you can create Stack of Integer or Stack of String.
 * 
 * @author WINDOWS 8
 *
 * @param <T>
 */
class ArrayStack<T> implements IStack<T> {

    private static final int DEFAULT_CAPACITY = 10;
    private T[] store;
    private int size = 0;
    private int capacity;

    @SuppressWarnings("unchecked")
    public ArrayStack() {
        this.capacity = DEFAULT_CAPACITY;
        store = (T[]) new Object[DEFAULT_CAPACITY];
    }

    @SuppressWarnings("unchecked")
    public ArrayStack(int capacity) {
        this.capacity = capacity;
        store = (T[]) new Object[capacity];
    }

    @Override
    public boolean push(T value) {
        if (this.size >= store.length) {
            int newSize = size + (size >> 1);
            store = Arrays.copyOf(store, newSize);
        }

        // not only store value in Stack but also
        // increases size of the array, a good use
        // ++ operator which ensures that first
        // you store at current index and than
        // increment size.

        store[size++] = value;
        return true;
    }

    @Override
    public T pop() {
        if (size <= 0) {
            return null;
        }

        // again first we are reducing size and then getting value
        // from Stack, because size is always 1 more array index
        // because index starts at 0. So if you have just one
        // element in Stack, then valid index is zero but size
        // would be one.
        T value = store[--size];

        // make sure you dereference element at top of the stack
        // to prevent memory leak in Java
        store[size] = null;

        // shrinking array if its too big
        int reducedSize = size;
        if (size >= capacity && size < (reducedSize + (reducedSize << 1))) {
            System.arraycopy(store, 0, store, 0, size);
        }
        return value;
    }

    @Override
    public boolean contains(T value) {
        // check for an element in array using
        // sequential search algorithm
        boolean found = false;
        for (int i = 0; i < size; i++) {
            T element = store[i];
            if (element.equals(value)) {
                found = true;
            }
        }

        return found;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public void clear() {
        // make sure you release reference of all
        // element to avoid memory leak in Java
        for (int i = 0; i < size; i++) {
            store[i] = null;
        }
        size = 0;
    }

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

    /**
     * returns String view of Stack, fist element
     * is the top of stack
     */
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = size - 1; i >= 0; i--) {
            sb.append(this.pop());

            if (i > 0) {
                sb.append(",");
            }
        }
        sb.append("]");

        return sb.toString();
    }
}

Output:
Stack of Integers : [20,10]

JUnit tests for testing Stack data structure in Java

Now, let's test our Stack implementation by writing some unit tests using JUnit. Well, I did write them before writing code, just because I follow test-driven development sometimes, but it's your choice. 

You are always free to add more unit tests to cover more scenarios. If you are not familiar with test-driven development in Java, I suggest reading Test Driven: TDD and Acceptance TDD for Java developers, one of my favorite books on this topic.

Let me know if you find any bug on this Stack implementation using an array.

import static org.junit.Assert.*;

import org.junit.Test;

public class StackTest {

    @Test
    public void size() {
        IStack<Integer> myStack = new ArrayStack<Integer>();
        assertTrue(myStack.size() == 0);

        myStack.push(1);
        assertEquals(1, myStack.size());
    }

    @Test
    public void isEmpty() {
        IStack<Integer> newStack = new ArrayStack<Integer>();
        assertTrue(newStack.isEmpty());

        newStack.push(2);
        assertFalse(newStack.isEmpty());

        newStack.pop();
        assertTrue(newStack.isEmpty());
    }

    @Test
    public void clear() {
        IStack<Integer> aStack = new ArrayStack<Integer>();
        assertTrue(aStack.isEmpty());

        aStack.push(2);
        assertFalse(aStack.isEmpty());

        aStack.clear();
        assertTrue(aStack.isEmpty());
    }

    @Test
    public void pushAndPop() {
        IStack<String> bStack = new ArrayStack<String>();
        assertEquals(0, bStack.size());
        
        bStack.push("one");
        assertEquals(1, bStack.size());
        bStack.push("two");
        assertEquals(2, bStack.size());
        
        assertEquals("two", bStack.pop());
        assertEquals("one", bStack.pop());
        assertEquals(0, bStack.size());
    }
}

That's all about how to implement Stack data structure in Java using Array. It's also a good example to improve your coding skill because implementing fundamental and advanced data structure in Java is not a trivial exercise, they make you think and also challenges your coding technique. 

You can not only learn about data structure and algorithms but also develop the coding sense which is the biggest strength of a programmer. If you want to learn more about Stack and other data structures, I suggest you reading Introduction to Algorithms by Thomas H. Cormen. It contains a wealth of information about essential data structures, which you won't find anywhere.



Other Data structure and Algorithms Tutorials for Java programmers

• When to use ArrayList vs LinkedList in Java? (answer)
• How to find if a single linked list contains a loop? (solution)
• How to reverse a linked list in Java? (tutorial)
• How to find the first and last element of a linked list in Java? (solution)
• How to remove duplicate elements from the array in Java? (tutorial)
• How to find the middle element of the linked list in one pass? (solution)
• How to reverse an array in place in Java? (tutorial)
• How to search elements inside a linked list in Java? (solution)
• What is the difference between LinkedList and ArrayList in Java? (answer)
• How to implement pre-order traversal of a binary tree using iteration and recursion? (solution)
• How to implement post-order traversal in Java? (solution)
• How to print all leaf nodes of a binary tree in Java? (solution)
• How to find all pairs in the given array whose sum is equal to a given number? (solution)

Thanks for reading this article. If you like this article then please share it with your friends and colleagues. If you have any questions, feedback, or suggestion then please drop a comment and I'll try to answer it. 

And lastly one question for you, which data structure you have so far implemented on your own in Java? linked list, binary search tree, stack, queue, heap? Let me know in comments and if you haven't done so, try it now. It will definitely improve your coding skill and expand your knowledge.