PLEASE HELP WITH THIS Queue Implementation A programmer proposes the following i

Question

PLEASE HELP WITH THIS

Queue Implementation

A programmer proposes the following implementation of a queue using a List:

Create a queue by creating the List: List myQueue = new ... // some list constructor

Use myQueue.add( item ) to implement the enqueue operation. This adds at the end of the list, so the end of the list will be the rearof the queue, and the beginning of the list will be the front of the queue.

Use myQueue.get( 0 ) to implement the front operation -- examine the item at the front of the queue.

Use myQueue.remove( 0 ) to implement the dequeue operation -- remove the item at the front of the queue.

Which kind of list should be used: ArrayList or LinkedList? Evaluate and comment on the efficiency of each of these options. Would one of these be more efficient? If so, why? Use "Big-O" notation to describe the complexity of each of the four operations listed.

Explanation / Answer

Queue

   Operation                   ArrayList           LinkedList

   add(T)/enqueue                   O(1)               O(1)
   remove(0)/dequeue              O(n)               O(1)
   get(0)/front                           O(1)               O(1)

add(T)/enqueue : Need to add the rear(last),hence it takes constant time to add an element at end in both array and linked list
remove(0).dequeue: Need to remove first element
           In arraylist, removing first element needs to shift all elements right to first, one by left
                   But, in the linked list removing first element is the constant time operation

get(0)/front : getting first element from both array list/linked list is a constant operation

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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