1 Based on the Queue ADT specification an application progra

1. Based on the Queue ADT specification, an application programmer has two ways to check for an empty queue. Describe them and discuss when one approach might be preferable to the other approach.

2. Discuss the relative efficiency of the enqueue and dequeue operations for fixed-front and floating-front approaches to an array-based implementation of a queue.

Solution

enqueue: add element to the end of the queue

dequeue: returns the element from the from of the queue removing it.

enqueue operation: • a[size] = element; size++. Performance: O(1) • But, if array fills up, expensive. all n elements have to be copied to a new, larger array. Cost: O(n) in copying. • Think about if you double every time array fills up, what is the average cost per insertion? Suppose array size is 100. • First 100 insertions are cheap (constant time). Next one costs 100 operations. Then, the next 100 will be cheap. Next one costs 200. Then, the next 200 will be cheap, next one costs 400, etc. • One expensive operation makes subsequent ones cheap. Average performance per insert is at most one element copy + one element update. It is still constant time.

save A[0], shift all elements left, and decrement size • Have to shift everything to the left. • Cost: O(size)

Enqueue: O(n) worst-case. O(1): average • Dequeue: O(n)