Java Data structures Queues

  

Suppose you want to create a copy of a queue, Q, without destroying the original queue.

If you simply do Queue C = Q , it will not create a true copy, it just creates a second reference to Q – if Q is changed, C will also change in this case.

  

Here’s one way to do this:

1. Make two empty queues, C and T.

2. while Q is not empty do:

Dequeue Q, called this element e. Make a copy of e, call it e2.

Enqueue e in C, enqueue e2 in T.

3. While T is not empty:

Dequeue T, and enqueue the dequeued element in C

4. C is an identical copy of Q. This is called a deep copy of Q.

Basically we are dequeuing Q, copying the elements to C and keeping a temporary queue T. Then we dequeue the temporary queue T and enqueue into Q.

If we don’t do this, your oroiginal Q will be empty afterwards. Draw some pictures and see for yourself.

Write a method,

public static LinkedList<Integer> copyOfQ(LinkedList<Integer> Q)

to return a copy of an input Queue Q of Integer objects. We are crating a Queue here using JDK’s java.util.LinkedList class.

import java.util.*;

public class CopyQ{

public static LinkedList<Integer> copyOfQ(LinkedList<Integer> Q){

//Your Code below

}

public static void main(String[] args){

LinkedList<Integer> Q= new LinkedList<>();

for (int i=0; i<10; i++){

Q.add(new Integer(i+1));

}

LinkedList<Integer> C= copyOfQ(Q);

System.out.println("Checking Original Queue:");

for(Integer e:Q){

System.out.print(e+" ");

}

System.out.println();

System.out.println("Checking Copy:");

for(Integer e:C){

System.out.print(e+" ");

}

System.out.println();

}

}