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

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  BStep 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  BStep 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堆栈移动到堆栈temppoppushorigin堆栈现在是空的，并且temp堆栈是倒置的创建copy堆栈将所有值从temp堆栈移动到两者origin并copy同时堆栈origin返回到原始内容，并且copy堆栈具有相同的内容。