3
\$\begingroup\$

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";
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Could you explain the purpose for your code, maybe provide a use case? I fail to see the purpose of adding a max and min query to a stack, but I’m sure it’s useful to you. Please share! :) \$\endgroup\$ – Cris Luengo Dec 11 '18 at 1:49
  • 1
    \$\begingroup\$ It doesn't have any particular purpose, except educational :) This is just a common interview question to implement a stack that supports min() / max() in constant time. \$\endgroup\$ – user_185051 Dec 11 '18 at 4:18
4
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't see how keeping min/max in the node breaks encapsulation. The node is private to the stack and the consumer can't access it in any way. \$\endgroup\$ – Johnbot Dec 11 '18 at 14:19
  • 2
    \$\begingroup\$ The stack could be a piece of an algorithm where the time complexity is way more important than the space requirement. \$\endgroup\$ – Johnbot Dec 11 '18 at 14:22
  • 2
    \$\begingroup\$ If you have [7, 1, 7], min=1, max=7 and you pop the last element how would you propose we calculate the new min and max values from min=1, max=7 and popped=7? \$\endgroup\$ – Johnbot Dec 11 '18 at 14:59
  • 1
    \$\begingroup\$ @Johnbot You're right. When popping a value equal to min or max recalculating will be done at O(n). However this is all still the wrong approach. See my addition to the answer for more information. \$\endgroup\$ – brug Dec 11 '18 at 18:48
  • 1
    \$\begingroup\$ @user_185051 I don't have a great source no. Just look at Wikipedia or here on SO/SE for Encapsulation, Data Hiding, and Abstraction. I will also note that I don't agree fully with Johnbot's point but it isn't entirely invalid. The container would still maintain protection from outside manipulation. Think of each Node as a file and the container as a filing cabinet. It's okay if the filing cabinet knows about the files. After all it needs to sort the files by alphabet, or date, or size or whatever. But I don't want information from my file to end up in yours. \$\endgroup\$ – brug Dec 12 '18 at 4:50
4
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Good point! I missed that! \$\endgroup\$ – Cris Luengo Dec 12 '18 at 7:28
  • 1
    \$\begingroup\$ Having three vectors to store the value, min and max is a bad idea, it causes unnecessary memory fragmentation, it will cause more cache usage on your CPU to iterate through getting min and max, it's easy to create a bug where they de-sync, it's more code and slower because of more memory allocations and instructions to grow/shrink three vectors. Please don't do this. \$\endgroup\$ – Emily L. Dec 12 '18 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.