Stack Implementation and Valid Parentheses

1. The Stack: Last-In, First-Out (LIFO)

At its core, a stack is a simple yet powerful concept. It's a collection of items that follows the Last-In, First-Out (LIFO) principle. Think of a stack of plates: you add a new plate to the top, and when you need a plate, you take the one from the top. The last plate you put on is the first one you take off.

This behavior is defined by three main operations:

• push: Adds an element to the top of thestack.
• pop: Removes the element from the top of the stack.
• peek: Looks at the top element without removing it.

We also typically have an isEmpty operation to check if the stack contains any elements.

To build a solid understanding of the LIFO principle and these operations, let's watch a brief introductory video.

2. Implementing a Stack in Java

When it comes to using a stack in Java, you have a few choices. There is a legacy class called java.util.Stack, but it's generally not recommended for new code. It extends Vector, which means it carries unnecessary synchronization overhead and methods that don't belong to a pure stack.

The modern and preferred approach is to use the Deque (Double-Ended Queue) interface, with ArrayDeque being the most common implementation. A Deque can function as both a stack (LIFO) and a queue (FIFO). To use it as a stack, you consistently use methods for one end (e.g., addFirst/removeFirst or push/pop).

To understand this better and see how to create a clean, reusable stack implementation, let's look at an excellent article from HappyCoders.eu.

Here is the clean Stack interface and the ArrayDeque-backed implementation from the article. This is the structure you'd want to use in a larger project. For a quick interview problem, you can often just use ArrayDeque directly.

Stack Interface:

public interface Stack<E> {
    void push(E item);
    E pop();
    E peek();
    boolean isEmpty();
}

Implementation using ArrayDeque:

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

public class ArrayDequeStack<E> implements Stack<E> {
    // Using composition: the ArrayDequeStack HAS-A Deque
    private final Deque<E> deque = new ArrayDeque<>();

    @Override
    public void push(E item) {
        // Pushing to the stack is equivalent to adding to the front of the deque
        deque.addFirst(item);
    }

    @Override
    public E pop() {
        // Popping from the stack is equivalent to removing from the front of the deque
        // removeFirst() also throws an exception if the deque is empty, which is correct behavior for pop()
        return deque.removeFirst();
    }

    @Override
public E peek() {
        // Peeking the stack is equivalent to getting the element at the front of the deque
        // getFirst() throws an exception if empty, correct for peek()
        return deque.getFirst();
    }

    @Override
    public boolean isEmpty() {
        return deque.isEmpty();
    }
}

3. Application: The 'Valid Parentheses' Problem

Now, let's put our stack to use by solving a classic interview problem: Valid Parentheses.

The problem is simple: given a string containing just the characters (, ), {, }, [ and ], determine if the input string is valid.

An input string is valid if:

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

Think about the rule "Open brackets must be closed in the correct order." For the string {[()]}, the ( is the last one opened, so it must be the first one closed. This "last-in, first-out" requirement is a perfect signal to use a stack.

The algorithm is as follows:

• Iterate through the string character by character.
• If you see an opening bracket ((, {, [), push it onto the stack.
• If you see a closing bracket (), }, ]), check the top of the stack.
  • If the stack is empty or the bracket at the top is not the corresponding opening bracket, the string is invalid.
  • If it is the matching opening bracket, pop it from the stack.
• After iterating through the entire string, if the stack is empty, it means every opening bracket found its match. The string is valid. If the stack is not empty, it means there are unclosed brackets, and the string is invalid.

Let's watch a detailed walkthrough of this logic and its implementation in Java.

For a more textual and detailed breakdown, the AlgoMonster article is an excellent companion resource.

Here is a clean Java implementation for the isValid method, inspired by the resources. Notice how it directly uses ArrayDeque as a stack. In an interview, this is perfectly acceptable and efficient.

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

class Solution {
    public boolean isValid(String s) {
        // Use Deque as a Stack. `push` adds to the front.
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                // If it's an opening bracket, push it onto the stack.
                stack.push(c);
            } else {
                // It's a closing bracket. The stack cannot be empty.
                if (stack.isEmpty()) {
                    return false;
                }

                // Check if the closing bracket matches the last opening one.
                char top = stack.pop(); // Pop the top element
                if (c == ')' && top != '(') {
                    return false;
                }
                if (c == '}' && top != '{') {
                    return false;
                }
                if (c == ']' && top != '[') {
                    return false;
                }
            }
        }

        // If the stack is empty, all brackets were matched.
        // If not, there are unmatched opening brackets.
        return stack.isEmpty();
    }
}

The time complexity of this solution is O(n) because we traverse the string once. The space complexity is also O(n) in the worst case, where the input string consists of only opening brackets (e.g., "((((("), and we have to store all of them on the stack.

Conclusion

In this lesson, we explored the stack data structure, its LIFO principle, and its practical application. You've learned not only the theory but also the modern, idiomatic way to implement and use stacks in Java for solving a real interview problem.

Key Takeaways:

• A stack is a collection that operates on a Last-In, First-Out (LIFO) basis.
• The primary operations are push, pop, and peek.
• In modern Java, it's best to use the Deque interface with an ArrayDeque implementation to model a stack.
• The 'Valid Parentheses' problem is a classic application of stacks, perfect for matching nested pairs of items. The core logic involves pushing opening symbols and popping them when a matching closing symbol is found.

In our next lesson, we'll look at the stack's counterpart: the queue. We will implement a queue and use it to solve another common problem: performing a level-order traversal on a binary tree, opening the door to tree-based algorithms.