C++ a.) Write a pseudocode algorithm to solve the following problem: Given 2 que

Question

 C++ a.) Write a pseudocode algorithm to solve the following problem:  Given 2 queues, Q1 & Q2, merge them into a single queue, Q3.  Each element in the queues have an arrival time data member,  which stores the time that they were inserted into their queue.  Elements with lower time values were inserted first.  When done, the values in Q3 should be stored with their arrival times in ascending order.  You are not changing the arrival times, only accessing them to decide which element should be stored in Q3 next.  You may only use the ADT operations listed in the slides: enqueue, dequeue, getFront, size, isEmpty.   b.) What is the Big-Oh running time complexity of your algorithm above. Explain. 

Explanation / Answer

Struct Queue

{

   int element;

   int time;

   int front;

   int rear;

  }Q[size];

Queue merge (Queue Q1,Queue Q2)

{

Queue Q3;

For(i=Q1.front,j=Q2.front;i<=Q1.size,j<=Q2.size;i++,j++)

{

If(Q1[i].time>=Q2[j].time)

   Q3.enqueue(Q1.dequeue);

else

   Q3.enqueue(Q2.dequeue);

}

For(i=Q1.front;i<=Q1.size;i++)

   Q3.enqueue(Q1.dequeue);

For(j=Q2.front; j<=Q2.size; j++)

   Q3.enqueue(Q2.dequeue);

Return Q3;

}

Time Complexity: O(n2)

Because each enqueue and dequeue operation takes O(n) and the enqueue and dequeue operations are called within for loop so overall complexity is O(n2).

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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