1

I take two stacks s1 and s2, initialize them with some values, and eventually, both have -1024 as there top.

Now, if I compare peeks of both in an if condition, the results are coming wrong. For example:

if (s1.peek() == s2.peek()) --> returns false

Even when both peeks have -1024 as the values.

BUT

If I take the values in different variables, and then compare, that works just fine. For example:

int first = s1.peek();
int second = s2.peek();
if (first == second) --> returns true

I checked same with other values (eg 10). Direct peek comparison works fine in that case.

Am I doing something wrong by comparing peeks directly or is this related to values being compared somehow?

Below is the minimal coded example (I was doing this just as a practice to implement min stack problem):

public class MinStack {

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(512);
        minStack.push(-1024);
        minStack.push(-1024);
        minStack.push(512);
        minStack.pop();
        System.out.print(minStack.getMin());
        minStack.pop();
        System.out.print(minStack.getMin());
        minStack.pop();
        System.out.print(minStack.getMin());
    }

    Stack<Integer> originalStack;
    Stack<Integer> minStack;

    /** initialize your data structure here. */
    public MinStack() {
        originalStack = new Stack<>();
        minStack = new Stack<>();
    }

    public void push(int x) {
        originalStack.push(x);
        if(minStack.isEmpty() || minStack.peek() >= x)
            minStack.push(x);
    }

    public void pop() {
        if(originalStack.peek() == minStack.peek())
            minStack.pop();
        originalStack.pop();
    }

    public int top() {
        return originalStack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }

}
DroidDev
  • 1,527
  • 4
  • 20
  • 42

1 Answers1

3

This happens because of Integer interning. java.lang.Integer objects representing small values, such as 10, are pre-manufactured, so when you push autoboxed 10 on two separate stacks, the same object is pushed.

Once you get to the place in your code where you peek(), the same object is returned for 10, yet two different objects are returned for -1024. That is why == returns true for 10, but not for -1024.

When you add int variables to receive the peek()-ed values, auto-unboxing takes care of harvesting ints of the same value from Integer, so the code with -1024 works again.

You can fix this by replacing == with equals in your conditional:

if (s1.peek().equals(s2.peek())) --> returns true
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • Perhaps you should check, if the `s1` stack is not empty before checking for equality with `!s1.isEmpty()` – gil.fernandes Sep 07 '18 at 15:04
  • @gil.fernandes I agree, generally you would. However, it looks like OPs code relies on `Stack`'s code throwing an exception in this situation. – Sergey Kalinichenko Sep 07 '18 at 15:05
  • Can you please explain the `pre-manufactured` part more and maybe why it is done for some values and not for some others. – DroidDev Sep 07 '18 at 15:08
  • 1
    @DroidDev This is documented [here](https://docs.oracle.com/javase/7/docs/api/java/lang/Integer.html#valueOf(int)). More info could be found [in this Q&A](https://stackoverflow.com/q/13098143/335858). – Sergey Kalinichenko Sep 07 '18 at 15:14
  • I meet the exact same problem! And I'm very confused, thanks for the explain though I don't understand what is `pre-manufactured` or `autoboxed`. At least I know what I should check. – Zhou Haibo Mar 30 '21 at 06:57