Course contentsShow
← Java
Lesson 1215 of 2,87027. Queue and Deque ImplementationsFree lesson

Stack Operation Examples: Balanced Parentheses

Implement a classic stack algorithm to check for balanced parentheses using Deque as a stack.

Stack Operation Examples: Balanced Parentheses

What You'll Learn

You'll learn how to implement a classic algorithm that checks if parentheses in a string are properly balanced using Deque as a stack.

The Problem

Balanced parentheses means every opening bracket has a matching closing bracket in the correct order. For example:

  • "(())" is balanced ✓
  • "(()" is not balanced ✗ (missing closing bracket)
  • "())" is not balanced ✗ (extra closing bracket)
  • ")()" is not balanced ✗ (wrong order)

The Stack Solution

A stack is perfect for this problem because of its Last-In-First-Out nature:

  1. When you see an opening bracket ( → push it onto the stack
  2. When you see a closing bracket ) → pop from the stack and check if it matches
  3. At the end → the stack should be empty (all brackets were matched)

Think of it like checking nested boxes: each time you open a box (push), you must close that exact box (pop) before moving to the outer one.

Implementation Using ArrayDeque

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

public class BalancedParentheses {
    public static boolean isBalanced(String str) {
        Deque<Character> stack = new ArrayDeque<>();
        
        for (char ch : str.toCharArray()) {
            if (ch == '(') {
                stack.push(ch);
            } else if (ch == ')') {
                if (stack.isEmpty()) {
                    return false;  // No matching opening bracket
                }
                stack.pop();
            }
        }
        
        return stack.isEmpty();  // All brackets matched
    }
    
    public static void main(String[] args) {
        System.out.println(isBalanced("(())"));    // true
        System.out.println(isBalanced("(()"));     // false
        System.out.println(isBalanced("())"));     // false
    }
}

We use push for adding opening brackets, pop for removing them when we find a match, and isEmpty to verify all brackets paired up correctly.

Key Takeaway: Stacks naturally solve nested structure problems like balanced parentheses—push opening symbols, pop and match closing symbols, and verify the stack is empty at the end.