在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