Last Updated: 21 Dec, 2020
Reversing a Queue
Easy
Asked in companies
You are given a queue of 'N' elements. Your task is to reverse the order of elements present in the queue.
You can only use the standard operations of the QUEUE STL.
1. enqueue(x): Add an item x to the rear of the queue.
2. dequeue(): Removes an item from the front of the queue.
3. size(): Returns the number of elements in the queue.
4. front(): Finds front element.
5. empty(): Checks whether the queue is empty or not.
Input format:
The very first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of every test case contains an integer ‘N’ denoting the number of elements present in the queue.
The second line of every test case contains ‘N’ space-separated integers denoting the elements present in the queue.
Output format:
For each test case, print space-separated integers denoting the elements in the queue in the reverse order.
Print the output of each test case in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 3000
-10 ^ 5 <= Queue[i] <= 10 ^ 5
Time Limit: 1 sec
Approaches
- The idea is to use another queue to solve this problem. This queue will be used to store the final result.
- So, create an empty queue, say result.
- Now, remove the top element from the given queue.
- Each time you remove an element, push it back to the same queue.
- After repeating the previous two steps N-1 times (where N is the size of the queue). The last element of the (given) queue will reach the front of the queue.
- Dequeue the front element and enqueue it to result .
- The size of the given queue has now decreased by one and the size of the result queue has increased by one.
- Repeat the steps until the (given) queue becomes empty.
- The result queue holds the final answer.
- 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 dequeue 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 where the OS has to maintain the stack.
- The idea is to dequeue 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.
The algorithm for the approach is as follows:
- Base Case: If Queue is empty, return the queue.
- Dequeue the front element and store it in a variable, say E.
- Recursively call the reverse function.
- Enqueue E back to the queue.
- Return the queue.
- 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, 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.