Java Stack Example (with video)

In this post, we feature a comprehensive Java Stack Data Structure Example.

1. Introduction

A stack data structure is a container of objects that are inserted and removed according to the last-in-first-out (LIFO) principle. In the stacks, only two operations are allowed-

• push the item into the stack
• pop the item out of the stack.

A stack is a limited access data structure. Elements can be added and removed from the stack only at the top. 

push adds an item to the top of the stack, pop removes the item from the top.

You can also check this tutorial in the following video:

A stack is a recursive data structure. Here is a structural definition of a Stack:

A stack is either empty or it consists of a top and the rest which is a stack

2. Stack in Collection class hierarchy

The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends Vector class with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top. When a stack is first created, it contains no items.

3. Stack Operations

Stack is a LIFO(Last In First Out) implementation of Vector class with 5 additional methods that allow a vector to be treated as a stack. These methods are push(), pop(), peek(), search() and empty(). Stack has only one constructor i.e. default constructor. We can create Stack Objects and use all five methods as follows.

3.1 Create a Stack

To use a Java Stack you must first create an instance of the Stack class. Here is an example of creating a Java Stack instance:

Stack<String> stackOfBooks = new Stack();

3.2 Push Element on Stack

Once you have a Java Stack instance, you can push elements to the top of the Stack. The elements you push onto the Stack must be Java objects. Thus, you actually push objects to the Stack.

You can use push() method to add elements into a Java Stack. Here is an example of pushing an element (object) onto a Java Stack:

Stack<String> stackOfBooks = new Stack();
stackOfBooks.push("Book 1");
stackOfBooks.push("Book 2");

Explanation: In the above example we have created a java Stack and then used it push() to add elements (book 1, book 2) into it. When we pushed book one into stack top of the stack gets incremented by one and start pointing to book 1. As soon as a new element book 2 gets pushed into stack top again gets incremented by one and start pointing to book 2. This is how the top of the stack always points to the latest element pushed onto the stack.

3.3 Pop Element from Stack

Once we are having an element in the stack, We can remove elements from the stack. This operation on the stack is called pop operation. As soon as one element gets popped from stack top of the stack will decrease its value by one to point to the next latest element into the stack.

We can use pop() from java Stack class to pop an element from the stack. here is an example-

pop() operation in Java Stack

// Creating empty stack
Stack stackOfBooks = new Stack();
// pushing elements into stack
stackOfBooks.push("Book 1");
stackOfBooks.push("Book 2");
System.out.println("Initial Stack: " + stackOfBooks);
//removing top element from stack
stackOfBooks.pop();
System.out.println("Updated Stack: " + stackOfBooks);
//removing top element from stack
stackOfBooks.pop();
System.out.println("Updated Stack: " + stackOfBooks);

Explanation: First we are creating an empty stack and then adding to elements(Book 1, Book 2) into the stack. again in the next set of lines, we are removing elements from the stack.

Result

Initial Stack: [Book 1, Book 2]
Updated Stack: [Book 1]
Updated Stack: []

3.3.1 EmptyStackException in java Stack

If the stack is empty and we try to pop an element from the stack. It throws EmptyStackException. Below is an example demonstrating the same-

EmptyStackException in Java Stack

// Creating empty stack
Stack stackOfBooks = new Stack();

// pop operation on empty stack. It leads to java.util.EmptyStackException
stackOfBooks.pop();

Explanation: In the above example we created an empty stack and trying to pop() an element from the stack. Since it is empty so code leads to EmptyStackException.

Result

Exception in thread "main" java.util.EmptyStackException
	at java.util.Stack.peek(Stack.java:102)
	at java.util.Stack.pop(Stack.java:84)
...
...

3.4 Peek at Top Element of Stack

We can use peek() of Stack class to get information about the top location element which is getting pointed by the top of the stack. Here is an example of peeking at the top of a Java Stack:

Peek() in Java Stack

Stack<String> stackOfBooks = new Stack();
stackOfBooks.push("Book 1");
stackOfBooks.push("Book 2");
System.out.println("Top of the stack is pointing to : "+ stackOfBooks.peek());

In the above example, we have created a stack of two books. Since Book 2 is pushed at last so the top of the stack is pointing to Book 2. When we call peek() in this example it will return Book 2.

Result

Top of the stack is pointing to : Book 2

3.5 Search the Stack

