Greetings! Today, we're drawing back the curtains on Stacks in Java, a crucial data structure. A stack is like a pile of dishes: you add a dish to the top (Last In) and take it from the top (First Out). This Last-In, First-Out (LIFO) principle exemplifies the stack. Java executes stacks effortlessly using the Stack class from the java.util package. This lesson will illuminate the stack data structure, its operations, and their applications in Java. Are you ready to start?

To create a stack, Java employs a built-in data structure known as a Stack. For the Push operation, we use push(), which adds an element at the stack's end. For the Pop operation, there's the pop() function that removes the last element, simulating the removal of the 'top' element in a stack. Here's how it looks:

Java
Copy to clipboard
1import java.util.Stack;
2
3public class StackExample {
4    public static void main(String[] args) {
5        Stack<String> stack = new Stack<>(); // A new empty stack
6
7        // Push operations
8        stack.push("John");
9        stack.push("Mary");
10        stack.push("Steve");
11
12        stack.pop(); // Pop operation removes 'Steve'
13        System.out.println(stack); // Outputs: [John, Mary]
14    }
15}

In the example provided, we push 'John', 'Mary', and 'Steve' into the stack and then pop 'Steve' from the stack.

Stack operations go beyond merely push and pop. For example, to verify if a stack is empty, we can use the empty() method. If it returns true, that means the stack is empty. Conversely, if it returns false, we can infer the stack is not empty. To peek at the top element of the stack without popping it, we use the peek() method.

Here's an example:

Java
Copy to clipboard
1public class StackOperations {
2    public static void main(String[] args) {
3        Stack<String> stack = new Stack<>();
4        stack.push("Steve");
5        stack.push("Sam");
6        
7        System.out.println(stack.peek()); // Outputs: 'Sam'
8
9        System.out.println(stack.empty()); // Outputs: false
10        stack.pop(); // Remove 'Sam'
11        stack.pop(); // Remove 'Steve'
12        System.out.println(stack.empty()); // Outputs: true
13    }
14}

In this example, 'Sam' is added (pushed), and then the topmost stack element, which is 'Sam', is peeked.

Practical applications of stacks in Java are plentiful. Here is one of them — reversing a string.

We will push all characters into a stack and then pop them out to get a reversed string!

Java
Copy to clipboard
1public class ReverseString {
2    public static String reverseString(String input) {
3        Stack<Character> stack = new Stack<>();
4
5        for (char c : input.toCharArray()) {
6            stack.push(c);
7        }
8
9        StringBuilder reversedString = new StringBuilder();
10        while (!stack.empty()) {
11            reversedString.append(stack.pop());
12        }
13
14        return reversedString.toString();
15    }
16
17    public static void main(String[] args) {
18        System.out.println(reverseString("HELLO")); // Outputs: OLLEH
19    }
20}

A stack can be utilized to verify if parentheses in an expression are well-matched, i.e., every bracket has a corresponding pair. For example, parentheses in the string "()[{}]" are well-matched, while in strings "([]()", ")()[]{}", "([)]", and "[{})" they are not.

Let's break down the solution into simple steps:

We start by creating a HashMap that maps each closing bracket to its corresponding opening bracket and an empty stack. Then, we iterate over each character paren in the string parenString:

• If paren is an opening bracket, it gets appended to the stack.
• If paren is a closing bracket and the top element in the stack is the corresponding opening bracket, we remove the top element from the stack.
• If neither of the above conditions is met, we return false.

Finally, if the stack is empty (all opening brackets had matching closing brackets), we return true. If there are some unmatched opening brackets left, we return false.

Java
Copy to clipboard
1import java.util.HashMap;
2import java.util.Stack;
3
4public class ParenthesesBalance {
5
6    public static boolean isParenBalanced(String parenString) {
7        Stack<Character> stack = new Stack<>();
8        HashMap<Character, Character> openingParen = new HashMap<>();
9        openingParen.put(')', '(');
10        openingParen.put(']', '[');
11        openingParen.put('}', '{');
12
13        for (char paren : parenString.toCharArray()) {
14            if (openingParen.containsValue(paren)) {
15                // We met an opening parenthesis, just putting it on the stack
16                stack.push(paren);
17            } else if (openingParen.containsKey(paren)) {
18                // We met a closing parenthesis
19                if (stack.isEmpty() || stack.pop() != openingParen.get(paren)) {
20                    return false;
21                }
22            }
23        }
24        
25        return stack.isEmpty();
26    }
27
28    public static void main(String[] args) {
29        System.out.println(isParenBalanced("(())")); // Outputs: true
30        System.out.println(isParenBalanced("({[)}")); // Outputs: false
31    }
32}

Kudos to you! Covering the stack data structure, its operations, and their applications in Java is a commendable feat. Next up, you'll encounter practice exercises that will solidify your newly acquired knowledge. Dive into them and master Stacks in Java!