WebsiteLogo

Data Structures: Arrays, Lists, and Stacks in Java

Implementation and application of fundamental data structures like arrays, ArrayLists, and Stacks in Java for solving competitive programming problems.

⬅ Previous Next ➡

Stacks in Java and Competitive Programming

What are Stacks?

A stack is a fundamental data structure in computer science that follows the Last-In, First-Out (LIFO) principle. Imagine a stack of plates; you can only add or remove plates from the top. The last plate you put on the stack is the first one you take off.

Stacks in Java

Java provides the Stack class in the java.util package. This class implements the stack data structure. Alternatively, you can use the Deque interface (specifically, the ArrayDeque implementation) for generally better performance, especially in concurrent scenarios. Using Deque provides more flexibility.

Here's a brief overview of both approaches:

Using java.util.Stack

 import java.util.Stack;

public class StackExample {
  public static void main(String[] args) {
    Stack<Integer> stack = new Stack<>();

    stack.push(10);
    stack.push(20);
    stack.push(30);

    System.out.println("Stack: " + stack);
    System.out.println("Top element: " + stack.peek());
    System.out.println("Popped element: " + stack.pop());
    System.out.println("Is stack empty? " + stack.isEmpty());
  }
}

Using java.util.Deque (ArrayDeque)

 import java.util.Deque;
import java.util.ArrayDeque;

public class DequeStackExample {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();

        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println("Stack: " + stack);
        System.out.println("Top element: " + stack.peek());
        System.out.println("Popped element: " + stack.pop());
        System.out.println("Is stack empty? " + stack.isEmpty());
    }
}

Note: When you use Deque implementation, methods like push(), pop() and peek() always operate on the *head* of the queue (which effectively simulates the top of the stack.)

Stack Operations

  • push(item): Adds an item to the top of the stack.
  • pop(): Removes and returns the item at the top of the stack. Throws EmptyStackException if the stack is empty when using `java.util.Stack`. Throws `NoSuchElementException` when using Deque when the stack is empty.
  • peek(): Returns the item at the top of the stack without removing it. Throws EmptyStackException if the stack is empty when using `java.util.Stack`. Throws `NoSuchElementException` when using Deque when the stack is empty.
  • isEmpty(): Returns true if the stack is empty, false otherwise.

Stack Applications in Competitive Programming

Stacks are extremely useful in solving a variety of problems in competitive programming. Some common applications include:

  • Backtracking: Stacks can be used to keep track of the state of a problem as you explore different possibilities.
  • Expression Evaluation: Stacks are crucial in converting infix expressions to postfix (Reverse Polish Notation) and then evaluating them.
  • Depth-First Search (DFS): Stacks can be used (though recursion is more common) to implement DFS in graphs.
  • Balancing Parentheses: Checking if parentheses in an expression are properly balanced.
  • Undo/Redo Functionality: Maintaining a history of actions.
  • Function Call Stack: In programming languages, the call stack is implemented using a stack data structure.
  • Nearest Greater Element: Find the nearest greater element to the left or right in an array.

Example Problems and Solutions

1. Balanced Parentheses

Given a string containing parentheses ((, ), {, }, [, ]), determine if the input string is valid. An input string is valid if:

  • Open brackets must be closed by the same type of brackets.
  • Open brackets must be closed in the correct order.

 import java.util.Deque;
import java.util.ArrayDeque;

public class BalancedParentheses {

    public static boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (c == ')' || c == '}' || c == ']') {
                if (stack.isEmpty()) {
                    return false; // Closing bracket without a matching opening bracket
                }

                char top = stack.pop();

                if ((c == ')' && top != '(') ||
                    (c == '}' && top != '{') ||
                    (c == ']' && top != '[')) {
                    return false; // Mismatched brackets
                }
            }
        }

        return stack.isEmpty(); // Check if any opening brackets are left unclosed
    }

    public static void main(String[] args) {
        String s1 = "()[]{}";
        String s2 = "(]";
        String s3 = "([)]";
        String s4 = "{[]}";
        String s5 = "){";

        System.out.println(s1 + ": " + isValid(s1)); // true
        System.out.println(s2 + ": " + isValid(s2)); // false
        System.out.println(s3 + ": " + isValid(s3)); // false
        System.out.println(s4 + ": " + isValid(s4)); // true
        System.out.println(s5 + ": " + isValid(s5)); // false
    }
}

2. Next Greater Element

Given an array, for each element, find the next greater element. The next greater element for an element x is the first greater element on the right side of x in the array. Elements for which no greater element exist, consider the next greater element as -1. 

 import java.util.Arrays;
import java.util.Deque;
import java.util.ArrayDeque;

public class NextGreaterElement {

    public static int[] nextGreaterElement(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        Arrays.fill(result, -1); // Initialize with -1 (default for no greater element)
        Deque<Integer> stack = new ArrayDeque<>(); // Store indices

        for (int i = 0; i < n; i++) {
            // While the stack is not empty and the current element is greater than the element at the top of the stack
            while (!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
                int index = stack.pop(); // Get the index of the smaller element
                result[index] = arr[i];   // Set the next greater element for that index
            }
            stack.push(i); // Push the current index onto the stack
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = {4, 5, 2, 25};
        int[] arr2 = {13, 7, 6, 12};

        System.out.println("Array: " + Arrays.toString(arr1) + ", Next Greater Elements: " + Arrays.toString(nextGreaterElement(arr1)));
        System.out.println("Array: " + Arrays.toString(arr2) + ", Next Greater Elements: " + Arrays.toString(nextGreaterElement(arr2)));
    }
}

3. Reverse a Stack using Recursion

Reverse the order of elements in a stack using recursion. 

 import java.util.Deque;
import java.util.ArrayDeque;

public class ReverseStackRecursion {

    public static void reverseStack(Deque<Integer> stack) {
        if (stack.isEmpty()) {
            return;
        }

        int temp = stack.pop();
        reverseStack(stack);
        insertAtBottom(stack, temp);
    }

    private static void insertAtBottom(Deque<Integer> stack, int item) {
        if (stack.isEmpty()) {
            stack.push(item);
            return;
        }

        int temp = stack.pop();
        insertAtBottom(stack, item);
        stack.push(temp);
    }

    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);

        System.out.println("Original Stack: " + stack);

        reverseStack(stack);

        System.out.println("Reversed Stack: " + stack);
    }
}
⬅ Previous Next ➡