Queue Concatenation X60068

Modify the LinkedQueue class (included in the public_files section of the problem statement) by implementing a new method called concatenate. A call to concatenate of the form

q1.concatenate(q2)

takes all elements of the LinkedQueue instance q2 and appends them to the end of the LinkedQueue instance q1. The operation should run in $O(1)$ time and should result in q2 being an empty queue.

You should also write a program that uses the class LinkedQueue to process a sequence of orders consisting of an integer number indicating the queue the operation should be applied to, a string of the form enqueue, dequeue, first, last, concatenate, len, print and empty, and an integer number that represents the element to be enqueued if the string was “enqueue”, or the queue that should be concatenated with the queue identified by the number read before the order if the order was “concatenate”. The input begins with an integer number $n>0$ indicating the number of queues to be handled, followed by a sequence of orders. The program should perform each order requested, if it can be executed.

Observation: Although the built-in print method is not defined for queue, you may override the special method __str__ so that the contents of a LinkedQueue instance of integer numbers can be printed without making any call to the public method dequeue.

In particular, you should add the following public methods to the LinkedQueue class:

  def concatenate(self, q):
    # Insert your implementation below


  def __str__(self):
    # In the implementation of this method, assume the queue instance
    # can only contain integer numbers. This is only true in the context
    # of this problem.
    # Insert your implementation below