0

I encountered this question in the book Algorithms by Sedgewick and Wayne.

Catenable queues, stacks, or steques. Add an extra operation catenation that (destructively) concatenates two queues, stacks, or steques (see Exercise 1.3.32). Hint: Use a circular linked list, maintaining a pointer to the last item.

The class definition for a queue looks like this.

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.
}

The problem is how do I implement the instance method, or should I even implement one, and should I destructively update both queues? If I try to write an instance method like public void catenate(Queue<Item> other), I can't access other's last node because it is private. If I try to write a static method public static Queue<Item> catenante(Queue<Item> a, Queue<Item> b) I encounter the same problem.

Cœur
  • 37,241
  • 25
  • 195
  • 267
johnson
  • 283
  • 2
  • 9
  • Add getters and setters for the first and last item in the queue. If you create the catenante method within the Queue class, you will have full access to private variables anyway, so this wouldn't be an issue. https://stackoverflow.com/questions/215497/in-java-difference-between-package-private-public-protected-and-private – Zachary Dec 24 '17 at 06:47
  • I do not have access to the private variables of the other queue, which I would need in order to change pointers. I don't think we should use getters and setters since the definition of the Node is private and should be hidden from the client. – johnson Dec 24 '17 at 06:52
  • This has nothing to do with that link on access specifiers. I understand the basics of it well enough. This has something to do with data type design and encapsulation. – johnson Dec 24 '17 at 06:55
  • 2
    I think you misunderstand the purpose for access modifiers. They are not there to hide information from a client. Also, private variables are accessible from within the class they are declared, even if not from the same Object. You could implement a method in the Queue class that will have access to the privately defined first and last attributes even if they belong to another Object. I don't think you understand the basics well enough, hence why I provided the link. – Zachary Dec 24 '17 at 06:57
  • I do not think you are able to do what you mentioned in the second-last sentence. Could you show me how to do that. – johnson Dec 24 '17 at 07:00
  • `public class TestingClass { private int i = 0; public static void main (String args[]) throws Exception { TestingClass test = new TestingClass(); test.i = 234; System.out.println(test.i); } }` – Zachary Dec 24 '17 at 07:02
  • Ah,I guess I have been doing that without realising when implementing equals. equals(ADT other) this.var1==other.var1&& this.var2 == other.var2.Anyway, should the method concatenate(Queue other) destructively update both queues, or just the calling queue. What do you think. – johnson Dec 24 '17 at 07:19
  • If the method is non-static (invoked on a single queue), then it should only update the queue you are invoking the method on. It should not destroy the other. – Zachary Dec 24 '17 at 07:21
  • But I guess to turn two circular queues into a single one, without deep copying both queues, we need to modify both the queues. If we implement public void concatenate(Queue other), other would also have to be modified. – johnson Dec 24 '17 at 07:27

1 Answers1

1

For the sake of completeness, here is a simple implementation. The concatenation is different to how you intend to implement so as to not spoil the question. What the implementation does is show various usage of Access Modifiers, specifically that a variable declared private can still be accessed from within the Class it was declared, regardless of whether it belongs to the same Object that attempting to access it. This is outlined in the access level table below: Access Levels

This shows that a variable declared private is accessibly only within the class it was declared.

As for the purpose of Access Modifiers; they are not explicitly to protect information for "security purposes". They have a role in object oriented programming to encapsulate the implementation; prevent direct access. Remember that with Encapsulation, you are restricting direct access to data while providing methods to allow you to interact with such data. The primary reason I find for Encapsulation is to avoid misuse of a class; For example a user may attempt to adjust the last Node variable to null, which would throw many errors throughout the code below. Getters and Setters are perfectly legitimate ways for allowing various Classes to interact with the data belonging to a Class while still ensuring Encapsulation as you can restrict how a variable can be updated.

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;
        }
    }
}

This is missing remove and implementation for the Iterable interface as they weren't required for basic implementation. Also note there are three concatenate methods there. The first, concatenate, is a static method that will clone two Queues and concatenate one to the other. Cloning is done to avoid overwriting the original Queues. The second, concatenateD1, is a member method that appends a given Queue to the end of the Queue the method is invoked on. This will only modify the Queue that has invoked the method. The final, concatenateD2, is also a member method that appends the given Queue to the end of the Queue that the method is invoked on. This, however, will modify values from the two Queues in question, thus isn't safe if you want to reused the original Objects.

Zachary
  • 1,693
  • 1
  • 9
  • 13
  • "A non-static method would be better as it would avoid this deep cloning." Could you show me how this would work, as in implement it also in the above code. I've thought about this for a while, and was able to find a solution that I think solves this problem, exactly as stated(destructively update) and also uses the hint(Use a circular linked list, maintaining a pointer to the last item). – johnson Dec 24 '17 at 08:33
  • Using only a single instance variable, last. public static Queue concatenate (Queue A, Queue B) { Node newhead=A.last.next; A.last.next=B.last.next; B.last.next=newhead; } – johnson Dec 24 '17 at 08:35
  • After this step, A and B would both be references to the same queue. But, my guess is that this is safe, and we would not have any aliasing problems, because it is a circular list. Any addition and deletion operations to A would modify B and vice versa. – johnson Dec 24 '17 at 08:36
  • The reason why the static method is expensive is because you are required to clone the objects to avoid overwriting. If you are happy to destroy, simply remove the copyA and copyB and point the end of A to the start of B. This will modify the elements in the original A and B. – Zachary Dec 24 '17 at 08:43
  • 1
    Yes, this is what I did, but did you say we could do this also with an instance method? – johnson Dec 24 '17 at 08:44
  • I've added two additional methods to illustrate what I was talking about. It being static doesn't make a difference to performance, cloning the items to avoid destroying the originals does. – Zachary Dec 24 '17 at 08:46
  • 1
    I think we also need to assign this.last = toAdd.last and toAdd.first=this.first. Then we will get this anomaly. insertion is reflected in both queues, but deletion is not. – johnson Dec 24 '17 at 09:04
  • Missed that. Fixed – Zachary Dec 24 '17 at 09:10
  • I guess if we make a deep copy, everything is fine. But if we do not copy, after concatenation, there is still an anomaly. A and B reference the same queue . If we enqueue items in A, this is reflected in B and vice versa, but if we dequeue items in A, this is not reflected in B, and vice versa(if dequeue is implemented using first.next=first.next.next). However I think circular lists get around this issue. Enqueue involves{Node front=last.next; last.next=node; node.next=front}. Dequeue involves{last.next=last.next.next} Both operations modify A and B.Cheers for the wonderful discussion. – johnson Dec 24 '17 at 09:23