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

Question

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 rear of 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. One question remains unanswered: 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. In a manner similar to that used in the previous question, explain how a List could be used to implement a stack. List each operation required for a stack and explain exactly how a List operation (a method from the list interface) could be used to implement it. When the List method requires a parameter, explain what value should be used. Draw a diagram that illustrates the operations in action.

Explanation / Answer

1)
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), so it takes constant time to add an element at end in both array and linked list
remove(0).dequeue: Nedd to remove first element
                   In array, removing first element needs to shift all elements right to first, one by left
                   But in linked list removing first element is constant time operation

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

2)
Stack:
   In stack implementation
       using ArrayList: In this case : starting point(head of array) => bottom of stack, last part (end point) => top of stack
       using LinkedlIst: In this case : starting point(head) => top of stack, end part => bottom of stack

   Operation                   ArrayList           LinkedList

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

add(T)/enqueue : Need to add the rear(last), so it takes constant time to add an element at end in both array and
               starting of linked list
remove(0).dequeue: Nedd to remove top element
                   In array, removing last element needs takes constant time
                   In linked list removing first element is constant time operation

get(0)/front : getting first element fromlinkedlist and last element from array takes constant time

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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