In this article, we will discuss how to reverse a Queue in different ways
Reverse a Queue :
There are different ways to reverse a queue –
- Using Recursion
- Using Java Stack class
1. Using Recursion :
- Queue interface have some useful methods to operate –
- poll() – retrieve & removes head element from Queue but returns null, if Queue is empty
- offer() – adds a specified element into Queue
- In the below illustration,
- First retrieve/remove head elements one-by-one from Queue recursively using poll() method
- Store/assign the polled elements in a temporary variable
- Then add to queue using offer() method
ReverseQueueUsingRecursion.java
package in.bench.resources.queue.reverse;
import java.util.LinkedList;
import java.util.Queue;
public class ReverseQueueUsingRecursion {
// main() method
public static void main(String[] args) {
// 1. create Queue and add elements
Queue<Integer> queue = new LinkedList<>();
// 1.1 add elements to Queue
queue.add(63);
queue.add(97);
queue.add(21);
queue.add(86);
queue.add(19);
queue.add(37);
// 1.2 print queue elements in insertion order
System.out.println("Original Queue - insertion order :- \n" + queue);
// 2. call reverse function
reverse(queue);
// 2.1 print queue elements in reverse order
System.out.print("\nReverse Queue - reverse insertion order :- \n" + queue);
}
/**
* This method reverses the Queue elements in Recursive way
*
* @param q
*/
private static void reverse(Queue<Integer> q) {
// 1. check for empty
if(q.isEmpty()) {
return;
}
// 2. retrieve & remove head element from Queue
int e = q.poll();
// 3. call function, recursively
reverse(q);
// 4. add specified element into Queue 1-by-1
q.offer(e);
}
}
Output :
Original Queue - insertion order :-
[63, 97, 21, 86, 19, 37]
Reverse Queue - reverse insertion order :-
[37, 19, 86, 21, 97, 63]
2. Using Java Stack class :
- Already in the last example, few methods of Queue interface discussed
- Here, few more methods of Queue interface are used for reversing Queue elements using Java Stack class
- remove() – retrieve & remove head element from Queue
- add() – similar to offer() method but throws IllegalStateException for space constraints
- Below methods of Java Stack are used –
- push() – add/inserts new element/object into Stack
- peek() – returns top of the Stack (just returns but doesn’t remove unlike pop() operation)
- In the below illustration,
- First, iterate through Queue elements checking whether Queue is empty
- Retrieve & remove elements one-by-one from Queue and simultaneously add to the Stack
- This will empty the Queue and simultaneously fill elements from Queue to Stack in reverse order
- Then iterate through Stack elements checking whether Stack is empty
- Retrieve elements one-by-one from Stack and simultaneously add to the Queue
- This won’t empty the Stack but fills the elements in the Queue
- Note: If the requirement is to empty the Stack then use pop() method instead of peek() method
- First, iterate through Queue elements checking whether Queue is empty
ReverseQueueUsingStack.java
package in.bench.resources.queue.reverse;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class ReverseQueueUsingStack {
// main() method
public static void main(String[] args) {
// 1. create Queue and add elements
Queue<Integer> queue = new LinkedList<>();
// 1.1 add elements to Queue
queue.add(63);
queue.add(97);
queue.add(21);
queue.add(86);
queue.add(19);
queue.add(37);
// 1.2 print queue elements in insertion order
System.out.println("Original Queue - insertion order :- \n" + queue);
// 2. call method
reverse(queue);
// 2.1 print queue elements in reverse order
System.out.print("\nReverse Queue - reverse insertion order :- \n" + queue);
}
/**
* This method reverses the Queue elements using Stack
*
* @param q
*/
private static void reverse(Queue<Integer> q) {
// 1. create temporary Stack object
Stack<Integer> stack = new Stack<Integer>();
// 2. add to Stack(LIFO) && remove from Queue(FIFO)
while(!q.isEmpty()) {
// add to Stack & remove from Queue
stack.push(q.peek());
q.remove();
}
// 3. add to Queue(FIFO) && remove from Stack(LIFO)
while(!stack.isEmpty()) {
// add from Queue & remove from Stack
q.add(stack.peek());
stack.pop();
}
}
}
Output :
Original Queue - insertion order :-
[63, 97, 21, 86, 19, 37]
Reverse Queue - reverse insertion order :-
[37, 19, 86, 21, 97, 63]
Related Articles :
References :
- https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html
- https://docs.oracle.com/javase/8/docs/api/java/util/List.html
- https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html
- https://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html
- https://docs.oracle.com/javase/8/docs/api/java/util/Vector.html
- https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html
Happy Coding !!
Happy Learning !!
