1

晚上好。

我有一个相当复杂的问题。为了练习 Java，我一直在重新实现标准库中的一些数据结构。Stacks、LinkedLists、Trees 等。我刚刚通过一个非常简单的示例确定，当使用or方法时，java.util.Stack该类执行深层复制。这是可以理解的，因为目标是保护课程内容免受外界干扰。到目前为止，在我自己的 Stack 实现中（一个简单的数组的幼稚实现，链表将在后面出现），我根本不关心这个：peek()pop()

public class ArrayStack<T> implements Stack<T> {
    private T[] data; // Will expand the array when stack is full.
    private int top; // serves as both top and count indicator.
    ...
    ...
   @Override
   public T pop() throws EmptyStackException {
    if(top == -1)
        throw new EmptyStackException("Stack is empty.");
    return data[top--]; // Shallow copy, dangerous!
}

不幸的是，由于无法实例化泛型，所以我不能假设一个复制构造函数并执行return new T(data[top--]);我在 SO 中一直在寻找的东西，并且我发现了两个相关线程，它们试图通过使用clone(). 该线程建议将该类的签名扩展到：

public class ArrayStack<T extends DeepCloneableClass> implements Stack<T>
...

在哪里DeepCloneableClass是一个实现允许“深度克隆”的接口的类（有关详细信息，请参阅该线程中的顶部响应）。当然，这种方法的问题在于，我不能真正期望标准类，例如String或Integer扩展我的自定义类，当然，我所有现有的 jUnit 测试现在都在编译时抱怨，因为它们依赖于这样的整数和字符串堆栈。所以我不觉得这个解决方案是可行的。

该线程建议使用第三方库来克隆几乎任何对象。虽然这个库似乎仍然受支持（最新的错误修复日期不到一个月前），但我宁愿不依赖第三方工具，而是使用 Java 可以为我提供的任何东西。这样做的原因是这些 ADT 的源代码有朝一日可能会与本​​科生共享，我不希望他们承担安装额外工具的负担。

因此，我正在寻找一种简单且（如果可能的话）有效的方法来维护通用 Java 数据结构的内部完整性，同时仍然允许与方法的简单接口，例如pop()，peek()、popFront()等方法的简单接口。

非常感谢您的帮助！

杰森

4

4 回答 4

2

为什么需要克隆对象？

您的堆栈只有一组引用。您可能不需要克隆它们，只需创建一个新数组并将适当的引用放入其中，然后丢弃旧数组。

于 2013-09-27T04:40:20.457 回答
1

Integer, Strings, 等都是不可变的，所以它们的内容在设计上是安全的。

至于自定义对象，虽然有经验的 Java 程序员肯定会对此有不同的感受，但实现自定义接口无疑是解决问题的一种方法。

另一种是通过序列化制作<T extends Serializable>（由 , 等实现Integer）String和“克隆”。

但是，如果您想以“正确的方式”教您的学生，我肯定会使用第三方库...您可以在项目中创建一个 lib 文件夹并配置您的构建工具/IDE，以使用将所需的 jar 添加到 Classpath相对路径，因此您的本科生无需安装或设置任何东西。

仅供参考，这个问题可能非常有用。

我一直在使用这种方法教授 Java 入门课程（作为 IT 讲师/不是作为大学教授），而且它不像听起来那么痛苦。

于 2013-09-27T04:55:54.990 回答
0

这些评论帮助我理解了我做错了什么。我正在使用以下示例向我自己和其他人“证明”Java 标准库的集合在提供对集合中对象的引用时会进行深层复制：

import java.util.Stack;

public class StackTestDeepCopy {
    public static void main(String[] args){
        Stack<String> st = new Stack<String>();
        st.push("Jim");
        st.push("Jill");
        String top = st.peek();
        top = "Jack";
        System.out.println(st); 
    }
}

在打印 st 时，我看到对象没有改变，并得出结论，发生了深拷贝。错误的！Strings 是不可变的，因此该语句top = "Jack"不会以任何方式修改String（并不是说任何Object会被这样的语句“修改”，但我没有直截了当），它只是将参考点指向一个新的地方堆。一个涉及实际可变类的新示例使我以自己的方式理解了错误。

现在这个问题已经解决了，我对标准库允许这样做的事实感到非常困惑。为什么访问标准库中的元素被实现为浅拷贝？听起来很不安全。

于 2013-09-27T05:08:50.100 回答
-1

java.util.Stack不做深拷贝：

import java.util.Stack;
public class Test {
    String foo;
    public static void main(String[] args) {
        Test test = new Test();
        test.foo = "bar";
        Stack<Test> stack = new Stack<Test>();
        stack.push(test);
        Test otherTest = stack.pop();
        otherTest.foo = "wibble";
        System.out.println("Are the same object: "+(test.foo == otherTest.foo));
    }
}

结果是：

Are the same object: true

如果它确实做了一个副本，那么 test 和 otherTest 将指向不同的对象。典型的堆栈实现只是返回对添加到堆栈中的同一对象的引用，而不是副本。

您可能还希望在返回之前将数组项设置为 null，否则数组仍将包含对该对象的引用。

于 2013-09-27T05:09:43.010 回答