CC-13 : Remove Duplicate elements from Queue.

Description:

Given a Queue, remove duplicate elements from it and preserve order of rest of elements of the Queue.

Test cases and expected outputs:

Input Parameters	Expected outputs
Queue< Integer > queue = new LinkedList< Integer >(); queue.add(9); queue.add(14); queue.add(17); queue.add(34); queue.add(21); queue.add(28); queue.add(21); queue.add(14); queue.add(21); queue.add(33); printQueue(queue); System.out.println("Removing duplicate nodes.."); QueueRemoveDuplicateElements queueRemoveDuplicateElements= new QueueRemoveDuplicateElements(); queueRemoveDuplicateElements. queueRemoveDuplicateElements(queue);	Add to Queue Queue nodes: 9 <- 14 <- 17 <- 34 <- 21 <- 28 <- 21 <- 14 <- 21 <- 33 <- Removing duplicate nodes.. Queue nodes: 9 <- 14 <- 17 <- 34 <- 21 <- 28 <- 33 <-

Input Parameters

Expected outputs

Queue< Integer > queue = new LinkedList< Integer >();
queue.add(9);
queue.add(14);
queue.add(17);
queue.add(34);
queue.add(21);
queue.add(28);
queue.add(21);
queue.add(14);
queue.add(21);
queue.add(33);
printQueue(queue);
System.out.println("Removing duplicate nodes..");
QueueRemoveDuplicateElements
queueRemoveDuplicateElements=
new QueueRemoveDuplicateElements();
queueRemoveDuplicateElements.
queueRemoveDuplicateElements(queue);

Add to Queue
Queue nodes:
9 <- 14 <- 17 <- 34 <- 21 <- 28 <- 21 <- 14 <- 21 <- 33 <-

Removing duplicate nodes..
Queue nodes: 9 <- 14 <- 17 <- 34 <- 21 <- 28 <- 33 <-

Pseudocode:

Declare and initialize a HashMap to hold frequencies of occurrence of data elements in the input Queue.

Using a for loop iterate through all elements of input Queue:

If the current element does not exist in the HashMap, add it to HashMap with frequency of 1.

Else If the current element exists in the HashMap, add increment its frequency in the HashMap by 1.

If current nodes frequency == 1 then remove it from the start of Queue and add it to the end of the Queue.

If current nodes frequency != 1 the remove it from the start of Queue.

Code:

public Queue< Integer > queueRemoveDuplicateElements(Queue< Integer > queue) {
	HashMap< Integer, Integer > cntMap=new  HashMap< Integer,Integer >();
	int curr=0; int qSize=queue.size(); 
	int cnt=0;
	for (int idx=0;idx < qSize ; idx++) {
		curr=queue.remove();
		cntMap.put(curr, cntMap.getOrDefault(curr, 0)+1);
		if (cntMap.get(curr) == 1) {
			queue.add(curr);
		}
	}
	return queue;
}

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.

import java.util.*;
import java.util.Queue;

public class QueueRemoveDuplicateElements {
	
public Queue< Integer > queueRemoveDuplicateElements(Queue< Integer > queue) {
	HashMap< Integer, Integer > cntMap=new  HashMap< Integer,Integer >();
	int curr=0; int qSize=queue.size(); 
	int cnt=0;
	for (int idx=0;idx < qSize ; idx++) {
		curr=queue.remove();
		cntMap.put(curr, cntMap.getOrDefault(curr, 0)+1);
		if (cntMap.get(curr) == 1) {
			queue.add(curr);
		}
	}
	return queue;
}

public static void printQueue(Queue<Integer> queue) throws Exception   {
    if (queue.size() == 0) { System.out.println("Queue empty"); return; }
    System.out.println();
	System.out.println("*********************************************************************");
	System.out.print("Queue nodes: ");
	Iterator itr=queue.iterator();
	while (itr.hasNext())  {
	    System.out.print(itr.next());
	    System.out.print(" <- ");
	} 
	System.out.println();
	System.out.println("*********************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}
  	
public static void main(String[] args) {
	try {
	Queue<Integer> queue=new LinkedList<Integer>();
	System.out.println("Add to Queue");
	queue.add(9);
	queue.add(14);
	queue.add(17);
	queue.add(34);
	queue.add(21);
	queue.add(28);
	queue.add(21);
	queue.add(14);
	queue.add(21);
	queue.add(33);
	printQueue(queue);
	
	System.out.println("Removing duplicate nodes..");
	QueueRemoveDuplicateElements queueRemoveDuplicateElements=new QueueRemoveDuplicateElements();
	queue=queueRemoveDuplicateElements.queueRemoveDuplicateElements(queue);
	printQueue(queue);
	

}catch (Exception exception) {
	System.out.print("Exception: "+ exception);
	}
	
}
	
}