CodesJava

Easy learning with example program codes

Java PriorityQueue implementation


A queue is an ADT – Abstract Data Type or a linear data structure. It is a FIFO data structure because element inserted first will be removed first. FIFO stands for First-in-first-out. Queue use one end to insert data which is called REAR or tail and other end to remove the data which is called FRONT or head.

Queue operations

  • enqueue(): Insert an item to the queue.
  • dequeue(): Remove an item from the queue.
  • peek(): Get the top data element of the queue, without removing it.
  • isFull(): Check if queue is full.
  • isEmpty(): Check if queue is empty.

Queue states

  • Overflow state: A queue is in overflow state if it does not contain enough space to accept an entity to be inserted.
  • Underflow state: A queue is in underflow state if we want to operate stack with dequeue operation and the queue is empty.

PriorityQueue Queue

PriorityQueue extends AbstactQueue. PriorityQueue is a type of queue but not provide the FIFO facility to its elements. It not allows the null elements. A PriorityQueue is like a normal queue but each element has a priority associated with it.

Example

package com.codesjava;
 
public class Test {
    @SuppressWarnings("rawtypes")
    private Comparable[] pQueue;
    private int index;
 
    public Test(int capacity){
        pQueue = new Comparable[capacity];
    }
 
    public void insert(Comparable item ){
        if(index == pQueue.length){
            System.out.println("Overflow state.");
            return;
        }
        pQueue[index] = item;
        index++;
        System.out.println("Adding element: "+item);
    }
 
    @SuppressWarnings("unchecked")
    public Comparable remove(){
        if(index == 0){
            System.out.println("Underflow state.");
            return null;
        }
        int maxIndex = 0;
        for (int i=1; i<index; i++) { 
            if (pQueue[i].compareTo (pQueue[maxIndex]) > 0) { 
                maxIndex = i; 
            } 
        } 
        Comparable result = pQueue[maxIndex]; 
        System.out.println("removing: "+result);
        index--; 
        pQueue[maxIndex] = pQueue[index]; 
        return result;
    }
 
	public static void main(String args[]){
		try {
			Test pQueue = new Test(3);
			pQueue.insert(15);
			pQueue.insert(8);
			pQueue.insert(12);
			pQueue.remove();
			pQueue.remove();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

Output

Adding element: 15
Adding element: 8
Adding element: 12
removing: 15
removing: 12
Sign Up/ Sign In
Ask a Question


Copyright © 2018 CodesJava DMCA.com Protection Status SiteMap Reference: Java Wiki