Return to Answer

#include "max_stack.h"
#include <iostream>

using std::cout;
using std::endl;

int main() {
    int N;
    int queryType;
    int element;
    MaxStack<int> stack;

    std::cin >> N;

    for(int i = 0; i < N ; i++) {
        std::cin >> queryType;

        switch(queryType) {
            case 1 :
                std::cin >> element;
                stack.push(element);
                break;

            case 2 :
                stack.pop();
                break;

            case 3 :
                cout << stack.max() << endl;
                break;
            default :
                std::cout << "Invalid queryType" << std::endl;
        }
    }

    return 0;
}

#include "max_stack.h"
#include <iostream>

using std::cout;
using std::endl;

int main() {
    int N;
    int queryType;
    int element;
    MaxStack<int> stack;

    std::cin >> N;

    for(int i = 0; i < N ; i++) {
        std::cin >> queryType;

        switch(queryType) {
            case 1 :
                std::cin >> element;
                stack.push(element);
                break;

            case 2 :
                stack.pop();
                break;

            case 3 :
                cout << stack.max() << endl;
                break;
        }
    }

    return 0;
}

#pragma once
#ifndef MAX_STACK_H
#define MAX_STACK_H

#include <stdexcept>

template<typename T>
class MaxStack {
public:

    MaxStack()
    :
    top_node{nullptr},
    maximum{nullptr}
    {}

    void push(T datum)
    {
        MaxStackNode* new_node = new MaxStackNode(datum, top_node);

        if (top_node == nullptr)
        {
            maximum = new_node;
        }
        else if (maximum->datum < datum)
        {
            new_node->previousMaximum = maximum;
            maximum = new_node;
        }

        top_node = new_node;
    }

    void pop()
    {
        check_not_empty();
        MaxStackNode* ret = top_node;

        if (maximum == ret)
        {
            maximum = ret->previousMaximum;
        }

        top_node = top_node->previous;
    }

    T top()
    {
        check_not_empty();
        return top_node->datum;
    }

    T max()
    {
        check_not_empty();
        return maximum->datum;
    }

private:

    struct MaxStackNode {
        T datum;
        MaxStackNode* previous;
        MaxStackNode* previousMaximum;

        MaxStackNode(T datum, MaxStackNode* previous)
        :
        datum{datum},
        previous{previous},
        previousMaximum{nullptr}
        {}
    };

    MaxStackNode* top_node;
    MaxStackNode* maximum;

    void check_not_empty()
    {
        if (top_node == nullptr)
        {
            throw std::runtime_error{"The stack is empty."};
        }
    }
};

#endif // MAX_STACK_H

#pragma once
#ifndef MAX_STACK_H
#define MAX_STACK_H

#include <stdexcept>

template<typename T>
class MaxStack {
public:

    MaxStack()
    :
    top_node{nullptr},
    maximum{nullptr}
    {}

    void push(T datum)
    {
        MaxStackNode* new_node = new MaxStackNode(datum, top_node);

        if (top_node == nullptr)
        {
            maximum = new_node;
        }
        else if (maximum->datum < datum)
        {
            new_node->previousMaximum = maximum;
            maximum = new_node;
        }

        top_node = new_node;
    }

    void pop()
    {
        check_not_empty();
        MaxStackNode* ret = top_node;

        if (maximum == ret)
        {
            maximum = ret->previousMaximum;
        }

        top_node = top_node->previous;
        delete ret;
    }

    T top()
    {
        check_not_empty();
        return top_node->datum;
    }

    T max()
    {
        check_not_empty();
        return maximum->datum;
    }

private:

    struct MaxStackNode {
        T datum;
        MaxStackNode* previous;
        MaxStackNode* previousMaximum;

        MaxStackNode(T datum, MaxStackNode* previous)
        :
        datum{datum},
        previous{previous},
        previousMaximum{nullptr}
        {}
    };

    MaxStackNode* top_node;
    MaxStackNode* maximum;

    void check_not_empty()
    {
        if (top_node == nullptr)
        {
            throw std::runtime_error{"The stack is empty."};
        }
    }
};

#endif // MAX_STACK_H

It is possible to query for the maximum element, pushing and popping in constant time. And that is how:

It is possible to query for the maximum element, pushing and popping in constant time. The idea is that you maintain a partial linked list whithin the stack: