为堆栈正确编写 java 中的面向对象代码

Question

我正在尝试以面向对象的方式编写代码。在这种特殊情况下，我想在 O(1) 时间内跟踪堆栈的最小值。我知道怎么做，它的想法，我的想法，就是有另一个堆栈来跟踪每次推送和弹出的最小值。

我已经将每个 class 嵌套在程序 class 中，它被称为 minStack，这似乎不是正确的做法但是，当我创建 minStack 的实例并调用其变量时，它对于常规堆栈来说效果很好。我创建了一个 class extends a Stack called StackWithMin 但我不知道如何调用它的值。我应该创建一个 StackWithMin 的新实例吗？如果是这样我该怎么做？我在 main 函数上面的代码末尾做了它，但是 peek() 总是 returns 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();
}

Generics add stability to your code by making more of your bugs detectable at compile time.

查看有关泛型的更多信息here。

然后用通用的方式实现这个接口。所有实现细节都将隐藏在此 class 中（例如您的 Node class）。这是代码（它只是为了展示这个想法，如果你想使用它你需要通过异常处理来改进它）。请注意 class 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 class 并使用另一个 SimpleStack 添加字段。但是我认为最好再实现 Stack 并为值和最小值存储两个堆栈。示例如下。我已经概括了现在使用 Comparator 比较对象的 class，因此您可以使用任何其他对象类型。

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

为堆栈正确编写 java 中的面向对象代码

Properly Writing Object Oriented Code in java for a stack

java

stack

object-oriented-analysis