Reverse first ‘K’ items in a Queue in C++

Welcome to this tutorial where you are going to learn “How to reverse first ‘K’ items in a Queue in C++”. So without wasting any time let’s begin this tutorial with a quick revision of  “Queue” in C++.

  • So Queue is a linear structure of data where items can be inserted and deleted in the FIFO fashion. Here the term FIFO stands for First IFirst Out.
  • In other words, we can say that the first element to be inserted in a queue will be the first element to be deleted from the queue.
  • In a queue, we can only insert elements from the rear end of the queue. On the other hand, deletions will only take place from the front of the queue.

Now let’s understand how our program should work with an example,

Reverse first 'K' items in a Queue in C++

(Click on the above link for viewing the example)

  • Now you should have understood what we are trying to achieve. So before discussing the approach for this problem, I request you to write a scratch code on a paper.

 

Approach for the above problem

  • Let’s now talk about the solution to the problem. Since we need to reverse 1st ‘K’ items we are going to use a “Stack” of size ‘K’.
  • Then we will push first ‘K’ items of the queue into the stack. At this point, the queue will contain the remaining elements.
  • Now if we try to pop these ‘K’ items from the stack we will get the elements in reverse order than they are inserted.
  • So we will pop the ‘K’ items from the stack and insert it into the queue. Finally, we need to rearrange the queue by deleting “N-K” elements from the queue and inserting it again in the queue. (where ‘N’ is the size of the queue)

Click on the link below to understand the approach diagrammatically,

Reverse first 'K' items in a Queue in C++

Now let’s move towards the actual code for this problem…

C++ Program for reversing first ‘K’ elements of a Queue

// C++ program to reverse
// first 'K' items of a Queue

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

void reverse_Que(queue<int>* Q , int k)
{
  // If any of these conditions is true then return
  if(Q->empty() == true || k > Q->size() || k <= 0)
    return;

  stack<int> st;	//Stack container for storing first 'K' items

  // Push first 'K' into the stack and pop from queue
  for(int i=0 ; i<k ; i++)
    st.push(Q->front()),
    Q->pop();

  // Now pop all items of stack and push it into the queue
  while(!st.empty())
    Q->push(st.top()),
    st.pop();

  // Finally, rearrange the queue by
  // pushing "N-K" elements into the queue
  // and simultaneously pop from the front of queue
  for(int j=0 ; j<(Q->size()-k) ; j++)
    Q->push(Q->front()),
      Q->pop();
}

int main(void) 
{ 
  queue<int> Q;
  int K = 3;	// Reverse the first 3 elements of the queue 'Q'

  // Insert the elements of queue
  Q.push(1);
  Q.push(2);
  Q.push(3);
  Q.push(40);
  Q.push(50);

  // Call the function reverse_Que
  // with parameters as reference of queue 'Q'
  // and integer value 'K'
  reverse_Que(&Q , K);
  cout<<"Q = { ";

  // Display the updated queue 'Q'
  while(!Q.empty())
   cout<<Q.front()<<"  ",
   Q.pop();
  
  cout<<"}";

return 0; 
}

So the output that you will get after running the above program is,

Q = { 3 2 1 40 50 }

So that’s all for this tutorial. I hope you have understood the approach and program for this problem.

Thanks for going through this tutorial.

Comment down for any queries.

Also read: Reverse a string using stack in C++

Leave a Reply

Your email address will not be published. Required fields are marked *