Reverse First K elements of Queue in Java
In this tutorial, we are going to know about reversing the first K elements of queue in Java. The objective is to reverse the order of the first k elements in a queue of integers, leaving the remaining elements in the same relative order, given an integer k and the queue of integers.
Examples:
Example 1:
Input: {6, 7, 8, 9, 10} and K = 3
Output: {8, 7, 6, 9, 10}
Explanation: Given a queue and a K value. Reverse the first K = 3 elements, those are 6, 7 and 8. Do not change the remaining elements and the output will be {8, 7, 6, 9, 10}.
Example 2:
Input: {10, 20, 30, 40, 50, 60} and K = 4
Output: {40, 30, 20, 10, 50, 60}
Explanation: Given a queue and a K value. Reverse the first K = 4 elements, those are 10, 20, 30 and 40. Do not change the remaining elements and the output will be {40, 30, 20, 10, 50, 60}.
Approach 1: Using recursive reversal of first k elements in a queue
ALGORITHM:
Step 1: Reverse the initial K elements.
Step 2: Take out of the front and put in the back (N–K) elements.
Filename: ReverseQueue.java
import java.io.*; import java.util.*; public class ReverseQueue { // The function to reverse a queue's first k entries. static QueuereverseFirstK(Queue queue, int k) { reverse(queue, k); int remainingSize = queue.size() - k; while( remainingSize-- > 0) { int element = queue.poll(); queue.add(element); } return queue; } static void reverse(Queue queue, int k) { if(k == 0) return; int frontElement = queue.poll(); reverse(queue, k - 1); queue.add(frontElement); } public static void main (String[] args) { Queue queue = new LinkedList (); queue.add(100); queue.add(200); queue.add(300); queue.add(400); queue.add(500); queue.add(600); queue.add(700); queue.add(800); queue.add(900); queue.add(1000); int k = 5; queue = reverseFirstK(queue, k); // queue for printing while (!queue.isEmpty()) { System.out.print(queue.poll() + " "); } } }
Output:
500 400 300 200 100 600 700 800 900 1000
Complexity analysis:
Time complexity: The time complexity of the function reverseFirstK is O(n).
Space complexity: The space complexity of the function reverseFirstK is O(n).
Approach 2: Using Queue Reversal with Stack
ALGORITHM:
Step 1: Make an empty stack.
Step 2: Dequeue the first K items from the provided queue one at a time, then push the dequeued items into a stack.
Step 3: Put the items from the stack at the back of the queue in order.
Step 4: Enqueue each element one at a time into the same queue after dequeuing (size-k) entries from the front.
Filename: Reverse_first_k_elements.java
import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class Reverse_first_k_elements { static Queuequeue; // Reverse the first K elements in the queue using this function. static void reverseQueueFirstKElements(int k) { if (queue.isEmpty() == true || k > queue.size()) return; if (k <= 0) return; Stack stack = new Stack (); // Place the initial K elements in a stack. for (int i = 0; i < k; i++) { stack.push(queue.peek()); queue.remove(); } // Put the items on the stack toward the rear of the queue. while (!stack.empty()) { queue.add(stack.peek()); stack.pop(); } // After removing the last few elements, add them to the end of the queue. for (int i = 0; i < queue.size() - k; i++) { queue.add(queue.peek()); queue.remove(); } } // Useful feature to display the queue static void printQueue() { while (!queue.isEmpty()) { System.out.print(queue.peek() + " "); queue.remove(); } } public static void main(String args[]) { queue = new LinkedList (); queue.add(100); queue.add(200); queue.add(300); queue.add(400); queue.add(500); queue.add(600); queue.add(700); queue.add(800); queue.add(900); queue.add(1000); int k = 4; reverseQueueFirstKElements(k); printQueue(); } }
Output:
400 300 200 100 500 600 700 800 900 1000
Complexity analysis:
Time complexity: The time complexity of the program is O(N + K).
Space complexity: The space complexity of the program is O(k).
Approach 3: Using double ended queue
ALGORITHM:
Step 1: Use the push_front() function to dequeue and push the front k elements of the queue onto a deque.
Step 2: Use the pop_front() method to remove each element from the deque one at a time, while the push() function is used to re-enqueue the elements into the queue.
Step 3: Use Push() and pop() to dequeue the last few elements from the queue and re-enqueue them.
Filename: ReverseFirstKElement.java
import java.util.*; public class ReverseFirstKElement { // Function to reverse first k elements of the queue public static void reverseFirstK(Queuequeue, int k) { Deque dequeue = new ArrayDeque<>(); // Dequeue the first k elements of the queue and // push them onto a deque for (int i = 0; i < k; i++) { dequeue.push(queue.poll()); } // Pop the elements from the deque and enqueue them // back into the queue while (!dequeue.isEmpty()) { queue.add(dequeue.pop()); } // Dequeue the remaining elements from the queue and // enqueue them back into the queue for (int i = 0; i < queue.size() - k; i++) { queue.add(queue.poll()); } } public static void main(String[] args){ Queue queue = new LinkedList (); queue.add(1); queue.add(2); queue.add(3); queue.add(4); queue.add(5); queue.add(6); queue.add(7); queue.add(8); queue.add(9); queue.add(10); int k = 5; // function call. reverseFirstK(queue, k); while (!queue.isEmpty()) { System.out.print(queue.peek() + " "); queue.poll(); } } }
Output:
5 4 3 2 1 6 7 8 9 10
Complexity analysis:
Time complexity: The time complexity of the program is O(n).
Space complexity: The space complexity of the program is O(k).