Last Updated: 13 Feb, 2021
Reversing Queue
Easy
Asked in companies
You have been given a queue of ‘N’ distinct integers. For a given queue, you need to reverse all the elements in it.
Note:
You need to reverse the string in O(N) time complexity.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain an integer ‘N’ where ‘N’ is the size of the queue.
The last line of each test case will contain the ‘N’ elements of the queue.
Output Format:
For each test case, print the elements of the reversed queue.
Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of. You just need to complete the function.
Constraints:
1 <= T <= 50
1 <= N <= 10^4
0 <= Q[i] <= 10^5
Where Q[i] denotes the value ith element of the input queue.
Time Limit: 1 sec
Approaches
- The queue data structure follows FIFO (First In First Out) order. So, we cannot reverse the queue in-place. We require the help of another data structure in order to reverse the queue.
- One of the simplest data structures which we can use is an array.
- Create an array of size equal to the number of elements in the queue.
- The idea is to fill the array from the back, instead of front.
- So, one by one remove the elements from the queue and add them to the array.
- Now, iterate over the array and push each element back to the queue.
- Here instead of explicitly creating a stack, we use the concept of recursion. -
- The idea is to remove the front element from the queue and recursively call the reverse function for the remaining queue. In this way we are dividing the larger problem into smaller sub-problems.
- The previous step is repeated until the queue becomes empty (base condition).
- Now, after returning from the recursive call. Push the element back into the queue.
- In this way, we have reversed the order of elements in the queue.
Example:
Queue: 1 2 3 4 5 6 7 8
Queue = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
reverse(1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = reverse(2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) -> 1
reverse(2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = reverse(3 -> 4 -> 5 -> 6 -> 7 -> 8) -> 2
reverse(3 -> 4 -> 5 -> 6 -> 7 -> 8) = reverse(4 -> 5 -> 6 -> 7 -> 8) -> 3
reverse(4 -> 5 -> 6 -> 7 -> 8) = reverse(5 -> 6 -> 7 -> 8) -> 4
reverse(5 -> 6 -> 7 -> 8) = reverse(6 -> 7 -> 8) -> 5
reverse(6 -> 7 -> 8) = reverse(7 -> 8) -> 6
reverse(7 -> 8) = reverse(8) -> 7
reverse(8) = reverse() -> 8
reverse() = empty queue
So,
reverse(8) = 8
reverse(7 -> 8) = 8 -> 7
reverse(6 -> 7 -> 8) = 8 -> 7 -> 6
reverse(5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5
reverse(4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4
reverse(3 -> 4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4 -> 3
reverse(2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2
reverse(1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8) = 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1
Reversed Queue: 8 7 6 5 4 3 2 1
The algorithm for the approach is as follows:
Base Case: The reverse of an empty queue is an empty queue.
- If the queue is empty, return, else pop out the first element of the queue and store it in a variable, say “curr”.
- Call the reverse method recursively on the remaining queue.
- The reverse method will reverse the remaining queue, push the “curr” element to the queue.
- The queue is reversed.
- This approach is similar to the previous approach, where we used recursion to reverse the queue.
- Here, we will explicitly create a stack.
- Stack data structure follows a LIFO (Last In First Out) order, i.e. the element which was inserted the last in the stack is the first one to pop out.
- Hence, the stack can be used to reverse the order of elements.
- The idea here is to empty all the elements of the queue into a stack.
- Now, pop the elements from the stack and insert them back into the queue.
- The queue now stores the elements in reverse order.