Stack with a minimum

A practice interview question:


How would you design a stack which, in addition to push and pop, also has a function getMin which returns the minimum element? Push, pop and min should all operate in O(1) time.

class stackWithMin
{
private:
    std::vector stack;
    std::vector minLoc;
    int min, current, minCurrent;

public:
    stackWithMin()
    {
        min = NULL;
        current = 0;
        minCurrent = 0;
    }

    void print()
    {
        std::cout1)
            {
                int loc = minLoc.at(--minCurrent-1);
                minLoc.pop_back();
                min = stack.at(loc);
            }
            // No more elements
            else
            {
                min = NULL;
            }
        }

        current--;
        stack.pop_back();
        print();
        return;
    }

    int getMin(){return min;}

};

Here are some things that may help you improve your code:

Simplify the algorithm

Although it would take more space to store, a simpler algorithm would be to simply use minLoc as the current minimum. If you did so, then getMin() would simply be return minLoc.back();

Eliminate redundant variables

Even if you don't care for that particular algorithm, you can remove the variables min, current and minCurrent and also simplify the code:

void push(int num)
{
    stack.push_back(num);
    if (minLoc.size() == 0 || num < stack[minLoc.back()]) 
        minLoc.push_back(stack.size()-1);
    print();
}

void pop()
{
    // Check if the number to be popped is the current lowest
    if(minLoc.size() && minLoc.back() == stack.size()-1)
        minLoc.pop_back();
    stack.pop_back();
    print();
}

int getMin() const {
    return minLoc.size() ? stack[minLoc.back()] : 0;
}

Use const where possible

The getMin function doesn't (and shouldn't) modify the underlying stack, so it should be declared const. The same is true for the print function.

Avoid using index variables

Rather than using an index variable i in the print routine and then calling at() for each iteration, use iterators instead. For example, you could use this:

std::copy(stack.cbegin(), stack.cend(), 
          std::ostream_iterator(std::cout, ", "));

Omit empty strings

The current code for print includes this line:

std::cout<<""<<stack.at(i)<<", ";

There's no need for the empty string in that line.

Use whitespace to improve readability

To take the previously quoted line as an example, rewriting it with more whitespace makes it easier to read:

std::cout << stack.at(i) << ", ";

Don't use std::endl when '\n' will do

Using std::endl emits a \n and flushes the stream. Unless you really need the stream flushed, you can improve the performance of the code by simply emitting '\n' instead of using the potentially more computationally costly std::endl.

Take care with signed versus unsigned

The code includes this line in the print function:

for (int i=0;i<stack.size();i++)

However, stack.size() is unsigned and i is signed. For consistency, it would be better to declare i as std::size_t which is the type returned by size().

Consider the user of the code

The std::vector::pop_back() returns void but provides a member function back() to allow a user of the code to access the last member before removing it from the vector. You might consider either returning the popped value in your implementation of pop or implementing a back function such as the one std::vector supplies.

StackExchange Code Review Q#70724, answer score: 4