We can use the search() of the Stack class to find an element in the stack. search() return the distance of the element from the top of the stack. The distance is a 1 based index. If an element is present on the top of the element for this element search() will return 1. If we look for an element which doesn’t exist in the stack, search() method returns -1.

search() in Java Stack

        
Stack<String> stackOfBooks = new Stack();
stackOfBooks.push("Book 1");
stackOfBooks.push("Book 2");
System.out.println("Top of the stack is pointing to : " + stackOfBooks.peek());
System.out.println("Index of  Book 2 into  the stack is : " + stackOfBooks.search("Book 2"));
System.out.println("Index of  Book 4 into  the stack is : " + stackOfBooks.search("Book 4"));

Result

Index of  Book 2 into  the stack is : 1
Index of  Book 4 into  the stack is : -1

3.6 Iterate Elements of Stack

There are various ways to iterate Stack in java. Below are the options –

• Iterate over a Stack using Java 8 forEach().
• Iterate over a Stack using iterator().
• Iterate over a Stack using iterator() and Java 8 forEachRemaining() method.
• Iterate over a Stack from Top to Bottom using listIterator().

Iterating Stack

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

stackOfBooks.add("Book 1");
stackOfBooks.add("Book 2");
stackOfBooks.add("Book 3");
stackOfBooks.add("Book 4");

//Iterate over a Stack using Java 8 forEach() method
System.out.println("Iterate over a Stack using Java 8 forEach() method");
stackOfBooks.forEach(book -> {
    System.out.println(book);
});

//Iterate over a Stack using iterator()
System.out.println("Iterate over a Stack using iterator()");
Iterator<String> booksIterator = stackOfBooks.iterator();
while (booksIterator.hasNext()) {
    String book = booksIterator.next();
    System.out.println(book);
}

//Iterate over a Stack using iterator() and Java 8 forEachRemaining() method
System.out.println("Iterate over a Stack using iterator() and Java 8 forEachRemaining() method");
booksIterator = stackOfBooks.iterator();
while (booksIterator.hasNext()) {
    String book = booksIterator.next();
    System.out.println(book);
}


//Iterate over a Stack from TOP to BOTTOM using listIterator()
System.out.println("Iterate over a Stack from TOP to BOTTOM using listIterator()");
// ListIterator allows you to traverse in both forward and backward directions.
// We'll start from the top of the stack and traverse backwards.
ListIterator<String> booksListIterator = stackOfBooks.listIterator(stackOfBooks.size());
while (booksListIterator.hasPrevious()) {
    String book = booksListIterator.previous();
    System.out.println(book);
}

Result

Iterate over a Stack using Java 8 forEach() method
Book 1
Book 2
Book 3
Book 4
Iterate over a Stack using iterator()
Book 1
Book 2
Book 3
Book 4
Iterate over a Stack using iterator() and Java 8 forEachRemaining() method
Book 1
Book 2
Book 3
Book 4
Iterate over a Stack from TOP to BOTTOM using listIterator()
Book 4
Book 3
Book 2
Book 1

4. Application of a stack data structure

Below are a few real-life examples of stacks-

• Think of a stack of books; you can remove only the top book, also you can add a new book on the top.
• To reverse a word. You push a given word to stack – letter by letter – and then pop letters from the stack.
• An “undo” mechanism in text editors; this operation is accomplished by keeping all text changes in a stack.
• Wearing/Removing Bangles.

There are so many technical examples of using stack some of them are listed below-

4.1 Expression Evaluation

4.1.1 Postfix Evaluation Algorithm

1. Scan the expression left to right
2. Skip  values or variables (operands)
3. When an operator is found, apply the operation to the preceding two operands
4. Replace the two operands and operator with the calculated value (three symbols are replaced with one operand)
5. Continue scanning until only value remains–the result of the expression

4.1.2 Infix transformation to Postfix

