A Priority Queue is an Abstract Data Type that acts as a queue except that the o

Question

A Priority Queue is an Abstract Data Type that acts as a queue except that the order in which items are Dequeued is determined by their p i.e., the item with the highest priority is Dequeued first. Accordingly, ItemType has a member variable, intpriority, which is used by CompareTo() to order items. Suppose we modify the circular array version of QueueType to make it a priority queue. Enqueue works as usual: the new item is placed at the rear of the queue, regardless of priority. Dequeue works differently: First, the queue is searched for the item of highest priority, which is then returned by reference. Then, the dequeued item replaced with the last item in the queue, and the rear index is updated accordingly. Implement this new version. Suppose we change the implementation in part (a) to keep the circular array sorted at all times. Compare the performance of both approaches.

Explanation / Answer

/**
*
* @author Sam
*/
public class PriorityQueue <T extends Comparable<T>> {
    T[] queue;
    int front, rear;
    int size;
    public PriorityQueue(int size) {
        queue = (T[]) new Object[size];
        front = 0;
        rear = 1;
        this.size = size;
    }
  
    public void enqueue(T value) {
        if ((front == 0 && rear == size-1) ||(rear == front-1)) {
            System.out.println("Queue is Full");
            return;
        }

        else if (front == -1) { //for First Element
            front = rear = 0;
            queue[rear] = value;
        }

        else if (rear == size-1 && front != 0)
        {
            rear = 0;
            queue[rear] = value;
        }

        else
        {
            rear++;
            queue[rear] = value;
        }
    }
  
    public T dequeue() {
        if (front == -1) {
            System.out.println("Queue Empty");
            return null;
        }
      
        int maxPos = rear; //maxPos stores the location of max data
        int pos = rear; //let us start from pos
      
        while(pos!=front) {
            pos ++;
            if (pos == size)
                pos = 0;          
            if (queue[pos].compareTo(queue[maxPos]) > 0)
                maxPos = pos;
        }
        if (front == rear) //one one item was present, no need to replace
        {
            front = -1;
            rear = -1;
        }
        else {
            queue[maxPos] = queue[front];
            if (front == size-1)
                front = 0;
            else
                front++;
        }
      
        return queue[maxPos];
    }
}

Here you go champ... the code is there for you. Enqueue method is same as it should be so didnt comment. Dequeue is commented.

b.

In this case the time complexity:
      enqueue: O(1)
      dequeue: O(n) since it performs linear search

For the case mentioned in the question

      enqueue: O(n) since it need to insert and shift remainin items
      dequeue: O(1)

I hope am clear and this makes sense.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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