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中的最小值

回答

相關問題