Java: Recursively Finding the minimum element in a Stack-CodePudding

public static void removeMin(Stack<Integer> st)
{
    if (st.isEmpty())
        return;
    int min = st.pop();
    removeMin(st);
    if(min<st.top())
        return;
    st.push(min);
}

I tried to find the minimum element and remove it, but unfortunately I could not. I would like to get some help, here is my code.

I only have these methods in Class Stack: equals, isEmpty, pop, push, top, toString (the main methods).

Thanks in advance.

CodePudding user response：

I tested your method. You had two lines transposed. All you need to do is place the recursive call AFTER the test.

public static void removeMin(Stack<Integer> st) {
    if (st == null || st.isEmpty())
        return;
    int min = st.pop();
    if(st.isEmpty() || min<st.firstElement())
        return;
    removeMin(st); // this was in the wrong place, causing the stack to empty out completely
    st.push(min);
}

I ran this example:

public static void main (String[] args) {
    Stack<Integer> stack = new Stack<>();
    stack.add(2);
    stack.add(1); // to be removed
    stack.add(5);
    stack.add(3);
    stack.add(4);
    removeMin(stack);
    System.out.println(stack.toString());
}

and it printed out [2, 5, 3, 4].

This solution works with the minimum value being at the top, bottom, or anywhere in the middle of the stack.

CodePudding user response：

You have to compare the top of the stack to the minimum element of the rest of the stack.

That's not what you are doing. You are only comparing the top of the stack to the next element of the stack.

You should probably change your recursive method to return the minimum element. This way you can compare to it:

public static int removeMin(Stack<Integer> st)
{
    if (st.isEmpty())
        return Integer.MAX_VALUE; // if the stack is empty, return a value that is larger 
                                  // than any other value
    int top = st.pop();
    int min = removeMin(st);
    if(top < min) {
        // top is the minimum element
        st.push(min);
        return top;
    } else {
        // min is the minimum element
        st.push(top);
        return min;
    }
}

I haven't tested it.