Reverse First K elements of Queue

Posted: 19 Dec, 2020
Difficulty: Easy


Try Problem

You are given a QUEUE containing ‘N’ integers and an integer ‘K’. You need to reverse the order of the first ‘K’ elements of the queue, leaving the other elements in the same relative order.

You can only use the standard operations of the QUEUE STL:

1. enqueue(x) : Adds an item x to rear of the queue
2. dequeue() : Removes an item from front of the queue
3. size() : Returns number of elements in the queue.
4. front() : Finds the front element.
For Example:
Let the given queue be { 1, 2, 3, 4, 5 } and K be 3.
You need to reverse the first K integers of Queue which are 1, 2, and 3.
Thus, the final response will be { 3, 2, 1, 4, 5 }.
Input format:
The first line of input contains an integer ‘T’ denoting the number of queries or test cases. 

The first line of each input consists of 2 space-separated integers ‘N’ and ‘K’ denoting the size of the queue and the number of elements to be reversed from the front.

The second line of each input consists of ‘N’ space-separated integers denoting the elements of the queue.
Output format:
For each test case, print the elements of the queue after reversing the order of first ‘K’ elements in a separate line.
You do not need to print anything, it has already been taken care of. Just implement the given function.
Follow Up
Can you solve this without using arrays?
1 <= T <= 10
1 <= N <= 10 ^ 5
0 <= K <= N
-10 ^ 9 <= queue elements <= 10 ^ 9

  Time limit: 1 sec
Approach 1

The very first approach can be to use an array to reverse the elements.

What needs to be done is: 

  • Store all the elements of the queue in an array.
  • Reverse first K elements of the array.
  • Push all elements of the array into the queue.

The algorithm is as follows:

  • Initialize N = Queue.size
  • Create an array ARR of size equal to the size of the queue.
  • Loop for( i = 0 to N ):
    • ARR[ i ] = Queue.front()
    • Q.pop()
  • reverse(ARR, ARR + K)
  • Loop for( i = 0 to N )
    • Queue.push( ARR[ i ] )
  • Return Queue.
Try Problem