Good evening.
I have a rather involved question. To practice Java, I've been re-implementing some of the data structures in the standard library. Stacks, LinkedLists, Trees, etc. I just established, through a very simple example, that the java.util.Stack class performs a deep copy when either the peek() or pop() methods are used. This is understandable, since the goal would be to protect the contents of the class from outside interference. So far, in my own implementation of the Stack (a naive implementation with a simple array, linked lists will come later), I have not cared for this at all:
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!
}
Unfortunately, since a generic cannot be instantiated, I cannot assume a copy constructor and do stuff like return new T(data[top--]); I've been looking around in S.O and I've found two relevant threads which attempt to solve the problem by using some variant of clone(). This thread suggests that the class's signature be extended to:
public class ArrayStack<T extends DeepCloneableClass> implements Stack<T>
...
where DeepCloneableClass is a class that implements an interface that allows for "deep cloning" (see the top response in that thread for the relevant details). The problem with this method, of course, is that I can't really expect from standard classes such as String or Integer to be extending that custom class of mine, and, of course, all my existing jUnit tests are now complaining at compile-time, since they depend on such Stacks of Integers and Strings. So I don't feel as if this solution is viable.
This thread suggests the use of a third-party library for cloning pretty much any object. While it appears that this library is still supported (latest bug fixes date from less than a month ago), I would rather not rely on third-party tools and use whatever Java can provide for me. The reason for this is that the source code for these ADTs might be someday shared with undergraduate college students, and I would rather not have them burdened with installing extra tools.
I am therefore looking for a simple and, if possible, efficient way to maintain a generic Java data structure's inner integrity while still allowing for a simple interface to methods such as pop(), peek(), popFront(), etc.
Thanks very much for any help!
Jason
Why do you need to clone the objects?
Your stack just has a collection of references. You probably don't need to clone them, just make a new array and put the appropriate references in it, then throw away the old array.