Last Updated: 19 Dec, 2020
Reverse First K elements of Queue
Easy
Asked in companies
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.
Note:
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?
Constraints:
1 <= T <= 10
1 <= N <= 10 ^ 5
0 <= K <= N
-10 ^ 9 <= queue elements <= 10 ^ 9
Time limit: 1 sec
Approaches
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.
Another approach can be using a stack to reverse the elements.
- Store the first K elements of the queue into a stack.
- Push all elements of the stack into the queue.
- Pop and push continuously N-K elements in the queue.
The algorithm is as follows:
- Initialize N = Queue.size
- Create a stack S.
- Loop: for( i = 0; i < K; i++ ):
- Push front of Queue to stack S.
- Pop first element of Queue.
- Loop: while(S.size > 0)
- Queue.push( S.top )
- Pop element from stack S.
- Loop for( i = 0; i < N - K; i++ ): push and pop N - K times.
- Queue.push( Queue.front )
- Queue.pop
- Return Queue.
Let’s take an example where the queue is { 1, 2, 3, 4 } and K be 2
We will create an empty stack { } and push K elements from the front of the queue to stack.
- Pop 1 from the queue and push in the stack.
- Stack: { 1 }.
- Queue: { 2, 3, 4 }
- Pop 2 from the queue and push in the stack.
- Stack: { 1, 2 }
- Queue: { 3, 4 }
Now, we push stack elements in the queue
- Pop 2 from the stack and push in the queue.
- Stack: { 1 }
- Queue: { 3, 4, 2 }
- Pop 1 from the stack and push in the queue.
- Stack: { }
- Queue: { 3, 4, 2, 1 }
Now push and pop 2(N - K) elements from the queue.
- Push and pop 3 in the queue.
- Queue: { 4, 2, 1, 3 }
- Push and pop4 in the queue.
- Queue: { 2, 1, 3, 4 }