CC-7 : Implement Priority Queue.

Description:

In a priority queue elements are processed based on their order/priority, rather than their their insertion order. In remove/ de-queue operation a priority queue returns elements with higher priority before elements with lower priority. Implement a Priority Queue that stores integers in ascending order.

Test cases and expected outputs:

Input Parameters	Expected outputs
QueuePriority queue=new QueuePriority(); queue.addByPriority(99); queue.addByPriority(14); queue.addByPriority(77); queue.addByPriority(34); queue.addByPriority(21); queue.addByPriority(82);	Queue nodes: 14 <- 21 <- 34 <- 77 <- 99
queue.remove(); queue.remove(); queue.remove(); queue.add(44); queue.add(55);	Queue nodes: 34 <-44<-55<-77<- 99

Pseudocode:

Refer to code for Queue implementation from code challenge1.

For Priority Queue we just to need to replace add() method in Queue code by addByPriority() method. Rest of the code remains the same.

addByPriority() method:

If Priority Queue is currently empty, set new node as firstNode of Priority Queue.

Else If new node’s data is greater than data of firstNode, set new node as firstNode of priority Queue.

Else Navigate the Priority Queue’s nodes from firstNode onwards. Keep going tonext node till we find a node thats data is lesser than data of new node. Insert new node between the current node and its previousNode.

Else if while navigating if we reach end of the Priority Queue (that is all nodes data is less than data of new node) then add new node as last node of the Priority Queue.

Code:

public class QueuePriority {	
	
private QueueNode firstNode=null;
	
public int get() {
	if (firstNode !=null) {
		return firstNode.getNodeData();
	}
	return Integer.MIN_VALUE;
}

public boolean addByPriority(int data){
	QueueNode node=new QueueNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(null);
		return true;		
	}
	if (firstNode.getNodeData()<=data) {
		node.setNextNode(firstNode);
		firstNode=node;
		return true;				
	}
	QueueNode currNode=firstNode;
	QueueNode prevNode=null;
	while (( currNode != null) && (currNode.getNodeData() > data))	{
		prevNode=currNode;
		currNode=currNode.getNextNode();				
	}
	if (currNode != null) {
		prevNode.setNextNode(node);
		node.setNextNode(currNode);
		return true;
	} 
	if (currNode == null){
		prevNode.setNextNode(node);
		node.setNextNode(null);
	}	
	return true;
}

public int remove() {
	if (firstNode == null) { return Integer.MIN_VALUE; }
	int removedData=firstNode.getNodeData();
	if (firstNode.getNextNode()==null) {
		firstNode=null; 
		return removedData;
	}
	firstNode=firstNode.getNextNode();
	return removedData;
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class QueuePriority {	
	
private QueueNode firstNode=null;
	
public int get() {
	if (firstNode !=null) {
		return firstNode.getNodeData();
	}
	return Integer.MIN_VALUE;
}

public boolean addByPriority(int data){
	QueueNode node=new QueueNode();
	node.setNodeData(data);
	if (firstNode==null) { 
		firstNode=node; 
		node.setNextNode(null);
		return true;		
	}
	if (firstNode.getNodeData()<=data) {
		node.setNextNode(firstNode);
		firstNode=node;
		return true;				
	}
	QueueNode currNode=firstNode;
	QueueNode prevNode=null;
	while (( currNode != null) && (currNode.getNodeData() > data))	{
		prevNode=currNode;
		currNode=currNode.getNextNode();				
	}
	if (currNode != null) {
		prevNode.setNextNode(node);
		node.setNextNode(currNode);
		return true;
	} 
	if (currNode == null){
		prevNode.setNextNode(node);
		node.setNextNode(null);
	}	
	return true;
}

public int remove() {
	if (firstNode == null) { return Integer.MIN_VALUE; }
	int removedData=firstNode.getNodeData();
	if (firstNode.getNextNode()==null) {
		firstNode=null; 
		return removedData;
	}
	firstNode=firstNode.getNextNode();
	return removedData;
}

public int getSize() {
	QueueNode currentNode=firstNode;
  	int idx=0;
  	while (currentNode !=null) {
  		currentNode=currentNode.getNextNode();
  		idx++;
  	}
  	return idx;
}

public void traverse() {
	QueueNode currentNode=firstNode;
	while (currentNode !=null) {
  		System.out.println(currentNode.getNodeData());
  		currentNode=currentNode.getNextNode();
  	}
}			

public void printQueue() throws Exception    {
    if (firstNode == null) { System.out.println("Linked list empty"); return; }
    QueueNode currentNode=firstNode;
	System.out.println();
	System.out.println("**************************************************************");
	System.out.print("Queue nodes: ");
	do  {
	    System.out.print(currentNode.getNodeData());
	    if (currentNode.getNextNode() != null)  System.out.print(" <- ");
		currentNode=currentNode.getNextNode();
	} while( currentNode != null);
		System.out.println();
		System.out.println("**************************************************************");
		System.out.println();
		Thread.sleep(2000);
		return;
}  
  	
public static void main(String[] args) {
	/* Test Cases provided below; */
	try {
	QueuePriority queue=new QueuePriority();
	System.out.print("Add to Queue");
	queue.addByPriority(99);
	queue.printQueue();
	System.out.print("Add to Queue");
	queue.addByPriority(14);
	queue.printQueue();
	System.out.print("Add to Queue");
	queue.addByPriority(77);
	queue.printQueue();
	System.out.print("Add to Queue");
	queue.addByPriority(34);
	queue.printQueue();
	System.out.print("Add to Queue");
	queue.addByPriority(21);
	queue.printQueue();
	System.out.print("Add to Queue");
	queue.addByPriority(82);
	queue.printQueue();
	
	System.out.println("QUEUE SIZE "+queue.getSize());
	
	System.out.print("\nRemove from Queue");
	queue.remove();
	queue.printQueue();
	System.out.print("Remove from Queue");
	queue.remove();
	queue.printQueue();
	System.out.print("Remove from Queue");
	
	System.out.println("GET FIRST NODE "+queue.get());
	
	queue.remove();
	queue.printQueue();
	System.out.print("\nRemove from Queue");
	queue.remove();
	queue.printQueue();
	System.out.print("Remove from Queue");
	queue.remove();
	queue.printQueue();
	System.out.print("Remove from Queue");
	queue.remove();
	queue.printQueue();
	
	System.out.println("QUEUE SIZE "+queue.getSize());
	System.out.println("\nGET FIRST NODE "+queue.get());
	
	System.out.print("Add to Queue");
	queue.addByPriority(99);
	queue.printQueue();
	System.out.print("Add to Queue");
	queue.addByPriority(9);
	queue.printQueue();
	System.out.print("Add to Queue");
	queue.addByPriority(31);
	queue.printQueue();
	System.out.print("Remove from Queue");
	queue.remove();
	queue.printQueue();
	System.out.print("Remove from Queue");
	queue.remove();
	queue.printQueue();	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
	}
	
}

public class QueueNode {
	private QueueNode nextNode=null;
	private int nodeData=0;
	public QueueNode getNextNode() {
		return nextNode;
	}
	public void setNextNode(QueueNode nextNode) {
		this.nextNode = nextNode;
	}	
	public int getNodeData() {
		return nodeData;
	}
	public void setNodeData(int nodeData) {
		this.nodeData = nodeData;
	}
}
	
}