不使用“克隆”复制堆栈或队列

Question

在不使用克隆的情况下复制堆栈和队列。例如，当我调用一个传递堆栈的方法时，我不能修改保留传递的原始堆栈。我需要复制/克隆传递的 Stack 以在方法中更改/使用。我只能使用 Stack.java（附件）。我创建了以下辅助方法：public static Stack<CalendarDate> qToS(Queue<CalendarDate> q) {    Stack<CalendarDate> s = new Stack<CalendarDate>();    while (!q.isEmpty()) {       CalendarDate n = q.remove();       s.push(n);    }    return s; // Return stack s}public static Queue<CalendarDate> sToQ(Stack<CalendarDate> s) {    Queue<CalendarDate> q = new LinkedList<CalendarDate>();    while (!s.empty()) {       CalendarDate n = s.pop();       q.add(n);    }    return q; // Return queue q}/*          Provided as a Stack Class alternative    Limits user to actual Stack methods    so Vector<E> is not available*/public class Stack<E> {    // avoid blanked import of java.util    private java.util.Stack<E> secret;    // default constructor    public Stack() {        secret = new java.util.Stack<E>();    }     // empty that collection    public void clear() {        secret.clear();    }    // should be order constant    public int size() {        return secret.size();    }    // simply have push call push from API    public E push(E a) {        secret.push(a);        return a;    }    // And, empty calls empty from API    public boolean empty() {        return secret.empty();    }    // And my pop() uses pop() form JAVA API    public E pop() {        return secret.pop();    }    // My peek uses their peek    public E peek() {        return secret.peek();    }    // Following are not basic Stack operations    // but needed to do some simple testing    // toString is probably not O(constant)    public String toString() {        return secret.toString();    }}

Answer 1

想象一下您有三个 Stack 的场景，Stack A（您要从中复制的那个）、Stack B（您要复制到的目标）和一个 Stack temp（辅助 Stack）。

Step 1: (The Initial Stack)

|1|  | |  | |

|2|  | |  | |

|3|  | |  | |

 A   TEMP  B

Step 2: (Move elements from Stack A to Temp Stack)

| |  | |  | |

|2|  | |  | |

|3|  |1|  | |

 A   TEMP  B

| |  | |  | |

| |  |2|  | |

|3|  |1|  | |

 A   TEMP  B

| |  |3|  | |

| |  |2|  | |

| |  |1|  | |

 A   TEMP  B

Step 3: (Move elements from Temp stack to Stack A & B)

| |  | |  | |

| |  |2|  | |

|3|  |1|  |3|

 A   TEMP  B

| |  | |  | |

|2|  | |  |2|

|3|  |1|  |3|

 A   TEMP  B

|1|  | |  |1|

|2|  | |  |2|

|3|  | |  |3|

 A   TEMP  B

充分理解的最好方法是举个例子并亲自尝试一下。

Answer 2

要复制堆栈：

• 创建temp堆栈

• 使用和将所有值从origin堆栈移动到堆栈temppoppush

• origin堆栈现在是空的，并且temp堆栈是倒置的

• 创建copy堆栈

• 将所有值从temp堆栈移动到两者origin并copy同时堆栈

• origin返回到原始内容，并且copy堆栈具有相同的内容。