Stack and Queue Problems

# CHAPTER 7

Stack and Queue Problems #

1. Chapter Introduction #

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

• Push(): Add an item to the top. O(1) Time.

• Pop(): Remove the top item. O(1) Time.

• Peek(): Look at the top item without removing it. O(1) Time.

3. Pattern 1: Valid Parentheses #

*The Logic:*

1. 1. Iterate through the string.

1. 2. If it's an Open Bracket, Push it onto the stack.

1. 3. If it's a Closed Bracket, look at the Peek of the stack. Does it match?

• If yes, Pop the top element and continue.

• If no, or if the stack is empty, return False.

1. 4. At the end, if the stack is empty, return True.

4. Pattern 2: The Monotonic Stack (Advanced) #

*The Decreasing Stack Logic:* We push elements onto the stack. If we encounter a new temperature that is *warmer* than the temperature at the top of the stack, we have found the "Next Greater Element" for that top item! We Pop the top item, calculate the distance, and repeat until the stack is monotonic (decreasing) again.

def dailyTemperatures(temps):
    res = [0] * len(temps)
    stack = [] # Stores indices, not the actual temperatures
    
    for i, t in enumerate(temps):
        # While stack is not empty and current temp is > top of stack temp
        while stack and t > temps[stack[-1]]:
            stack_idx = stack.pop()
            res[stack_idx] = i - stack_idx # Calculate days waited
        stack.append(i)
        
    return res
# Time: O(N), Space: O(N)

5. The Queue (FIFO: First-In, First-Out) #

• Enqueue/Push: Add to the back of the line. O(1) Time.

• Dequeue/Pop: Remove from the front of the line. O(1) Time.

*Implementation Warning:* In Python, if you use a standard List arr.pop(0) to remove the first element, it is O(N) Time, because every other element must shift forward. You MUST use collections.deque to achieve O(1) Queue operations.

6. When to use a Queue #

7. Real-World Scenario: The Browser History #

• historyStack: When you visit a new page, push the current page here.

• forwardStack: When you hit the "Back" button, pop from historyStack and push it to forwardStack.

• When you hit the "Forward" button, pop from forwardStack and push it to historyStack.

8. Mini Project: Evaluate Reverse Polish Notation #

9. Common Mistakes #

• Popping an Empty Stack: Always check if len(stack) > 0 or if not stack.isEmpty() before calling pop() or peek(), otherwise your code will crash with an Exception.

• Using arrays for Queues: As stated, list.pop(0) in Python or ArrayList.remove(0) in Java is O(N) Time. This will fail performance tests. Use Deque or LinkedList.

10. Best Practices #

• Stacking Indices: When building a Monotonic Stack to calculate distances or spans, push the *Index* of the element onto the stack, not the value itself. You can always use the index to look up the value in the array, but you cannot use the value to look up the index.

11. Exercises #

1. 1. Trace the Valid Parentheses logic on the string "{[()]}".

1. 2. Trace the Valid Parentheses logic on the string "{[(])}". At what exact point does the algorithm fail?

12. MCQs #

14. Interview Questions #

• Q: "Design a Stack that supports push, pop, top, and retrieving the minimum element in constant O(1) time." (LeetCode 155 - Min Stack. Hint: You need to store tuples or use two parallel stacks).

15. FAQs #

• Q: Should I build my own Stack class from scratch in an interview?

16. Summary #

17. Next Chapter Recommendation #