check for minimum in a stack C++

Question

I have a program that has three functions, one that pushes to stack, second that pops from stack, and third that checks the minimum in that stack.

It is easy to check the minimum when we are pushing, as we can check at every new push if the minimum changes or not. However, what if the user popped the minimum value, how can I go back to the min value of the one before it? I thought of using nodes. I know I could use a vector instead of a stack, however I want to use the stack function and be able to still find the minimum even if the user popped the last minimum.

Can we keep track of the minimum numbers with a node or is a vector the only way?

Here is my code:

#include <iostream>
#include <stack>
using namespace std;


void myPush(int num, stack<int>& myStack, int &min);
void myPop(stack<int>& myStack, int &min);
int main()
{
    int x=0;
    int choice;
    int n;
    int dmin= 2147483646;
    stack<int> myStack;
    while( x==0) {
    cout << "stack menu: " << endl;                  //this is just a menu

    cout << "1- for push " << endl;
    cout << "2- for pop " << endl;
    cout << "3- for min " << endl;
    cout << "4-exit " << endl;
    cin >> choice;

    if(choice == 1)
    {
        cout << " I want to push: " << endl;
        cin >> n;
        myPush(n, myStack, dmin);
    }
    else if(choice == 2)
    {
        cout << "popped: " << endl;            
        myPop(myStack, dmin);
    }
    else if(choice == 3)
    {
        cout << "minimum is: " << endl;
        cout << dmin;
    }
    else
        x=1;             //this will exit the menu 
    }

}

void myPush(int num, stack<int>& myStack, int &min)
{

    if(num <= min)                 //check if it's the new minimum
        min = num;

    myStack.push(num);           //pushes new num

}

void myPop(stack<int>& myStack, int &min)
{

    cout << "popping: " << myStack.top() << endl;        //tells the user what we are popping

    if( min == myStack.top())                      //let the user know that minimum changed(DISASTER!!!)
        cout<< "min changed " << endl;

    myStack.pop();                         //pop that value(Hopefully not the min !)
}

Drop the nerfed `std::stack` data structure and use good old `std::vector`. You can then use `std::min_element` to find the minimum. — Neil Kirk, Mar 09 '15 at 18:03
What about using node to keep track what the minimum beneath itself is ? — Mozein, Mar 09 '15 at 18:04
Use a second min var with the *old* mins When the *actual* min goes away, update it with the old ones — hlscalon, Mar 09 '15 at 18:04
@1nflktd that is not a good solution at all. What if he pops both minimums after each other... — Mozein, Mar 09 '15 at 18:05
@Mozein Use a array-vector- or everything, and you will take care of that — hlscalon, Mar 09 '15 at 18:06
Just store pairs on the stack, containing the value and the minimum so far. That way you can easily determine the minimum by reading it off the top stack value, and popping the top pair will automatically give you the correct minimum again. Only when pushing a new value, yu'll have to calculate the new minimum to go along with it, which is easy though. — celtschk, Mar 09 '15 at 21:14
you can refer this too. http://stackoverflow.com/questions/685060/design-a-stack-such-that-getminimum-should-be-o1 — mhs, Mar 10 '15 at 01:10

score 1 · Accepted Answer · answered Mar 09 '15 at 22:15

1

Make another stack (minstack) and push the minimum to it each time you have a new minimum. When the minimum gets popped, also pop the minstack, then the top of the minstack will hold the current minimum.

answered Mar 09 '15 at 22:15

M Y

1,831
4
24
52

This is false. Consider pusing 4 3 1 2. When popping out the 4 3 1, your strategy will give 3 as minimum (while the only thing left is a 2). – Vincent Fourmond Mar 09 '15 at 22:26
1

If you push 4 3 1 2 then you have to pop 2 1 3 4 – M Y Mar 09 '15 at 22:28
1

Duplicate values would pose a problem, 1 1 1 1 for instance. This can be routed around by checking if new values are equal to the current minimum. If equal push an additional 1 (etc) to the minstack. – M Y Mar 09 '15 at 22:48
@Mozein what problem are you running into? Can you give me an example stack like Vincent did? Although celtschk's idea would be easier, – M Y Mar 10 '15 at 03:15
@hellyale it is similar to creating a vector you are right, thanks for the help – Mozein Mar 10 '15 at 04:45

score 0 · Answer 2 · answered Mar 10 '15 at 01:46

Okay I used vectors like everyone suggested and it works now ! Thank you all . New code:

#include <iostream>
#include <stack>
#include <vector>
using namespace std;


void myPush(int num, stack<int>& myStack, vector<int>& Min);
void myPop(stack<int>& myStack, vector<int>& Min);
int main()
{
    int x=0;
    int choice;
    int n;
    vector<int> min;
    min.push_back(2147483646);
    stack<int> myStack;
    while( x==0) {
    cout << "stack menu: " << endl;                  //this is just a menu

    cout << "1- for push " << endl;
    cout << "2- for pop " << endl;
    cout << "3- for min " << endl;
    cout << "4-exit " << endl;
    cin >> choice;

    if(choice == 1)
    {
        cout << " I want to push: " << endl;
        cin >> n;
        myPush(n, myStack, min);
    }
    else if(choice == 2)
    {
        cout << "popped: " << endl;            
        myPop(myStack, min);
    }
    else if(choice == 3)
    {
        cout << "minimum is: " << endl;
        cout << min.back() << endl;
    }
    else
        x=1;            
    }

}

void myPush(int num, stack<int>& myStack, vector<int>& Min)
{

    if(num <= Min.back())                 
        Min.push_back(num);

    myStack.push(num);           

}

void myPop(stack<int>& myStack, vector<int>& Min)
{

    cout << "popping: " << myStack.top() << endl;        //tells the user what we are popping

    if( Min.back() == myStack.top())
        {

        cout<< "min changed " << endl;
        Min.pop_back();
    }


    myStack.pop();                         
}

check for minimum in a stack C++

2 Answers2