1. Create an empty stack and an empty postfix output string/stream
2. Scan the infix input string/stream left to right
3. If the current input token is an operand, simply append it to the output string (note the examples above that the operands remain in the same order)
4. If the current input token is an operator, pop off all operators that have equal or higher precedence and append them to the output string; push the operator onto the stack.  The order of popping is the order in the output.
5. If the current input token is ‘(‘, push it onto the stack
6. If the current input token is ‘)’, pop off all operators and append them to the output string until a ‘(‘ is popped; discard the ‘(‘.
7. If the end of the input string is found, pop all operators and append them to the output string.

4.2 Backtracking

Backtracking is used in algorithms in which there are steps along some path (state) from some starting point to some goal. 

• Find your way through a maze.
• Find a path from one point in a graph (roadmap) to another point. 
• Play a game in which there are moves to be made (checkers, chess). 

In all of these cases, there are choices to be made among several options.  We need some way to remember these decision points in case we want/need to come back and try the alternative

Consider the maze.  At a point where a choice is made, we may discover that the choice leads to a dead-end.  We want to retrace back to that decision point and then try the other (next) alternative.

Again, stacks can be used as part of the solution.  Recursion is another, typically more favored, solution, which is implemented by a stack.

4.3 Memory Management

Any modern computer environment uses a stack as the primary memory management model for a running program.  Whether it’s native code (x86, Sun, VAX) or JVM, a stack is at the center of the run-time environment for Java, C++, Ada, FORTRAN, etc.

4.4 Method Call and Return Process

When a method/function is called

1. An activation record is created; its size depends on the number and size of the local variables and parameters.
2. The Base Pointer value is saved in the special location reserved for it
3. The Program Counter value is saved in the Return Address Location
4. The Base Pointer is now reset to the new base (top of the call stack prior to the creation of the AR)
5. The Program Counter is set to the location of the first bytecode of the method being called
6. Copies the calling parameters into the Parameter region
7. Initializes local variables in the local variable region

While the method executes, the local variables and parameters are simply found by adding a constant associated with each variable/parameter to the Base Pointer.

When a method returns

1. Get the program counter from the activation record and replace what’s in the PC
2. Get the base pointer value from the AR and replace what’s in the BP
3. Pop the AR entirely from the stack.

5. Evaluating Postfix expression using stack

As Postfix expression is without parenthesis and can be evaluated as two operands and an operator at a time, this becomes easier for the compiler and the computer to handle.

5.1 Evaluation rule of a Postfix Expression

1. While reading the expression from left to right, push the element in the stack if it is an operand.
2. Pop the two operands from the stack, if the element is an operator and then evaluate it.
3. Push back the result of the evaluation. Repeat it till the end of the expression.

5.2 Algorithm to Evaluate Postfix Expression

1. Add ) to postfix expression.
2. Read postfix expression Left to Right until ) encountered 
3. If the operand is encountered, push it onto Stack 
4. [End If]
5. If an operator is encountered, Pop two elements
   1. A -> Top element
   2. B-> Next to Top element
   3. Evaluate B operator A 
   4. push B operator A onto Stack
6. Set result = pop
7. END

5.3 Example

Let’s take an example postfix expression(456*+) to better understand the algorithm to evaluate postfix expression-

Evaluating Postfix expression using Stack

package com.javacodegeeks.examples.stack;

import java.util.Stack;

public class PostfixExpEvaluator {
    public static void main(String[] args) {
        char postfix[] = {'4', '5', '6', '*', '+', ')'};
        evaluatePostFixExpression(postfix);
    }

    private static void evaluatePostFixExpression(char postfix[]) {
        int A, B;
        Stack s = new Stack();

        for (int i = 0; postfix[i] != ')'; i++) {
            char ch = postfix[i];
            if (Character.isDigit(ch)) {
                s.push(ch - '0');
            } else if (isOperator(ch)) {
                A = s.pop();
                B = s.pop();
                int val = calculateValue(A, B, ch);
                s.push(val);
            }
        }
        System.out.println("Result of expression evaluation: " + s.pop());
    }

    private static int calculateValue(int a, int b, char ch) {
        int val = 0;
        switch (ch) {
            case '*':
                val = b * a;
                break;
            case '/':
                val = b / a;
                break;
            case '+':
                val = b + a;
                break;
            case '-':
                val = b - a;
                break;
        }
        return val;
    }

    private static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/';
    }
}

Result

Result of expression evaluation: 34

6. More articles

• ArrayList Java Example – How to use arraylist
• Java Array – java.util.Arrays Example (with Video)
• Java List Example
• Java Queue Example
• LinkedList Java Example

7. Download the Source Code

That was all about Java Stack example. Hope you have enjoyed it.

Last updated on May 03rd, 2021

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you our best selling eBooks for FREE!

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

and many more ....

I agree to the Terms and Privacy Policy

Sign up

Thank you!

We will contact you soon.