Java Stack

In this article, we’ll go through Java Stack data structure, through detailed examples.

1. What is a Java Stack?

A Java Stack is a LIFO(Last-In-First-Out) data structure which means that the last inserted item will be the first item that we will be able to remove from the stack or just peek at it. Moreover, as you should have already guessed, it maintains the insertion order.

An example of a real-life stack could be a stack of books as shown below:

In order to achieve this specific state, we would need to do the following:

1. Push the “Clean Code” into the stack
2. Push the “Effective Java” into the stack
3. Push the “Java: A Beginners’ Guide, Eighth Edition” into the stack
4. Push the “Thinking in Java” into the stack

Unlike in real life where you can grab any book and don’t destroy the stack, in Java, you would be able to remove the books only in reverse insertion order:

1. Remove the “Thinking in Java” from the stack
2. Remove the “Java: A Beginners’ Guide, Eighth Edition” from the stack
3. Remove the “Effective Java” from the stack
4. Remove the “Clean Code” from the stack

Nevertheless, you can traverse the stack and see what items it contains.

Last but not least, the Java Stack class extends the Vector class(therefore it is synchronized and is a type of List) and offers the following methods:

• push – to push an item to the stack
• pop – to remove an item from the stack
• peek – to retrieve an item from the stack without removing it
• empty – to check if the stack is empty
• search – to find an item in the stack

Of course, we will see in the next sections how these methods work.

An important note here is that as per Oracle docs, the Deque interface provides implementations with more complete and consistent LIFO operations, therefore, they should be favored against the Stack class.

2. Java Stack Example

// Create a stack
Stack<String> books = new Stack<>();

//Add books to stack
books.push("Clean Code");
books.push("Effective Java");
books.push("Java: A Beginners' Guide, Eighth Edition");
books.push( "Thinking in Java");

// Look the item on the top
String thinkingInJava = books.peek();

//Search the stack for "Java: A Beginners' Guide, Eighth Edition"
int index = books.search("Java: A Beginners' Guide, Eighth Edition"); // 2

//Check the size using inherited size()
int size = books.size(); // 4

//Remove 2 items of the stack
books.pop();
books.pop();

//Try to remove using vector method, does nothing
books.remove("Java: A Beginners' Guide, Eighth Edition");

//Remove the rest 2 items
books.pop();
books.pop();

//Check if is empty
boolean isEmpty = books.empty(); //true

In the example above, we demonstrated how to create a stack(since Stack has only an empty constructor, there is no other way). Then we pushed the 4 books, peeked at the item on the top, searched for an item, and removed two items. In the end, we tried to remove using the inherited method and as expected, it did not remove the item as it was not allowed(it wasn’t on top).

3. Java Stack Methods

In this section, we will take a deeper look at each method that is implemented inside the Stack class.

3.1 Java Stack Push

This method is used to add items to the stack

• It accepts the element to be inserted
• Returns the element that was inserted
• Has complexity O(1)

//Push a book
String cleanCode = books.push("Clean Code");

3.2 Java Stack Pop

This method is used to remove items from the stack.

• It accepts no arguments
• Returns the element that was removed
• Throws an EmptyStackException if the stack is empty
• Has complexity O(1)

//Remove a book
String cleanCode = books.pop();

3.3 Java Stack Peek

This method works just like pop and has the same complexity but with one big difference: it does not remove the element from the stack.

//Push a book
String cleanCode = books.push("Clean Code");
//Peek the book
String cleanCode = books.peek();
//Peek again
// it will return "Clean Code"
String cleanCode = books.peek();

3.4 Java Stack Search

This method is used to search for an item in the stack.

• It accepts the element to be searched
• Returns a 1-based index of the element that was found where 1 is the item on top and n is the item on the bottom. It returns -1 if the element was not found in the stack
• Has complexity O(n) , as it would require going through all the items in a worst-case scenario.

//Add books to stack
books.push("Clean Code");
books.push("Effective Java");
books.push("Java: A Beginners' Guide, Eighth Edition");
books.push( "Thinking in Java");

// 1
int topBook = books.search("Thinking in Java");
// 2
int secondBook = books.search("Java: A Beginners' Guide, Eighth Edition");
// 3
int thirdBook = books.search("Effective Java");
// 4
int bottomBook = books.search("Clean Code");
// -1
int missingBook = books.search("The C++ Programming Language");

3.5 Java Stack Empty

This method just returns true if the stack has no elements:

books.push("Clean Code");
books.push("Effective Java");
// Stack has elements inside
// false
boolean empty = books.empty();
// Remove all the items from the stack
books.pop();
books.pop();
// true
empty = books.empty();

4. How to Traverse a Java Stack

You have five options if you’d like to traverse a stack in Java:

1. Using For Each Loop

for(String book : books) {
    System.out.println(book);
}

2. Using an Iterator

var it = books.iterator();
while (it.hasNext()) {
    System.out.println(it.next());
}

3. Using a ListIterator

var listIt = books.listIterator();
while (listIt.hasNext()) {
    System.out.println(listIt.next());
}

4. Using a SplitIterator

books
        .spliterator()
        .forEachRemaining(System.out::println);

5. Using a Java 8 forEach

books.forEach(System.out::println); 
//or
books.stream().forEach(System.out::println); 

5. When to Use a Stack in Java

The most common use-case of stack is backtracking or undoing things. You can think of any editor that you might be using that allows a undo operation, most commonly the Ctrl + Z shortcut.

Now consider a scenario in which writing a whole word or typing space is a single action:

• You wrote the word “You”
• Then you typed a space
• Then you wrote the word “Learn”
• Then you typed a space
• Then you wrote the word “Code”

Now let’s say you would like to undo the " Code" that you wrote; you would just need to remove the last two items that you pushed to the stack:

From the above, you can understand that the stack data structure is a perfect fit for undoing things.

In the same fashion, another scenario in which a stack would be useful is when you are trying to find a solution for a problem that has specific steps. With this in mind, a perfect example is finding a way out of a labyrinth as you could try the following approach:

• Each time you are faced with the requirement to choose a path:
  • Choose a random path(push the path you choose to the stack):
    • If this path is a dead end, backtrack(remove from the stack the path that you chose before) and try a different path than the path you chose before.
    • If this is not a dead end, you will have to choose again a random path and repeat the previous steps.

6. Conclusion

After reading this article, you should know what is a stack, how it works and what are its unique characteristics. Moreover, you know when you should use a stack and what is the time complexity of each operation.

7. Sources

[1]: Stack(Java SE 18 & JDK 18) – Oracle