For which of the following representations can all basic queue operations be performed in constant worst-case time?
My answer is that to get the worst case time we should maintain the iterator that correspond to the last item
Assuming that your circular list is singly-linked, and that "the last item" in the circular list is the one that has been inserted the latest, your answer is correct *. In order to prove that you are right, you need to demonstrate how to perform these four operations in constant time:
- Get the front element - Since the queue is circular and you have an iterator pointing to the latest inserted element, the next element from the latest inserted is the front element (i.e. the earliest inserted).
- Get the back element - Since you maintain an iterator pointing to the latest inserted element, getting the back of the queue is a matter of dereferencing the iterator.
- Enqueue - This is a matter of inserting after the iterator that you hold, and moving the iterator to the newly inserted item.
- Dequeue - Copy the content of the front element (described in #1) into a temporary variable, re-point the next link of the latest inserted element to that of the front element, and delete the front element.
Since none of these operations require iterating the list, all of them can be performed in constant time.
* With doubly-linked circular lists both answers would be correct.