Validate a string of brackets like "([]{})". Data structure?

Options

1. Queue
2. Stack (Correct option)
3. Heap
4. Trie

Answer

Stack

Why

A stack is last-in, first-out, like a pile of plates.

Walk through the string: push every opening bracket. On a closing bracket, the top of the stack must be its matching opener; pop it. If it doesn't match, or the stack is empty, the string is invalid.

At the end the stack must be empty. O(n).

Remember

Matching pairs / nesting → stack.

Key terms

• Stack
• Queue
• Array
• Time complexity
• Space complexity
• Data structure