java - 连接队列

Question

我在 Sedgewick 和 Wayne 所著的《算法》一书中遇到了这个问题。

可串联的队列、堆栈或队列。添加一个额外的操作串联(破坏性地)连接两个队列、堆栈或steques(参见练习1.3.32)。提示:使用循环链表，维护指向最后一项的指针。

队列的类定义如下所示。

public class Queue<Item> implements Iterable<Item> {
    private Node<Item> first;    // beginning of queue
    private Node<Item> last;     // end of queue
    private int n;               // number of elements on queue

    // helper linked list class
    private static class Node<Item> {
        private Item item;
        private Node<Item> next;
    }
    // methods to add and remove etc.
}

问题是我如何实现实例方法，或者我是否应该实现一个实例方法，以及我是否应该破坏性地更新两个队列？如果我尝试编写像 public void catenate(Queue<Item> other) 这样的实例方法，我无法访问其他人的最后一个节点，因为它是私有(private)的。如果我尝试编写静态方法 public static Queue<Item> catenante(Queue<Item> a, Queue<Item> b)我也遇到同样的问题。

Answer 1

为了完整起见，这里是一个简单的实现。连接与您打算实现的方式不同，以免破坏问题。该实现的作用是显示 Access Modifiers 的各种用法。 ，特别是声明为 private 的变量仍然可以从声明它的类中访问，无论它是否属于尝试访问它的同一对象。下面的访问级别表对此进行了概述:

这表明声明为私有(private)的变量只能在声明它的类中访问。

至于访问修饰符的目的；它们并未明确出于“安全目的”保护信息。它们在面向对象编程中的作用是封装实现；防止直接访问。请记住，通过封装，您可以限制对数据的直接访问，同时提供允许您与此类数据交互的方法。我发现封装的主要原因是避免类的误用；例如，用户可能尝试将最后一个 Node 变量调整为 null，这会在下面的代码中引发许多错误。 Getters 和 Setters 是完全合法的方式，允许各种类与属于某个类的数据进行交互，同时仍然确保封装性，因为您可以限制变量的更新方式。

public class Queue<Item> {
    private Node<Item> first;
    private Node<Item> last;

    private static class Node<Item> {
        private Item item;
        private Node<Item> next;

        public Node (Item item) {
            this.item = item;
        }
    }

    /* Add node to Queue */
    public void add (Item item) {
        Node<Item> node = new Node(item);
        if (last == null) {
            this.first = node;
            this.last = node;
        } else {
            last.next = node;
            this.last = node;
        }
    }

    /* Static concatenate method */
    public static <Item> Queue concatenate (Queue<Item> A, Queue<Item> B) {
        Queue<Item> copyA = A.copy();
        Queue<Item> copyB = B.copy();
        copyA.last.next = copyB.first;
        return copyA;
    }

    /* Copy method to perform a Deep clone */
    public Queue<Item> copy() {
        Queue<Item> queue = new Queue<>();
        Node<Item> iter = first;
        while (iter != null) {
            queue.add(iter.item);
            iter = iter.next;
        }
        return queue;
    }

    /* Concatenate method that will modify the item invoking it */
    public void concatenateD1(Queue<Item> toAdd) {
        Queue<Item> copyToAdd = toAdd.copy();
        this.last.next = copyToAdd.first;
        this.last = copyToAdd.last;
    }

    /* Concatenate method that will modify both arrays invoking it */
    public void concatenateD2(Queue<Item> toAdd) {
        this.last.next = toAdd.first;
        this.last = toAdd.last;
    }

    /* Print method to Test */
    public void print() {
        Node<Item> iter = first;
        while (iter != null) {
            System.out.println(iter.item);
            iter = iter.next;
        }
    }
}

这缺少 Iterable 接口(interface)的删除和实现，因为基本实现不需要它们。另请注意，其中存在三种连接方法。第一个是 concatenate，它是一个静态方法，它将克隆两个队列并将一个队列连接到另一个队列。进行克隆是为了避免覆盖原始队列。第二个 concatenateD1 是一个成员方法，它将给定的 Queue 附加到调用该方法的 Queue 的末尾。这只会修改调用该方法的队列。最后一个 concatenateD2 也是一个成员方法，它将给定的 Queue 附加到调用该方法的 Queue 的末尾。但是，这将修改相关两个队列中的值，因此如果您想重用原始对象，则不安全。