CC-9 : Reverse k nodes of a Queue.

Description:

Given a Queue, reverse first k nodes of the same in the Queue.

Test cases and expected outputs:

Input Parameters	Expected outputs
Queue queue=new Queue(); queue.addByPriority(99); queue.addByPriority(14); queue.addByPriority(77); queue.addByPriority(34); queue.addByPriority(21); queue.addByPriority(82); queue.queueReverseKNodes(queue, 3);	Queue nodes: 14 <- 21 <- 34 <- 77 <- 99 After reversal: Queue nodes: 34 <- 21 <-14 <- 77 <- 99
queue.queueReverseKNodes(queue, 4);	Queue nodes: 34 <-44<-55<-77<- 99 After reversal: Queue nodes: 77<-55<-44<-37<- 99
queueRotate.QueueRotate(queue, 1);	Queue nodes: 34 <-44<-55<-77<- 99 After rotation: Queue nodes: 34 <-44<-55<-77<- 99

Pseudocode:

Size of input Queue is n, and k nodes are to be reversed.

Initialize a new Deque.

Remove k nodes from input Queue and add the same to end of Deque.

Remove k nodes from the end of Deque and add to Queue.

• Above step reverses the first k nodes of Queue, but these are at end of updated Queue instead of start. So, remove n-k nodes from start of Queue and add to end of Queue. Now we have Queue with first k nodes reversed.

Code:

public Queue< Integer > queueReverseKNodes(Queue< Integer > queue, int k) throws Exception {	
	Deque< Integer > deque=new LinkedList<Integer>();
	int oSize=queue.size();
	for (int idx=0; idx < k;idx++) {
		deque.addLast(queue.remove());
	}
	for (int idx=0; idx < k;idx++) {
		queue.add(deque.removeLast());
	}
	for (int idx=0; idx < oSize-k;idx++) {
		queue.add(queue.remove());
	}	
	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.Queue;
import java.util.Deque;
import java.util.Iterator;
import java.util.LinkedList;


public class QueueReverseKNodes {	
	
public Queue< Integer > queueReverseKNodes(Queue< Integer > queue, int k) throws Exception {	
	Deque< Integer > deque=new LinkedList<Integer>();
	int oSize=queue.size();
	for (int idx=0; idx < k;idx++) {
		deque.addLast(queue.remove());
	}
	for (int idx=0; idx < k;idx++) {
		queue.add(deque.removeLast());
	}
	for (int idx=0; idx < oSize-k;idx++) {
		queue.add(queue.remove());
	}	
	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) {
	/*Test cases given below:*/
	try {
	Queue<Integer> queue=new LinkedList<Integer>();
	System.out.print("Add to QueueStack");
	queue.add(9);
	queue.add(14);
	queue.add(17);
	queue.add(34);
	queue.add(21);
	queue.add(28);
	printQueue(queue);
	
	QueueReverseKNodes queueReverseKNodes=new QueueReverseKNodes();
	System.out.println("Reverse 1");
	queueReverseKNodes.queueReverseKNodes(queue, 1);
	printQueue(queue);
	
	System.out.println("Reverse 3");
	queueReverseKNodes.queueReverseKNodes(queue, 3);
	printQueue(queue);
	
	System.out.println("Reverse 6");
	queueReverseKNodes.queueReverseKNodes(queue, 6);
	printQueue(queue);
	
	System.out.println("Reverse 0");
	queueReverseKNodes.queueReverseKNodes(queue, 0);
	printQueue(queue);
	
	
	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
	}
		
}
	
}