Min Stack Implementation – C++

This C++ program implements a stack that supports standard stack operations (push and pop), along with retrieving the minimum element in constant time. This is achieved by using an auxiliary stack that keeps track of the minimum values.

Program Code

#include <iostream>
#include <stack>
#include <cassert>

class MinStack {
private:
    std::stack<int> s;        // Main stack to hold elements
    std::stack<int> minStack; // Stack to hold minimums

public:
    void push(int x) {
        s.push(x);
        if (minStack.empty() || x <= minStack.top()) {
            minStack.push(x);
        }
    }

    void pop() {
        assert(!s.empty() && "Stack is empty");
        if (s.top() == minStack.top()) {
            minStack.pop();
        }
        s.pop();
    }

    int top() {
        assert(!s.empty() && "Stack is empty");
        return s.top();
    }

    int getMin() {
        assert(!minStack.empty() && "Min stack is empty");
        return minStack.top();
    }
};

int main() {
    MinStack minStack;
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    std::cout << "Current Minimum: " << minStack.getMin() << std::endl; // returns -3
    minStack.pop();
    std::cout << "Top element: " << minStack.top() << std::endl;         // returns 0
    std::cout << "Current Minimum: " << minStack.getMin() << std::endl; // returns -2
    return 0;
}

Class and Function Documentation

• void push(int x): Adds the element x to the stack. If x is smaller than or equal to the current minimum, it is also pushed onto the min stack.
• void pop(): Removes the element on top of the main stack. If the popped element is the current minimum, it is also removed from the min stack.
• int top(): Returns the top element of the main stack.
• int getMin(): Retrieves the minimum element from the stack without removing it, using the min stack.

Example Usage

    MinStack minStack;
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    std::cout << "Current Minimum: " << minStack.getMin() << std::endl; // Outputs -3
    minStack.pop();
    std::cout << "Top element: " << minStack.top() << std::endl;       // Outputs 0
    std::cout << "Current Minimum: " << minStack.getMin() << std::endl; // Outputs -2