Home > Back-end >  Finding the smallest number in a stack and placing it at the top of the stack without changing the o
Finding the smallest number in a stack and placing it at the top of the stack without changing the o

Time:07-04

I'm trying to find the smallest number in an Integer stack and place it at the top of the stack without changing the order of the rest of the numbers, so a stack such as [1 2 3 4 5] with the leftmost number being the top of the stack and the rightmost number being the bottom of stack should become [2 3 4 5 1] after using the findSmallest method shown in the code below, but for some reason I encounter an EmptyStackException after trying to print the contents of the stack after the method calling.

Here is my code:

import java.util.Scanner;
import java.util.Stack;

public class StackTest {

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        Stack<Integer> stack1 = new Stack<>();
        for (int i = 0; i < 5; i  ) {
            stack1.push(input.nextInt());
        }

        System.out.println("------------------");
        findSmallest(stack1);
        for (int i = 0; i < 5; i  ) {
            System.out.println(stack1.pop());
        }
    }

    public static void findSmallest(Stack<Integer> stack1) {

        Stack<Integer> stack2 = new Stack<>();
        Integer min = stack1.peek();
        int i = 0;
        while(i < 5) {
            if(stack1.peek() < min)
                min = stack1.peek();
            stack2.push(stack1.pop());
            i  ;
        }
        int j = 0;
        while (j < 5) {
            if(!(stack2.peek().equals(min)))
                stack1.push(stack2.pop());
            j  ;
        }
        stack1.push(min);
        stack2.pop();
    }
}

CodePudding user response:

Avoid hard-coded values like while (i < 5).

You need to empty out the first stack and populate the second stack with all the contents of the first stack.

While doing this, you need to check every element against the minimal element previously encountered and a new minimal element was found, then you need to update its value and position.

After that, we need to do the opposite: populate the first stack with the contents of the second stack, with one exception - we need to skip the index that corresponds to the minimum element. For that, we can use the same index, i.e. no need to define a separate variable.

That how it can be implemented.

public static void findSmallest(Stack<Integer> stack1) {
    if (stack1.isEmpty()) return; // guarding condition against an empty stack
    
    Stack<Integer> stack2 = new Stack<>();
    int min = stack1.peek();
    int minInd = 0;
    int ind = 0;
    
    while(!stack1.isEmpty()) {
        int next = stack1.pop();
        if (next < min) {
            min = next;    // updating the minimum value
            minInd = ind;  // updating the minimum index
        }
        stack2.push(next); // saving the next element in the second stack
        ind  ;             // updating the index
    }
    
    while (!stack2.isEmpty()) {
        int next = stack2.pop();
        if (ind == minInd) {
            ind--;         // updating the index
            continue;      // moving to the next iteration step (we should skip the min number - it will be added at the top afterwards)
        }
        stack1.push(next); // saving the next element in the second stack
        ind--;             // updating the index
    }
    
    stack1.push(min);      // adding the min number at top
}

Note: class Stack is legacy and not encouraged to be used (it's still there for backward compatibility reasons). When you need an implementation of the Stack data structure in Java - use standard implementations of the Deque interface from the JDK. So if you're not required to use Stack class according to your assignment, you can substitute it with ArrayDeque.

CodePudding user response:

This section of your code is the problem:

while (j < 5) {
            if (!(stack2.peek().equals(min))) 
              stack1.push(stack2.pop());
            j  ;
        }

Why is this the issue?

What you were trying to do here in your if statement was

  1. Check the num at the top of stack2, if it's the min then skip it.
  2. If num is not the min, then put num on top of stack1. --> That itself is 2 steps: [a] pop num off of stack2 and [b] push num on top of stack1.

What happens in the case where you find the minimum? You ignore step 2 - which means that you never pop the top - which is the min - off of stack2. Consequently, when you loop back around again, the top of stack2 is still the min.

How do you fix it? Here's one way:

    while (j < 5) {
            int num = stack2.pop();//NOTE: I pop here instead of below
            if (num != min) stack1.push(num);//I cleaned up this line a bit
            j  ;
        }
        stack1.push(min);
        //NOTE: I deleted the pop from here, because I did it above

Aside: There are other ways to improve this code, but it seems like you have a lot to learn, so I only addressed the specific question you were asking so as not to overwhelm you.

  • Related