Stack implementation in C++ including min(), max() functions in O(1)

Question

This implementation seems to work. I would love to get any suggestions / comments on how this code could be improved. Are there any potential memory management issues? Any additional methods that would be useful (also, from educational point of view) to implement? Thank you!

Stack.hpp

#ifndef STACK_H
#define STACK_H

#include <iostream>
#include <memory>
#include <vector>
#include <stdexcept>

class Stack {

private:
    struct Node {
        int val;
        // To get min and max value of stack in O(1):
        int maxVal = std::numeric_limits<int>::min();
        int minVal = std::numeric_limits<int>::max();
    };

    std::vector<Node> currStack;

public:

    int size() const { return currStack.size(); }
    bool empty() const { return currStack.empty(); }
    void pop() { currStack.pop_back(); }

    void push(int val);
    int top() const; // O(1)
    int min() const; // O(1)
    int max() const; // O(1)

};

#endif /* STACK_H */

Stack.cpp

#include "Stack.hpp"

void Stack::push(int val) {

    Node tempNode;
    tempNode.val = val;
    if (this->empty()) {
        tempNode.minVal = val;
        tempNode.maxVal = val;
    } else {
        tempNode.minVal = std::min(currStack.back().minVal, val);
        tempNode.maxVal = std::max(currStack.back().maxVal, val);
    }

    currStack.push_back(tempNode);
}

int Stack::top() const {
    if (currStack.empty()) {
        throw std::out_of_range ("Stack is empty");
    }
    return currStack.back().val;
}

int Stack::min() const {
    if (currStack.empty()) {
        throw std::out_of_range ("Stack is empty");
    }
    return currStack.back().minVal;
}

int Stack::max() const {
    if (currStack.empty()) {
        throw std::out_of_range ("Stack is empty");
    }
    return currStack.back().maxVal;
}

main.cpp

#include "Stack.hpp"

int main() {

    // Stack init
    Stack myStack;

    std::cout << "Empty? " << myStack.empty() << "\n";
    std::cout << "Size: " << myStack.size() << "\n";

    try {
        std::cout << "Top: " << myStack.top() << "\n";
        std::cout << "Min: " << myStack.min() << "\n";
        std::cout << "Max: " << myStack.max() << "\n";
    }
    catch (const std::out_of_range& e) {
        std::cout << "Out of range error. " << e.what() << "\n";
    }

    std::cout << "Push some integers: \n";
    myStack.push(5);
    myStack.push(3);
    myStack.push(7);

    std::cout << "Empty? " << myStack.empty() << "\n";
    std::cout << "Size: " << myStack.size() << "\n";

    try {
        std::cout << "Top: " << myStack.top() << "\n";
        std::cout << "Min: " << myStack.min() << "\n";
        std::cout << "Max: " << myStack.max() << "\n";
    }
    catch (const std::out_of_range& e) {
        std::cout << "Out of range error. " << e.what() << "\n";
    }

    std::cout << "Pop some integers: \n";
    myStack.pop();

    std::cout << "Empty? " << myStack.empty() << "\n";
    std::cout << "Size: " << myStack.size() << "\n";

    try {
        std::cout << "Top: " << myStack.top() << "\n";
        std::cout << "Min: " << myStack.min() << "\n";
        std::cout << "Max: " << myStack.max() << "\n";
    }
    catch (const std::out_of_range& e) {
        std::cout << "Out of range error. " << e.what() << "\n";
    }
}

Answer 1

I'm going to answer your direct questions first.

Are there any potential memory management issues?

No. You don't do any manual memory management (using new and delete) so there are no issues.

Any additional methods that would be useful (also, from educational point of view) to implement?

Here is the reference page for std::stack. This is the standard library documentation. You may not be able to do them all right now but those are all possible functions and members you could implement for a stack. (I recommend only trying a little bit at a time.

I'd like to point out that your code is very clean and easy to read. I also appreciate good use of const correctness.

---

Use unique include guards

#ifndef STACK_H
#define STACK_H

This is a very basic name. It would be easy for others to use a very similar name. Make your includes unique. Add a namespace name, a project name, a library name and possibly a GUID or all of the above to eliminate the risk of clashes.

---

Use the right headers

#include <iostream>
#include <memory>
#include <vector>
#include <stdexcept>

You don't use <memory> or <iostream> in your class. You don't use <stdexcept> until the cpp file. declare the header there.

You are missing <limits> for :std::numeric_limits<>

---

List public members first

Anyone using your stack is only going to be able to use the public member functions. It is common practice therefor to list these first.

---

Avoid the use of this->

It is almost always wrong to have this-> in your code in C++. For example this:

if (this->empty())

can simply be written:

if (empty()) 

The exception to this rule is with variable shadowing (which you don't have) which is also typically solved with a name change.

---

Always ask: What does this feature serve?

So you implemented a min() and max(). You did it with an O(1) lookup by having every single element keep track of the current min and max value of the entire stack. This is a problem on two levels:

• Your nodes should not contain information on other nodes. That breaks encapsulation. This is the job of the Container.
• And its also useless information. There is one accessible node. What value do you gain by knowing what the min and max values beneath that one are? how can you even act on that even if you knew?

If you have your heart content on keeping the min() max() then at least store the value in the container. In addition to being good practice it will also take significantly less memory.

---

Lastly When you are ready you should look into Template Metaprogramming. A Container / Data Structure like this needs to be usable with any type, including user defined types, in order to be truly useful/robust.

---

Edit: to answer point brought up in comments

The problem as I see it is the fact that you need to store state, which a stack is great for. If I needed to maintain current, min, and max values like you are, I would put them all into a struct like so:

struct State
{
     int current_value;
     int min_value;
     int max_value;
}

Then I would use a stack that supports user-defined types. std::stack<State> state_machine.

Furthermore by maintaining min() and max(), in the node or in the container, if you do decide to extend your container to support user-defined types you will force your users to overload the comparison operators for their type even if there is no logical way to do so and it isn't otherwise needed.

Answer 2

I'll add to what @bruglesco says.

Storing the running min and max

If I understand correctly your goal is to have a stack where you can pop() and still access min() and max() in constant time.

Then it's indeed not sufficient to have a single max_ and min_ member in your class and your approach of storing the current min and max values in the stack is fine.

Alternatively you could store the values in a simple std::vector<int> and have two additional std::vector<int> instances currMax and currMin. Then push(val) would append val to currMax iff val is greater or equal to currMax.back(), and pop() would pop the last item from currMax if the popped item is equal to currMax.back(). (Similarly for currMin)

Member initialization

Remove the default member initialization from Stack::Node::maxVal and Stack::Node::minVal.
push() always sets these values.

Exception style

top(), min() and max() throw an exception if the stack is empty. pop() just calls currStack.pop() which is UB if the stack is empty. Both approaches are valid, you should just be consistent.

DRY

You have the same if (currStack.empty()) { throw std::out_of_range ("Stack is empty"); } in three functions. Make it a private function of its own, say void throwIfEmpty() const and call that.

empty() / clear()

From a practical view you could add a clear() method that clears the stack.
Some people complain about empty() because it's unclear it it's used as an attribute ("Is this instance empty?") or a command ("Empty this instance!"). In C++17 you could add a [[nodiscard]] attribute to issue warnings if empty() is used as a command.