What data structure is typically used to validate parentheses in a string?

• A. Queue
• B. HashMap
• C. Stack
• D. ArrayList

Answer: (C)

The use of a stack as a data structure for validating parentheses in a string is fundamentally rooted in the Last In, First Out (LIFO) nature of stacks. When validating parentheses, you need to ensure that for every opening parenthesis there is a corresponding closing parenthesis, and that they are properly nested.

Here’s how it works:

1. As you traverse the string, each time you encounter an opening parenthesis (such as '(', '{', or '['), you push it onto the stack. This action signifies that you are waiting for a matching closing parenthesis.

2. When you encounter a closing parenthesis (such as ')', '}', or ']'), you check if the stack is empty. If it is not empty, you pop the top element from the stack and check if it matches the type of the closing parenthesis. If there is a match, you continue; if not, the string is invalid.

3. At the end of the traversal, if the stack is empty, it means that all opening parentheses had matching closing ones, and thus the parentheses are valid. If the stack is not empty, it indicates that there are unmatched opening parentheses.

This orderly processing of opening and closing parentheses without losing track of their order is