Max Stack - CPP Solution

1. Introduction

This blog post focuses on designing a Max Stack data structure, which is an advanced version of a regular stack that allows retrieving the maximum element in the stack in constant time.

Problem

Design a Max Stack data structure that supports pushing, popping, top (retrieving the top element), and retrieving the maximum element in the stack. All operations should be done in O(1) time complexity.

2. Solution Steps

1. Use two stacks: one to store the actual stack elements (mainStack) and another to store the maximum elements (maxStack).

2. When pushing an element, add it to mainStack and update maxStack if the element is greater than the current maximum.

3. When popping, remove the element from both stacks if it's equal to the current maximum.

4. The top operation returns the top of mainStack.

5. The getMax operation returns the top of maxStack.

3. Code Program

#include <iostream>
#include <stack>
using namespace std;

class MaxStack {
    stack<int> mainStack, maxStack;

public:
    // Push element onto stack
    void push(int x) {
        mainStack.push(x);
        if (maxStack.empty() || x >= maxStack.top()) {
            maxStack.push(x);
        }
    }

    // Remove the element on top of the stack
    void pop() {
        if (mainStack.top() == maxStack.top()) {
            maxStack.pop();
        }
        mainStack.pop();
    }

    // Get the top element
    int top() {
        return mainStack.top();
    }

    // Retrieve the maximum element
    int getMax() {
        return maxStack.top();
    }
};

// Function to demonstrate the usage of MaxStack
void testMaxStack() {
    MaxStack stack;
    stack.push(4);
    stack.push(2);
    stack.push(8);
    cout << "Current Max: " << stack.getMax() << endl;
    stack.pop();
    cout << "Current Max after popping: " << stack.getMax() << endl;
}

int main() {
    testMaxStack();
    return 0;
}

Output:

Current Max: 8
Current Max after popping: 4

Explanation:

The MaxStack class uses two stacks for efficient operations. 

The push operation adds elements to both mainStack and maxStack (the latter only if the element is greater than or equal to the current maximum). 

The pop operation removes elements from both stacks only if the popped element is the current maximum. 

The top operation gives the top element of mainStack, and getMax provides the current maximum from maxStack. 

This design ensures that all stack operations, including retrieving the maximum element, are performed in O(1) time complexity.