Data structures and algorithms in Java

This article covers basic information on java.util.Stack data structure, common operations performed on the stack, an algorithm along with a code snippet of the most common application of Stack data structure. It also discusses the performance and time complexity of the algorithm and few other applications of Stack.

Prerequisites :

Basic knowledge of Java and data structures.

Definition :

Stack is a linear data structure where operations are performed in a particular order i.e. LIFO (Last In First Out) or FILO (First In Last Out). Which means the last element that is inserted is the first element that is removed.

Common operations performed on stack data structure:

Push: Adds a new element to the stack. If the stack is full then it is said to be a stack overflow condition.
Pop: Removes an element from the stack. If the stack is empty then it is said to be a stack underflow condition.
Peek: View the top element of the stack.
isEmpty: Checks if the stack is empty.
isFull: Checks if the stack is full.

To learn more about the internal implementation about stack data structure visit https://hetalrachh.home.blog/2020/01/04/java-util-stack-common-operations/

Common application of stack :

Check a well formed expression. Number of opening brackets of each type should be equal to the number of closing brackets of the respective type and the order of the brackets should be correct.

Examples :

(ABC){DEF} [XYZ(LMN)] – well formed expression as the number of opening and closing brackets are equal and the order in which the brackets open and close is well balanced.

(ABC{DEF} [XYZ(LMN)] – not well formed as the number of opening ‘(‘ brackets is not equal to the number of closing ‘)’ brackets, hence not balanced.

(ABC){DEF} [XYZ(LMN)]} – not well formed as the number of opening ‘{‘ brackets is not equal to the number of closing ‘}’ brackets, hence not balanced.

Algorithm :

Declare a map matchingParenMap and initialize it with closing and opening bracket of each type as the key-value pair respectively.
Declare a set openingParenSet and initialize it with the values of matchingParenMap.
Declare a stack parenStack which will store the opening brackets ‘{‘, ‘(‘, and ‘[‘.
Now traverse the string expression input.
- If the current character is an opening bracket ( ‘{‘, ‘(‘, ‘[‘ ) then push it to the parenStack.
- If the current character is a closing bracket ( ‘}’, ‘)’, ‘]’ ) then pop from parenStack and if the popped character is equal to the matching starting bracket in matchingParenMap then continue looping else return false.
After complete traversal if no opening brackets are left in parenStack it means it is a well balanced expression.

Code snippet :

Below is the code snippet for checking matching parenthesis using java.util.Stack class which provides the features of a stack data structure.

//map for storing matching parenthesis pairs
private static final Map<Character, Character> matchingParenMap = new HashMap<>();

//set for storing opening parenthesis
private static final Set<Character> openingParenSet = new HashSet<>();

static {
     matchingParenMap.put(')','(');
     matchingParenMap.put(']','['); 
     matchingParenMap.put('}','{'); 
     openingParenSet.addAll(matchingParenMap.values());  
}

//check if parenthesis match
public static boolean hasMatchingParen(String input) {
  try {
     //stack to store opening parenthesis
     Stack<Character> parenStack = new Stack<>();
     
     for(int i=0; i< input.length(); i++) {
        char ch = input.charAt(i);

        //if an opening parenthesis then push to the stack
        if(openingParenSet.contains(ch)) {
             parenStack.push(ch);
        } 

        //for closing parenthesis
        if(matchingParenMap.containsKey(ch)) {
             Character lastParen = parenStack.pop();
             if(lastParen != matchingParenMap.get(ch)) {
                return false;
             } 
        }
     }

     //returns true if the stack is empty else false
     return parenStack.isEmpty();
   }
     catch(StackOverflowException s) {}
     catch(StackUnderflowException s1) {}
     return false;
}

Other implementations of stack methods :

//method to check if the stack is empty
public boolean isEmpty() {
   return size==0;
}

//method to check if the stack is full
public boolean isFull() {
   return size==MAX_SIZE;
}

//method to get the size of the stack
public int getSize() {
   return size;
}

Performance and complexity of matching parenthesis code snippet :

Time complexity = O(N), N = length of input string because the entire string of length N is processed.
Space complexity = O(N), N = number of elements.
push() and pop() operations have constant time complexity i.e. O(1) because irrespective of the input parenthesis it always takes only one operation to push or pop an element from the stack.
isEmpty(), isFull(), getSize() have constant time complexity i.e. O(1) if size variable is maintained, it can be easily checked by comparing size variable with MAX_SIZE of the stack. If size variable is not used then complexity = O(N), N = number of elements, which requires counting the number of elements present in the stack.

Applications of stack:

Implementing undo in any application: In word processor application, color or font can be undo ed. Undo operation is performed by popping the last element of the stack.
Implementing back button in browsers: Keep adding the visited URL’s in the stack. And when you click the back arrow in browser pop an element from the stack and load the previous URL.

Here is the link to my github profile containing the code snippet shown above, Stack data structure in Java.

Please post comments below if you want to share any more information on the above topic discussed. Happy learning..!!