I'm trying to implement a stack that apart from offering the standard push and pop also returns the minimum value in O(1) time.
This is my code.
import java.util.Comparator;
import java.util.Iterator;
import java.util.ListIterator;
public class MinStack<T> {
private Node head;
private Node minHead;
private T minValue;
private class Node<T extends Comparable<T>> {
private T data;
private Node next;
public Node(T data){
this.data = data;
this.next = null;
}
public int compareTo(T other){
return data.compareTo(other);
}
}
public void push(T item){
Node p = new Node((Comparable) item);
if(head == null){
head = p;
minHead = p;
return;
}
p.next = head;
head = p;
if(((Comparable) item).compareTo(minValue) < 0){
minValue = item;
Node m = new Node((Comparable) item);
m.next = minHead;
minHead = m;
}
}
public T pop(){
if(head == null){
System.out.println("Popping off an empty stack!!!");
System.exit(-1);
}
Node item = (Node) head.data;
if(item == minValue){
minHead = minHead.next;
}
head = head.next;
return (T) item;
}
public T getMin(){
return minValue;
}
public void trace(){
Node current = head;
while(current != null){
if(current.next == null){
System.out.println(current.data);
}else{
System.out.println(current.data + "->");
}
current = current.next;
}
}
public void minTrace(){
Node current = minHead;
while(current != null){
if(current.next == null){
System.out.println(current.data);
}else{
System.out.println(current.data + "->");
}
current = current.next;
}
}
}
When i use the following client code,
MinStack<Integer> stack = new MinStack<>();
stack.push(12);
stack.push(1);
stack.push(7);
stack.push(9);
stack.push(3);
stack.push(2);
stack.trace();
I get a null pointer exception at the line where the T values are compared using the compareTo function. Can someone help me understand what am I doing wrong here.
