在java中正確編寫面向對象的代碼堆棧

Question

我正在嘗試以面向對象的方式編寫代碼。在這種特殊情況下，我想跟蹤O（1）時間內我的堆棧的最小值。我知道該怎麼做，它的想法，以及我對它的想法，也就是有另一個棧來記錄每次推送和流行的最小值。

我嵌套被稱爲minStack程序類，它似乎並不像正確的事情，當我創建minStack的實例，但是這樣做並調用它的變量內每一個類它的作品了罰款一個普通的堆棧。我創建了一個類，擴展一個堆棧稱爲StackWithMin，但我不知道該怎麼稱呼自己的價值觀。我應該創建一個StackWithMin的新實例嗎？如果是的話，我會怎麼做呢？我做了它的主要功能上面的代碼的結束，而是偷看（）始終返回null

class minStack { 

public class Stack { 

    Node top; 
    Object min = null; 

    Object pop() { 
     if(top != null) { 
      Object item = top.getData(); 
      top = top.getNext(); 
      return item; 
     } 
     return null; 
    } 

    void push(Object item) { 
     if(min == null) { 
      min = item; 
     } 
     if((int)item < (int)min) { 
      min = item; 
     } 
     Node pushed = new Node(item, top); 
     top = pushed; 
    } 

    Object peek() { 
     if(top == null) { 
      //System.out.println("Its null or stack is empty"); 
      return null; 
     } 
     return top.getData(); 
    } 

    Object minimumValue() { 
     if(min == null) { 
      return null; 
     } 
     return (int)min; 
    } 
} 

public class Node { 
    Object data; 
    Node next; 

    public Node(Object data) { 
     this.data = data; 
     this.next = null; 
    } 

    public Node(Object data, Node next) { 
     this.data = data; 
     this.next = next; 
    } 

    public void setNext(Node n) { 
     next = n; 
    } 

    public Node getNext() { 
     return next; 
    } 

    public void setData(Object d) { 
     data = d; 
    } 

    public Object getData() { 
     return data; 
    } 
} 

public class StackWithMin extends Stack { 
    Stack s2; 

    public StackWithMin() { 
     s2 = new Stack(); 
    } 

    public void push(Object value) { 
     if((int)value <= (int)min()) { 
      s2.push(value); 
     } 
     super.push(value); 
    } 

    public Object pop() { 
     Object value = super.pop(); 
     if((int)value == (int)min()) { 
      s2.pop(); 
     } 
     return value; 
    } 

    public Object min() { 
     if(s2.top == null) { 
      return null; 
     } 
     else { 
      return s2.peek(); 
     } 
    } 
} 

Stack testStack = new Stack(); 
StackWithMin stackMin = new StackWithMin(); 

public static void main(String[] args) { 
    minStack mStack = new minStack(); 
    //StackWithMin stackMin = new StackWithMin(); 
    mStack.testStack.push(3); 
    mStack.testStack.push(5); 
    mStack.testStack.push(2); 
    mStack.stackMin.push(2); 
    mStack.stackMin.push(4); 
    mStack.stackMin.push(1); 
    System.out.println(mStack.testStack.peek()); 
    System.out.println(mStack.stackMin.peek()); 
    mStack.testStack.pop(); 


} 

} 

Answer 1

我建議創建通用接口Stack這樣一個

interface Stack<T> { 

    void push(T item); 

    T pop(); 

    T peek(); 
} 

泛型添加通過在編譯時使更多的錯誤 可檢測到，從而保持代碼的穩定性。

查看更多有關泛型here。

然後以通用的方式實現這個接口。所有的實現細節都將隱藏在這個類的內部（例如你的Node類）。這裏是代碼（只是爲了展示這個想法，如果你想使用它，你需要改進它，例如異常處理）。請注意，類Node現在也是通用的。

class SimpleStack<T> implements Stack<T> { 

    private class Node<T> { ... } 

    private Node<T> root = null; 

    public void push(T item) { 
     if (root == null) { 
      root = new Node<T>(item); 
     } else { 
      Node<T> node = new Node<T>(item, root); 
      root = node; 
     } 
    } 

    public T pop() { 
     if (root != null) { 
      T data = root.getData(); 
      root = root.getNext(); 
      return data; 
     } else { 
      return null; 
     } 
    } 

    public T peek() { 
     if (root != null) { 
      return root.getData(); 
     } else { 
      return null; 
     } 
    } 
} 

現在我們要與存儲的最小值的部分。我們可以擴展我們的SimpleStack類，並添加另一個字段SimpleStack。不過，我認爲這是更好的做出Stack的另一個實現，並存儲兩個值和最小值的堆棧。示例如下。我已經概括了現在使用Comparator比較對象的類，因此您可以使用任何其他對象類型。

class StackWithComparator<T> implements Stack<T> { 

    private Comparator<T> comparator; 
    private SimpleStack<T> mins = new SimpleStack<>(); 
    private SimpleStack<T> data = new SimpleStack<>(); 

    public StackWithComparator(Comparator<T> comparator) { 
     this.comparator = comparator; 
    } 

    public void push(T item) { 
     data.push(item); 
     if (mins.peek() == null || comparator.compare(mins.peek(), item) >= 0) { 
      mins.push(item); 
     } else { 
      mins.push(mins.peek()); 
     } 
    } 

    public T pop() { 
     mins.pop(); 
     return data.pop(); 
    } 

    public T peek() { 
     return data.peek(); 
    } 

    public T min() { 
     return mins.peek(); 
    } 
} 

現在你可以使用兩種實現像這樣

SimpleStack<Integer> s1 = new SimpleStack<>(); 
s1.push(1); 
s1.push(2); 
s1.push(3); 

System.out.println(s1.pop()); // print 3 
System.out.println(s1.pop()); // print 2 
System.out.println(s1.pop()); // print 1 

StackWithComparator<Integer> s2 = new StackWithComparator<>(new Comparator<Integer>() { 
    public int compare(Integer o1, Integer o2) { 
     return Integer.compare(o1, o2); 
    } 
}); 
s2.push(1); 
s2.push(2); 
s2.push(3); 
s2.push(0); 
s2.push(4); 

System.out.println(s2.min() + " " + s2.pop()); // print 0 4 
System.out.println(s2.min() + " " + s2.pop()); // print 0 0 
System.out.println(s2.min() + " " + s2.pop()); // print 1 3 
System.out.println(s2.min() + " " + s2.pop()); // print 1 2 
System.out.println(s2.min() + " " + s2.pop()); // print 1 1