[Java] Stack concept and solving problem using the stack

Stack

What is Stack?

A stack data structure is much like an actual stack of plates.

The last plate you put on top of plates. That's going to be the first one you removed.
So the stack called LIFO(Last In First Out) data structure.

So the stack called LIFO(Last In First Out) data structure. The stack is linear data structures in that add element then another element sequentially. It has flexible size so it don’t need to allocate a fixed size like 50 initially. Also it can shrink it down when remove element.

What situations is it best or worst to use this data structure?

This is the best situation where you need to retrieve the last input data. Like forward and back button of web browser. On the other hand, the worst situation where you need to retrieve the first data you input.

Implementing a Stack

Stack need functions.
1) check the stack is empty before the node is going to be removed.
2) get the data top of the stack.
3) add node to the top of stack.
4) remove node at the top of stack.

public class Stack<E> {
    // We need thing can save data and link another thing.
    // It's a node. So I'm going to be make node as inner class because it just used in Stack class
    // We need thing can save data and link another thing. so I'm going to be make node
    private static class Node<E> {
        private final E element; // it's for saving data
        private Node<E> next; // it's for pointing next node.

        public Node(E element) {
            this.element = element; // The node needs data initially when was created.
            this.next = null; // Then next field for pointing previous node. so it is going to set when input the new node.
        }
    }

    // The stack is First In Last Out data structure.
    // So, it needs to know where is top.
    // Then, we can add and remove from the top.
    private Node<E> top = null; // remove node from the head

    // 1) We need check that stack is empty, before remove the node.
    public synchronized boolean isEmpty() {
        return top == null; // The top is null means empty because don't have node at removing point.
    }

    // 2) We need to get data of the first node. so I'm going to make method return the data of the first node.
    public synchronized E peek() {
        if (top == null){ // it can't access data when head is null, so let's throw the exception.
            throw new NoSuchElementException("Stack is empty");
        }
        return top.element;
    }

    // 3) Now, let's make method push a node to the last point.
    public synchronized void push(E element) {
        Node<E> node = new Node<>(element); // we need to create new node.
        node.next = top; // this new node point to an old top. because this new node gonna a become the top.
        top = node; // and then the top point to new node.
    }

    // 4) Also, let's make method remove the node. And it's going to return a data of top node.
    public synchronized E pop() {
        E data = peek(); // we can get the data of top node using peek method.
        top = top.next; // top need update to point down node. because top node is going to be removed.
        return data;
    }
}

Test code

The test scenario is as follows: 1) Stack instance initialization test. then check if the stack is empty.
2) Get the data of top node when stack is empty. then check if it throws an exception.
3) Input node then get the data of top node. then check if the input node's data matches the top node's data.
4) Input node then remove the data of the top node. then check if the stack is empty.
5) Input two nodes then get the data of the top node. then check if the top node was updated to the new node.
6) Input two nodes then remove the data of the top node. then check if the top node was updated to old top node.

class StackTest {  
    private Stack<Integer> stack;  

    @BeforeEach  
    void setUp() {  
        stack = new Stack<>();  
    }  

    // Let's express the test case as given, when, then.  

    /* 
    1) given: nothing    
    2) when: create stack instance    
    3) then: stack is empty    
    */    
    @Test  
    void valid_stack_initialization() {  
        assertTrue(stack.isEmpty());  
    }  

    /* 2)  
    given: empty stack    
    when: call peek method    
    then: throw NoSuchElementException   
     */    
    @Test  
    void get_data_from_empty_stack() {  
        assertThrows(NoSuchElementException.class, () -> stack.peek());  
    }  

    /* 3)  
    given: push node    
    when: call peek method    
    then: equal data of input node     
    */    
    @Test  
    void get_data_after_push_node() {  
        stack.push(10);  
        assertEquals(10, stack.peek());  
    }  

    /* 4)  
    given: push node    
    when: pop node    
    then: stack empty.     
    */    @Test  
    void remove_data_after_push_node() {  
        stack.push(10);  
        assertEquals(10, stack.pop()); // also check if pop return data of top node.  
        assertTrue(stack.isEmpty());  
    }  

    /* 5)  
    given: nothing    
    when: push two nodes    
    then: top node data equal last node data     
    */    
    @Test  
    void check_top_node_after_push_nodes() {  
        stack.push(10);  
        stack.push(20);  
        assertEquals(20, stack.peek());  
    }  

    /* 6)  
    given: nothing    
    when: push two nodes then pop node    
    then: top node data equal old top node data     
    */    
    @Test  
    void check_top_node_after_push_nodes_then_pop_node() {  
        stack.push(10);  
        stack.push(20);  
        stack.pop();  
        assertEquals(10, stack.peek());  
    }  
}

Solving problem using a stack

