Reversing the First K Elements of a Queue

Last Updated on October 10, 2022 by Gokul Kannan

Problem Statement:

You are given a queue of integers and an integer value K. Your task is to reverse the first K elements of the queue, leaving the rest of the elements of the queue undisturbed.

Example

Consider the queue shown below.

The above image shows the reversal of the first K elements of the queue.

Approach

We will use an auxiliary Stack to solve this problem. Let us consider an empty stack and the queue shown below.

Now, we will dequeue K elements from the queue and insert them into the stack. So, the same is shown below.

So, now the Stack and the queue look as shown below.

Now, we will pop an element from the Stack, and enqueue it into the queue. We will perform this operation until the stack becomes empty.

Now, we know that enqueuing an element in the queue happens from the rear end. So, the values that we will pop from the stack will be enqueued to the rear of the queue.

We pop 30 in the first step and enqueue it into the queue.

Next, we will pop 20 from the Stack and enqueue it into the queue.

Finally, 10 will be popped from the stack and will be inserted into the queue.

Now, the Stack is empty and we have inserted the K elements into the queue in reversed order.

However, there is still a problem. The reversed elements should be at the beginning of the queue and not at the end.

So, for that, we will dequeue an element from the queue and enqueue it back into the queue. This will be done N-K times as the starting N-K elements are the ones that need to come at the end reversed K elements.

So, we deque 40 from the queue and enqueue it into the same queue.

Next, we will deque 50 from the Stack and add it to the same queue.

Next, element 60 will be removed from the queue and will be inserted back into it.

Now, 70 will be dequeued and added to the rear of the queue.

Lastly, element 80 will be removed from the queue and inserted back into it.

So, finally, the first K elements of the queue have been reversed.

Now that we have understood the complete procedure, let us write the code for the same.

Code Implementation

#include <bits/stdc++.h>
using namespace std;


void reverseQueueFirstKElements(int k, queue<int>& Queue)
{
	if (Queue.empty() == true || k > Queue.size())
		return;
	if (k <= 0)
		return;

	stack<int> Stack;

	
	for (int i = 0; i < k; i++) {
		Stack.push(Queue.front());
		Queue.pop();
	}

	while (!Stack.empty()) {
		Queue.push(Stack.top());
		Stack.pop();
	}
	
	for (int i = 0; i < Queue.size() - k; i++) {
		Queue.push(Queue.front());
		Queue.pop();
	}
}


void Print(queue<int>& Queue)
{
	while (!Queue.empty()) {
		cout << Queue.front() << " ";
		Queue.pop();
	}
}

// Driver code
int main()
{
	queue<int> Queue;
	Queue.push(10);
	Queue.push(20);
	Queue.push(30);
	Queue.push(40);
	Queue.push(50);
	Queue.push(60);
	Queue.push(70);
	Queue.push(80);

	int k = 3;
	reverseQueueFirstKElements(k, Queue);
	Print(Queue);
}

import java.util.*;

public class Main {

	static Queue<Integer> queue;

	static void reverseQueueFirstKElements(int k)
	{
		if (queue.isEmpty() == true || k > queue.size())
			return;
		if (k <= 0)
			return;

		Stack<Integer> stack = new Stack<Integer>();

		for (int i = 0; i < k; i++) {
			stack.push(queue.peek());
			queue.remove();
		}

		while (!stack.empty()) {
			queue.add(stack.peek());
			stack.pop();
		}

		for (int i = 0; i < queue.size() - k; i++) {
			queue.add(queue.peek());
			queue.remove();
		}
	}

	static void Print()
	{
		while (!queue.isEmpty()) {
			System.out.print(queue.peek() + " ");
			queue.remove();
		}
	}

	public static void main(String args[])
	{
		queue = new LinkedList<Integer>();
		queue.add(10);
		queue.add(20);
		queue.add(30);
		queue.add(40);
		queue.add(50);
		queue.add(60);
		queue.add(70);
		queue.add(80);

		int k = 3;
		reverseQueueFirstKElements(k);
		Print();
	}
}

Time Complexity: The time complexity of the above solution is O(N) where N is the number of elements in the queue. This is because we have just removed all the N elements from the queue once and pushed them back into the queue.

Space Complexity: The space complexity of this solution is O(K). This is because we have used an auxiliary stack in which we have pushed K elements.

We tried to discuss Reversing the First K Elements of a Queue. We hope this article gives you a better understanding of Reversing the First K Elements of a Queue, PrepBytes also provides a good collection of Foundation Courses that can help you enhance your coding skills. Want to make sure you ace the interview in one go? Join our Placement Program which will help you get prepared and land your dream job at MNCs. Mentors of Prepbytes are highly experienced and can provide you with basic, in-depth subject knowledge for better understanding.