G. A deque (double-ended queue) is an abstract data type similar to a queue, but

Question

G. A deque (double-ended queue) is an abstract data type similar to a queue, but where elements can be added and removed both from the front and the rear of the queue. Much like queues and stacks, deques can be implemented using arrays, circular arrays, singly or doubly linked lists, etc. Consider the following implementations » ArrayDeque: a simple array implementation, which has an instance reference variable to the . CircularArrayDeque: a circular array implementation, which has an instance reference variable LinkedDeque: a (singly) linked list implementation, which has an instance reference variable to array, as well as an instance variable containing the number of elements in the array to the array, as well as instance variables for the current front and rear elements in the array the current head Node of the deque . DoublyLinkedDeque: a doubly linked list implementation, which has an instance reference vari able to the current head Node of the deque and an instance reference variable to the current tail Node of the deque, and doubly linked Nodes. For each of the four methods below, indicate for each implementation if the method can be Fast (that is, its execution time is constant) or if it will be Slow (that is, proportional to the number of elements in the list) Note that both array implementations are based on dynamic arrays, and thus can accommodate any number of elements. However, the array is not automatically shrunk ArrayDeque CircularArrayDequeLinkedDequeDoublyLinkedDeque void addFront(E elem) void addRear(E elem) E removeFront E removeRear0

Explanation / Answer

According to the given definitions in the questions, the following table provides the answers:

  arrayDeque c.arrayDeque LinkedDeque D.LinkedDeque

addFront fast fast fast fast

addRear fast fast slow fast

removeFront fast fast fast fast

removeRear fast fast slow fast

Explanation: I have assumed that in case of the simple queue, we have a reference variable to the front and in the linked queue, we have the only pointer to the front. also, it is given that we have dynamic arrays so no shifting is needed.

For simple queue , we also have a variable for storing size, so every time we need a refernce to rear, we can get it from the front+size -1 . so every operation is fast as it is independent of the size of array elements.

For circular queue, we have both front and rear refernce variables, so every operation is fast.

for linkedqueue, in case of insertion and deletion at rear end, we need to traverse the whole list as we only have a pointer to front end. so these operations will depend on size of list so these are slow. others are fast.

for doublylinkedqueue, we have both front and rear pointers so every operation is fast.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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