Problem: Is it Balanced Parentheses?

1. Understand test case and constraints

Ex) input -> output

{(){}()()} -> true
{(){]()} -> false

Constraints

1 <= s.length <= 104
Input string consists of parentheses only ()[]{}

2. Intuitive Understanding of the Problem

Here is an example of how a human might intuitively determine whether parentheses are balanced:

As shown, balanced parentheses occur when each pair of parentheses matches correctly. Initially, we rely on intuition to predict the output based on the input. This intuitive approach is often the fastest way for humans to grasp a problem.

3. Transitioning from Intuitive to Logical Problem-Solving

However, it’s challenging to directly match pairs of parentheses within a string array. A better approach would be to separate opening {, (, [ and closing }, ), ] brackets, making it easier to process them.

To do this, we can create a data structure to hold opening brackets. Then, as we iterate through the string:

Store opening brackets.
Compare closing brackets with the most recently stored opening bracket to see if they form a pair. If so, remove the opening bracket.

At the end of the string, if all stored opening brackets are removed, the parentheses are balanced.

4. Choosing the Right Data Structure

Now it’s time to decide on a data structure to implement the solution.

Data is input sequentially into the structure.
The last input is accessed for comparison.
Removal involves deleting the most recently added data.

These characteristics suggest using a stack, which allows easy addition, access, and removal of the last input. Thus, we store opening brackets in a stack.

5. Designing the Solution Logic

Iterate through the string character by character.
Push opening brackets onto the stack. When encountering a closing bracket, check if it matches the top of the stack.
If the brackets match, remove the top of the stack. Otherwise, return false.
At the end of the string, if the stack is empty and no unmatched brackets remain, return true.

6. Initial Implementation

To quickly implement the solution, the following code ensures proper functionality:

import java.util.Stack;

public class ValidBalancedParentheses1 {

    public static boolean isBalanced(String tokens) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < tokens.length(); i++) {
            char c = tokens.charAt(i);
            if (c == '{' || c == '[' || c == '(') {
                stack.push(c);
            } else if (c == '}' || c == ']' || c == ')') {
                if (stack.isEmpty()) {
                    return false;
                }
                char top = stack.peek();
                if (top == '{' && c == '}' || top == '(' && c == ')' || top == '[' && c == ']') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("{")); // false  
        System.out.println(isBalanced("}")); // false  
        System.out.println(isBalanced("{()[]()()}")); // true  
        System.out.println(isBalanced("{()[]()()")); // false  
        System.out.println(isBalanced("()[]()()}")); // false  
        System.out.println(isBalanced("{()[](]()}")); // false
    }
}
`

While writing the code, I noticed a potential issue: if a closing bracket is encountered and the stack is empty, the parentheses cannot be balanced. To address this, I added logic to return false when encountering an empty stack while processing a closing bracket.

7. Refactoring

To improve readability, performance, and eliminate redundant code, I refactored the initial implementation:

import java.util.Stack;

public class ValidBalancedParentheses2 {
    public static char[][] pairParentheses = { {'{', '}'}, {'(', ')'}, {'[', ']'} };

    public static boolean isBalanced(String tokens) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < tokens.length(); i++) {
            char c = tokens.charAt(i);
            if (isOpenParentheses(c)) {
                stack.push(c);
            } else if (isCloseParentheses(c)) {
                if (stack.isEmpty() || !isPairParentheses(stack.pop(), c)) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    private static boolean isPairParentheses(char openParentheses, char closeParentheses) {
        for (char[] pairs : pairParentheses) {
            if (openParentheses == pairs[0] && closeParentheses == pairs[1]) {
                return true;
            }
        }
        return false;
    }

    private static boolean isCloseParentheses(char c) {
        for (char[] pair : pairParentheses) {
            if (c == pair[1]) {
                return true;
            }
        }
        return false;
    }

    private static boolean isOpenParentheses(char c) {
        for (char[] pair : pairParentheses) {
            if (c == pair[0]) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("{")); // false  
        System.out.println(isBalanced("}")); // false  
        System.out.println(isBalanced("{()[]()()}")); // true  
        System.out.println(isBalanced("{()[]()()")); // false  
        System.out.println(isBalanced("()[]()()}")); // false  
        System.out.println(isBalanced("{()[](]()}")); // false
    }
}

Redundant Code Removal: Bracket pairs are pre-stored in pairParentheses, eliminating the need to repeatedly specify them.
Enhanced Readability: Separate methods for checking opening/closing brackets (isOpenParentheses() and isCloseParentheses()). Also a dedicated method, isPairParentheses(), for verifying pairs.
Performance Optimization: Instead of peek() and then pop(), pop() directly retrieves the top element, reducing redundancy and improving clarity.

Reference

John Park Devlog, 단순함으로 명쾌함을..!