Stack implementation using LinkedList in Java

Question

I came across this solution for stack implementation using Linked List on Leetcode and I understood almost all the logic behind it except the min part. Can anyone please explain how the code is keep tracking of the minimum element after the first minimum element is popped?

Code

class MinStack {
    private Node head;
        
    public void push(int x) {
        if (head == null) 
            head = new Node(x, x, null);
        else 
            head = new Node(x, Math.min(x, head.min), head);
    }
    
    public void pop() {
        head = head.next;
    }
    
    public int top() {
        return head.val;
    }
    
    public int getMin() {
        return head.min;
    }
        
    private class Node {
        int val;
        int min;
        Node next;
            
        private Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
}

Maybe I misunderstand the implementation, but it does not seem to work (Ideone demo). — Turing85
– Turing85, Commented Aug 20, 2021 at 15:09
@Turing85 the test code you use starts by pushing 0 and increments from there, so the minimum will always be 0. — Tim Moore
– Tim Moore, Commented Aug 20, 2021 at 15:13
@TimMoore I know. But I would normally expect hat the data structure organizes the values internally (like a min heap). But thenn again: Maybe i misunderstand the implementation. Without a clear problem statement, it is hard to know what the exact requirements for the data structure are. — Turing85
– Turing85, Commented Aug 20, 2021 at 15:15
It isn't ordering by minimum element, it's just tracking what the minimum is. — Tim Moore
– Tim Moore, Commented Aug 20, 2021 at 15:17

Tim Moore · Accepted Answer · 2021-08-20 15:12:34Z

1

When you push a new node to the head of the stack, the new minimum will either be the new node, or the previous minimum, which is stored in the previous head. When you pop the head, it reverts back to the previous minimum, stored in the previous head. Because getMin() always looks at the current head, this gives the correct result.

Try stepping through some examples:

Start with an empty stack
push 5 -> stack with one node with val = 5, min = 5, next = null

(I'll use abbreviated notation (val, min, next) like (5, 5, null) from now on)
push 10 -> stack with two nodes (10, 5, (5, 5, null))
push 1 -> (1, 1, (10, 5, (5, 5, null)))
pop -> back to (10, 5, (5, 5, null))
pop -> back to (5, 5, null)

answered Aug 20, 2021 at 15:12

Tim Moore

9,5572 gold badges26 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Saurav Shrivastav Over a year ago

When you pop the head, it reverts back to the previous minimum, stored in the previous head. This line is golden, thank you so much. I even saw this when I debugged the code in my IDE but i didn't paid much attention at that time cz somehow I was more focused that something magical is happening internally which i was really curious to know about . But now when you mentioned it , it immediately clicked and it all makes sense now. Thank you so much again!!

Collectives™ on Stack Overflow

Stack implementation using LinkedList in Java

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related