5. List and explain the Big-Oh runtimes of enqueue, dequeue, and getFront for 2 different implemenations of a queue. Both implementaions use a node-based implementation (single-link) that has pointers to both the head and tail nodes:

Implementation 1: enqueues at the head and dequeues at the tail Implementation 2: enqueues at the tail and dequeues at the head

A)

Implementation 1) Enqueue = O(1) as putting node in head takes constant time.

Dequeue = O(n) as to delete a node from tail we have to scan the whole list first.

getFront = O(1) as we are enqueuing at the head.

Implementation 2) Enqueue = O(n) as to insert a node from tail we have to scan the whole list first.

Dequeue = O(1) as deleting a node in head takes constant time

getFront = O(n) as we are enqueuing at the tail.

6. Suppose you have a circular array-based implementation of a Queue (as shown in the slides) and the array has a size of 100. If the data field front has the value 98 and the data field rear has the value 1, what will the values of front and rear be if 3 dequeue operations are performed, followed by 1 enqueue operation?

After 3 dequeue and 1 enqueue operation :-

Front = 4

Rear = 99 8. If instead of the erase function, the programmer uses the STL lists remove function in the previous question, what is the function's Big-Oh runtime now?