Min Stack

class MinStack {
private:
    std::stack<int> dataStack;
    std::stack<std::pair<int, int>> auxStack;
    
public:
    MinStack() {}
    
    void push(int value) {
        dataStack.push(value);
    
        if (auxStack.empty() || value < auxStack.top().first) {
            auxStack.push({value, 1});
        } else if (value == auxStack.top().first) {
            auxStack.top().second++;
        }
    }
    
    void pop() {
        if (dataStack.top() == auxStack.top().first) {
            auxStack.top().second--;
        }
    
        if (auxStack.top().second == 0) {
            auxStack.pop();
        }
    
        dataStack.pop();
    }
    
    int top() { return dataStack.top(); }
    
    int min() { return auxStack.top().first; }
};

The problem "Min Stack" involves creating a stack data structure that supports pushing, popping, and retrieving the smallest element in constant time. The provided C++ solution utilizes two stacks: one for storing all the elements and another auxiliary stack to keep track of the minimum elements.

Here's how the stacks function in the implemented Code:

• Data Stack: This stack holds all the elements of the stack.
• Auxiliary Stack: This is used to store the minimum elements. Each element is a pair where
  • the first part is the minimum value and
  • the second part is the count of how many times this minimum value occurs in the dataStack.

Functions and their operations:

1. Constructor (MinStack() {}): Initializes the stacks.

2. push(int value):

   • The value is pushed onto the dataStack.
   • If the auxStack is empty or the incoming value is less than the current minimum, a new pair is pushed onto the auxStack with the value and a count of one.
   • If the incoming value equals the current minimum, increment the count for that value in the top pair of auxStack.

3. pop():

   • Checks if the top value of dataStack equals the current minimum (top of auxStack).
   • If so, decrements the count of the top pair in the auxStack.
   • If the count of this minimum value in the auxStack becomes zero, it removes the top of auxStack.
   • The value is popped from the dataStack.

4. top():

   • Returns the top element of the dataStack without removing it.

5. min():

   • Returns the minimum element currently in the stack, by accessing the first value of the pair on top of the auxStack.

With this solution, each stack operation (push, pop, top, min) operates in constant time, O(1), which is efficient for scenarios involving frequent stack operations combined with frequent minimum value retrievals.