C++ implementation of Hackerrank's "Maximum Element in a Stack"

I just attempted the Maximum Element Challenge on Hackerrank. This question has been posted before in swift Swift Hackerrank Maximum Element in a Stack but it has attracted low views/no answers. Moving forward, based on the requirements of finding the maximum element, I used a vector as my underlying data structure as opposed to using Stack as I can't iterate through a stack. This exercise is meant to be a simple one but the time limit gets exceeded for larger input.

How do I improve the performance? Please feel free to criticise my approach as I'm new to C++ with 5 days of experience.


You have an empty sequence, and you will be given \$N\$ queries. Each
query is one of these three types:

• 1 x -Push the element x into the stack

• 2 -Delete the element present at the top of the stack

• 3 -Print the maximum element in the stack

Input Format


The first line of input contains an integer, \$N\$ . The next \$N\$
lines each contain an above mentioned query. (It is guaranteed that
each query is valid.)


Constraints

• \$1 \leq N \leq 10^5 \$

• \$1 \leq x \leq 10^9 \$

• \$1 \leq \text{type} \leq 3 \$

Output Format


For each type \$3\$ query, print the maximum element in the stack on a
new line.


Sample Input

10
1 97
2
1 20
2
1 26
1 20
2
3
1 91
3

Sample Output

26
91

```
#include
#include
#include

//using namespace std;
bool compareValues(int i, int j) { return i stackOfNumbers;

std::cin >> N;
for(int i =0; i > queryType;

switch(queryType) {
case 1 :
std::cin >> element;
stackOfNumbers.push_back(element);
break;
case 2 :
stackOfNumbers.erase(stackOfNumbers.end()-1);
break;
case 3 :
std::cout<< *std::max_element(std::begin(stackOfNumbers), std::end(stackOfNumbers),compareValues ) << std::endl;
break;
default :
std

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:

max_stack.h

#pragma once
#ifndef MAX_STACK_H
#define MAX_STACK_H

#include 

template
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 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

What comes to your coding style, you are not quite consistent:

for(int i =0; i < N ; i++){

Please, put a single space character before (, after ) and after =. Also, remove the space character after N; like this:

for (int i = 0; i < N; i++) {

You might want to fix the indentation as well.

main.cpp

#include "max_stack.h"
#include 

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

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

    std::cin >> N;

    for(int i = 0; i > 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;
}

Hope that helps.

StackExchange Code Review Q#146882, answer score: 5