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<int> stack;
std::vector<int> minLoc;
int min, current, minCurrent;
public:
stackWithMin()
{
min = NULL;
current = 0;
minCurrent = 0;
}
void print()
{
std::cout<<"Min: "<<min<<" --- ";
for (int i=0;i<stack.size();i++)
{
std::cout<<""<<stack.at(i)<<", ";
}
std::cout<<""<<std::endl;
}
void push(int num)
{
stack.push_back(num);
if(num<=min || current == 0)
{
minLoc.push_back(current);
minCurrent++;
min = num;
}
current++;
print();
}
void pop()
{
if(current==0)
{
std::cout<<"Stack is empty"<<std::endl;
return;
}
// Check if the number to be popped is the current lowests
if(minLoc.at(minCurrent-1)==current-1)
{
if(minCurrent>1)
{
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;}
};
print()
should print something. \$\endgroup\$