我正在尝试为链接堆栈实现浅表副本,但我的老师提供的J单元测试未通过。
我试图实现一个for循环,该循环将在堆栈中从上到下循环,并为每个节点创建对传递的新列表的引用。我添加了一条打印语句,并且数据引用似乎匹配,但是我的测试仍然失败。
public class LinkedStack<E> implements Stack<E>{
private int size = 0;
// Unlike the book, we'll use an inner class for our Node.
// Its two data members can be accessed directly by the Stack
// code, so we don't need setters and getters.
protected class Node{
E data;
Node next;
}
protected Node top; // not public, but can still be seen by other classes in the
// csci211 package.
/** Create an empty stack.
*
*/
public LinkedStack(){
top = null;
}
@Override // see interface for comments.
public void push(E e){
//TODO 75
Node temp = new Node();
temp.data = e;
temp.next = top;
top = temp;
}
@Override // see interface for comments.
public E pop(){
if (top==null) {
throw new NoSuchElementException("Cannout pop an Empty Stack.");
}
E topvar;
topvar = top.data;
top = top.next;
return topvar;
}
@Override // see interface for comments.
public E peek() {
if (top == null) {
throw new NoSuchElementException("Cannout peek an Empty Stack.");
}
//E topvar;
//topvar = top.data;
return top.data;
}
/** Retrieve the number of elements on this stack.
*
* @return an int containing the number of elements
*/
public int size() {
return this.size;
}
/** An Iterator for our LinkedStack.
*
* @author rhodes
*
*/
class LinkedStackIterator implements Iterator<E> {
LinkedStack<E>.Node next; // the book calls this "current"
public LinkedStackIterator(LinkedStack<E> s){
next = s.top;
}
@Override
public boolean hasNext() {
return top != null;
//TODO 100
//return false;
}
@Override
public E next() {
if (!hasNext()) throw new NoSuchElementException();
E data = top.data;
top = top.next;
return data;
//TODO 100
//return null;
}
}
@Override
public void add(E element) {
push(element);
}
@Override
public void clear() {
this.top = null;
this.size = 0;
}
@Override
public List<E> shallowCopy() {
LinkedStack<E> newstack = new LinkedStack<E>();
ArrayList<E> Alist = new ArrayList<E>();
//Iterate through while we haven't hit the end of the stack
Node newtest = top;
while (newtest != null) {
Alist.add(newtest.data);
newtest = newtest.next;
//TODO 85
}
for(int i = Alist.size()-1;i>=0;i--) {
newstack.push(Alist.get(i));
}
return newstack;
}
@Override
public Iterator<E> iterator() {
return new LinkedStackIterator(this);
}
}
这是我失败的Junit测试
@Test
@SuppressWarnings("deprecation") // for Date.setHours(), Date.getHours()
public void shallowCopy1() {
// let's use Date, since it's mutable.
LinkedStack<Date> s = new LinkedStack<Date>();
Date d = new Date();
d.setHours(17);
s.push(d);
LinkedStack<Date> s2 =(LinkedStack<Date>) s.shallowCopy();
Date d2=s2.pop();
// The shallow copy should contain references to the same objects
// as the original.
assertTrue(d == d2);
// So, we can change the Date in the original list using the Date that
// came from the shallow copy.
d2.setHours(14);
assertTrue(d.getHours() == 14);
// I don't usually put two asserts in one test, but this seems like
// an instructive example.
}
@Test(expected=NoSuchElementException.class)
public void shallowCopy2() {
LinkedStack<Integer> s1 = new LinkedStack<Integer>();
for(int i=0; i<10; i++) {
s1.push(i);
}
LinkedStack<Integer> s2 =(LinkedStack<Integer>) s1.shallowCopy();
s2.push(10); // supposed to only affect s2
s2.push(11); // supposed to only affect s2
for(int i=0; i<10; i++) {
s1.pop();
}
int last = s1.pop(); // should throw
}
@Test
public void shallowCopy3() {
LinkedStack<Integer> q1 = new LinkedStack<Integer>();
for(int i=0; i<10; i++) {
q1.push(i);
}
LinkedStack<Integer> q2 =(LinkedStack<Integer>) q1.shallowCopy();
//Let's check that the order of elements is correct in the copy.
for(int i=0; i<10; i++) {
int v1=q1.pop();
int v2=q2.pop();
assertEquals(v1, v2);
}
}
如果有人能指出正确的方向,我将不胜感激。这是一个作业问题。
最佳答案
浅拷贝应尽可能少地重复。集合的浅表副本是集合结构的副本,而不是元素。对于浅表副本,现在两个集合共享各个元素。
深层副本会复制所有内容。集合的深层副本是两个集合,原始集合中的所有元素都重复了。
protected class Node{
E data;
Node next;
Node(Node node){
this.next = node.next;
this.data = node.data;
}
}
@Override
public List<E> shallowCopy() {
// LinkedStack<E> newStack = new LinkedStack<E>();
//Iterate through while we haven't hit the end of the stack
Node s = new Node(top);
while (top.next != null) {
s.next = new Node(top.next);
top = top.next;
s = s.next;
}
System.out.println("FINSHED!");
return (List<E>) s;
}
@Override
public List<E> shallowCopyWithoutUpdatingNodeClass() {
// LinkedStack<E> newStack = new LinkedStack<E>();
//Iterate through while we haven't hit the end of the stack
Node s = new Node(top);
while (top.next != null) {
s.next = new Node();
s.next.next = top.next;
s.next.data = top.data;
top = top.next;
s = s.next;
}
System.out.println("FINSHED!");
return (List<E>) s;
}
答案受启发于:-What is the difference between a deep copy and a shallow copy?