Suppose there is a long line of people at a check-out counter in a store. A new

Question

Suppose there is a long line of people at a check-out counter in a store. A new counter is opened, and people in the even positions (second, fourth, sixth, etc.) in the original line are directed to the new line. If a check-out counter line is modeled using a Queue class, we can implement this "even split" operation in this class.

Assume that a Queue class is implemented using a CLL, with a rear field that refers to the last node in the queue CLL, and that the Queue class already contains the following constructors and methods:

Implement an additional method in this class that would perform the even split:

Derive the worst case big O running time of your implementationYou may assume that the constructors and existing methods of the Queue class all have a worst case O(1) running time.

Explanation / Answer

public Queue<T> evenSplit(){
   Queue<T> temp_1 = new Queue<T>();
   Queue<T> temp_2 = new Queue<T>();
   int i = 1;
   while (this.size() > 0){
       // Remove odd element from the Queue and add to temp_1
       if (i % 2 == 1)
           temp_1.enqueue(this.dequeue());
       // Remove even element from the Queue and add to temp_2
       else
           temp_2.enqueue(this.dequeue());
       i += 1;
   }
   // add all odd element back to the Original Queue
   while (temp_1.size() > 0)
       this.enqueue(temp_1.dequeue());
  
   // return temp_2 as it has all even position elements
   return temp_2;
}

Time Complexity
=> let the size of Original Queue is n;
=> We have performed enqueue operation for (n + n/2 times) and dequeue operation for (n + n/2 times)
=> Size is checked for (n+n/2 times) using size() function
so total time Complexity is
=> 3*n + 3*(n/2);
=> O(9*n/2)
=> O(n)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.