The Stack in Java

In this post we look at the stack in Java, a data structure that operates on the LIFO principle.

We discuss (clicking the link will take you to the section):

• What is a Stack
• How to implement a Stack using collections and deque
• How to implement a Java stack from scratch

What is a Stack in Java

A stack is a data structure where data is added and removed according to the last-in, first-out principle. You push elements on top of the stack and pop them off the stack. A stack can be implemented using a variety of data structures in Java. There is also a dedicated stack class in the Java collections module.

A stack is generally expected to support the following operations:

• Push a new element on top of the stack
• Pop an element off of the stack
• Retrieve the current size or height of the stack
• Peek at the first element in the stack
• Check if the stack is empty

How to Create a Stack in Java

Create a Java Stack using the Collections Module

Using the Java collections module you can create a stack using the dedicated stack class.

import java.util.Stack;

...

Stack stack = new Stack();

Push

Now that the stack has been created, you can push objects on top of it using the push method. The stack we’ve created doesn’t specify a type. At runtime, you can push any type of object you like onto the stack.

stack.push("String");
stack.push(1);

Pop and Peek

If the stack contains objects, you can retrieve and remove them using the pop method.

Object element = stack.pop();

If you just want to retrieve the first element without removing it, you can use the peek method.

Object element = stack.peek();

Specifying Generic Types for the Stack

As you may have noticed, we are retrieving generic Java objects from the stack. Since the stack accepts any type of object, we don’t know what object we get when we pop them off the stack.
Creating a stack without type constraints is a practice I wouldn’t recommend. Once you need to retrieve objects, you need to peek at the first element, check the type, retrieve, and subsequently cast it at runtime. Otherwise, you get a generic Java object, which isn’t very useful in most cases.

if(stack.peek() instanceof String ) {
    String topElement = (String) stack.pop();
}

The code that subsequently makes use of these objects needs to be designed to check or accept any type of object.

Instead, you can constrain the stack to only accept a certain type of element.

Stack<String> stack = new Stack<String>();

Now you can only push objects of type string onto the stack, but once you pop elements, you can be sure to get a string.

stack.push("String");
String string = stack.pop();

Retrieve the Size of the Stack

Using the size method you can retrieve the number of elements that are currently on the stack.

Stack<String> stack = new Stack<String>();

stack.push("String");
stack.push("String");

int size = stack.size();
System.out.println(size);

Here is the result:

Iterating and Searching the Stack

The stack class also comes with an inbuilt iterator object. The iterator exposes methods such as next() that you can use to iterate over the elements in the stack.

Stack<String> stack = new Stack<String>();

stack.push("String1");
stack.push("String2");
stack.push("String3");

Iterator it = stack.iterator();
while(it.hasNext()){
    String s = (String) it.next();
    System.out.println(s);
}

Note that the iterator doesn’t keep track of the type of object contained in the stack. Therefore we have to cast the element retrieved to a string. We can do this safely since we have previously type-constrained the stack to only contain strings.

Iteration can be used to find specific elements. But the stack class also offers an inbuilt method that finds an object and returns its index in the stack.

Stack<String> stack = new Stack<String>();

stack.push("String1");
stack.push("String2");
stack.push("String3");

int i = stack.search("String3");
System.out.println(i);

Since the element String3 is on top of the stack, this returns the index 1.

In other words, we have to pop only one item off the stack to get to the item we want. Since this a stack, where items are piled on top of each other, we can’t just go in and pull out an element. So if the index was three, we would have to pop the two items above off the stack to get to the element we want.

Create a Stack using Java Deque

Java util offers a deque data structure, which can be used in place of a variety of data structures including stacks. The deque offers all the main stack methods including peek, push, pop and size.

Deque<String> stack = new ArrayDeque<String>();

stack.push("String1");
stack.push("String2");
stack.push("String3");

System.out.println(stack.size());
System.out.println(stack.peek());
System.out.println(stack.pop());

Implement a Java Stack from Scratch

We can create our own stack class using Java’s array to hold the elements. We start by defining a public class named CustomStack with two private variables. The first variable is an array that holds our data. The second variable is an integer that keeps track of the index of the top of the stack. In the constructor, we require the user to specify the size of the array. The top element initially is -1 when the stack is empty. We set it to minus 1 because Java starts indexing from 0. So when the first element is added, the index of the top equals 0.

public class CustomStack {

    private int array[];
    private int top;

    CustomStack(int size) {
        array = new int[size];
        top = -1;
    }

}

The method to retrieve the size of the stack is the easiest to implement, and it helps us with the implementation of further methods.

public int size(){
    return top +1;
}

Next, we need a method to check whether the array is full. This is important for the push method because we need to check whether there is still space available on the stack before adding a new item. Otherwise, we’ll run into an “index out of bounds” exception.

To make sure that the stack is empty, the size of the stack needs to be smaller than the array contained in it.

public Boolean isFull(){
    if(size() < array.length){
        return false;
    }
    System.out.println("Stack is Full");
    return true;
}

Now we can finally implement push to add new elements to the stack.

public void push(int element) {
    if(!isFull() ) {
        top++;
        array[top] = element;
    }
}

Let’s test our implementation so far. We create a stack of size 2 but attempt to push three elements onto the stack and retrieve the size. This way, we are testing all methods we have implemented so far. We expect that the last push is caught by if statement using the isFull method, which in turn uses the size method. In total, the stack should only have a size of 2.

public static void main(String args[]) {
    CustomStack stack = new CustomStack(2);
    stack.push(4);
    stack.push(5);
    stack.push(6);

    System.out.println(stack.size());

}

To implement the pop method we first need a way to check that the stack is not empty. We cannot pop anything off a stack that has no elements.

public Boolean isEmpty(){
    if(size() == 0) return true;
    return false;
}

Note the succinct one-line notation in the if statement. If you only have one statement inside an if statement, you don’t need square brackets.

With the isEmpty method in place, we can finally implement the pop method. We check whether the stack is not empty. Then we return the element on top and subsequently decrement the top index by one. The top– index tells the array to retrieve the top element and then decrement top by one. If we had placed the double minus before top –top, Java would have decremented top before using it as an index to retrieve an element.

public int pop(){
    if(!isEmpty()) {
        return array[top--];
    }
    return -1;
}

We check whether our implementation works by pushing one element onto the stack and subsequently attempting to retrieve 2 elements using pop. The first pop should give us the element we pushed, while the second pop should return -1 since the stack is empty.

public static void main(String args[]) {
    CustomStack stack = new CustomStack(2);
    stack.push(4);
    System.out.println(stack.pop());
    System.out.println(stack.pop());

}

Having implemented pop, peek is fairly simple. It is the same method as pop without decrementing the top index.

public int peek(){
    if(!isEmpty()) {
        return array[top];
    }
    return -1;
}

That’s it. Our custom stack is complete. Here is the complete code.

public class CustomStack {

    private int array[];
    private int top;
    
    CustomStack(int size) {
        array = new int[size];
        top = -1;
    }
    
    public int size(){
        return top +1;
    }

    public void push(int element) {
        if(!isFull() ) {
            top++;
            array[top] = element;
        }
    }
    
    public Boolean isFull(){
        if(size() < array.length){
            return false;
        }
        System.out.println("Stack is Full");
        return true;
    }

    public Boolean isEmpty(){
        if(size() == 0) return true;
        return false;
    }

    public int pop(){
        if(!isEmpty()) {
            return array[top--];
        }
        return -1;
    }

    public int peek(){
        if(!isEmpty()) {
            return array[top];
        }
        return -1;
    }
}