Stack返回Java中的最小值

我试图实现一个除了提供标准push和pop之外的栈也返回O(1)时间的最小值。Stack返回Java中的最小值

这是我的代码。

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; 
     } 
    } 
}

当我使用下面的客户端代码，

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();

我得到中T值使用的compareTo函数相比，线null pointer exception。有人能帮助我理解我在这里做错了什么。

来源

2016-01-01 Zeus

是否因为minValue未初始化为任何内容？ –

'minValue'为空 – Ramanlfc

if(head == null){ 
      head = p; 
      minHead = p; 
      minValue = //try setting minvalue here 
      return; 
     }

当只有一个元素时，minValue将等于该元素。

来源

2016-01-01 03:49:54

当您弹出最小值时会发生什么？ – Bohemian

您正在获得null pointer exception，因为您的minValue未初始化。在使用之前，尝试用一些默认值进行初始化。

此外，您的意图似乎从数据结构中找到最低值。在这种情况下，Stack不是一个好的解决方案。我会推荐你使用Priority Queue。

还有This link可能会帮助你，如果你仍然与堆栈。

来源

2016-01-01 03:55:42

Stack返回Java中的最小值

回答

相关问题