18. DSA with C++ - Stack-related Questions

Common Stack-related Questions

1. Valid Parentheses: Given a string containing only parentheses ('(', ')', '{', '}', '[', ']'), determine if the string is valid. The validity is determined by matching opening and closing parentheses correctly.
   Example: Input: "({[]})", Output: true
2. Evaluate Reverse Polish Notation: Given a list of arithmetic expressions in Reverse Polish Notation (postfix notation), evaluate the expressions and return the result.
   Example: Input: ["2", "1", "+", "3", "*"], Output: 9 (Explanation: (2 + 1) * 3 = 9)
3. Next Greater Element: Given an array of integers, for each element, find the next element in the array that is greater than the current element. If there is no such element, return -1.
   Example: Input: [4, 5, 2, 25], Output: [5, 25, 25, -1]
4. Stock Span Problem: Given an array of stock prices, find the span of each stock price, which is the number of consecutive days before the current day (including the current day) for which the price was less than or equal to the current price.
   Example: Input: [100, 80, 60, 70, 60, 75, 85], Output: [1, 1, 1, 2, 1, 4, 6]
5. Largest Rectangle in Histogram: Given an array representing the heights of bars in a histogram, find the area of the largest rectangle that can be formed within the histogram.
   Example: Input: [2, 1, 5, 6, 2, 3], Output: 10 (Explanation: The largest rectangle can be formed by bars with heights 5 and 6.)
6. Implement a Min Stack: Design a stack that supports the usual push, pop, and top operations, along with an additional operation called getMin() that returns the minimum element in constant time.
   Example: MinStack stack; stack.push(3); stack.push(2); stack.getMin(); // Output: 2