Question

public class PQueue<E extends Comparable<E>> {
private E[] elements;
private int size;
private int head;
private int tail;
Private int count;  
}
public void enqueue(E item) {
if(isFull()){
return;
}
count++;
elements[tail] = item;
tail = (tail + 1) % size;
}
public E dequeue() {
if(isEmpty()) return null;
int ct = count-1;
E cur = elements[head];
int index = 0;
for(i=1;ct-->0;i++) {
if(cur.compareTo(elements[head+i)%size])<0)
cur = elements[(head+i)%size];
index = i;
}
}
return remove((head+index%size);
public E remove(int index) {
E item = elements[index];
if(index != tail) {
int i;
for(i-index; (i%size)!=tail; i++){
int j = i%size;
elements[j] = elements[(j+1)%size];
}
}
tail = (tail-1)%size;
count--;'
return item;
}
}

public class Test{
public static void main(string[] argv) {
PQueue<Integer> queue=new PQueue<>(20);
for(int i = 1; i < 12; i++)
queue.enqueue(1);
for(int j = 1; j < 12; j++) {
system.out.print(queue.dequeue()+" ");
}
system.out.println();
}
}

1) Suppose the above code compiles, please write down the execution results of "java Test"?

2) Given such a queue with n elements, please use the big-Oh notation to estimate the complexity of the enqueue() operations?

3) Given such a queue with n elements, please use the big-Oh notation to estimate the complexity of the dequeue() operations?

Answer 1

We are 12 number of 1s only to the queue.. which means all the data is same..
1.
When The data is dequeued the max element index is removed.. In this case max element will be at index 0, so first index 0 element is removed, then all the remaining elements are shifted towards their left. This process happens for all 12 numbers..

Hence Output: 1 1 1 1 1 1 1 1 1 1 1 1 

2. Enqueue is always an O(1) operation, since we only need to directly add the element at the end of the list.. There is no need for traversal.

3. Dequeue is always an O(N) operation, since after removing the element, the remaining items need to be shifted to left.. Hence it is an O(N) operation.