Problem

Submissions

Hints & solutions

Discuss

Reversing a Queue

Easy

0/40

Average time to solve is 10m

38 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

2
1
9
5
10 6 8 12 3

Sample Output 1:

9 
3 12 8 6 10

Explanation 1:

For the first test case, the queue has only one element, i.e. 9. So, even after reversing, our queue remains the same.

For the second test case, the queue has elements in the order: 10, 6, 8, 12, 3. Reversing the queue changes the order of elements to - 3, 12, 8, 6, 10.

Sample Input 2:

2
2
99 89
6
1 2 3 4 5 6

Sample Output 2:

89 99
6 5 4 3 2 1

Hint 1

Hint 2

Hint 3

Hint 4

Use another queue.

Approaches (4)

Approach 1

Approach 2

Approach 3

Approach 4

Using Another Queue

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.

Time Complexity

O(N ^ 2), where N is the number of elements in the queue.

In the worst case, we require O(N) operations for each element in the queue. Therefore, to reverse ‘N’ elements, the overall Time Complexity becomes O(N ^ 2).

Space Complexity

O(N), where N is the number of elements in the queue.

In the worst case, extra space O(N) is required by the queue. Hence, the overall Space Complexity is O(N).

(100% EXP penalty)

Reversing a Queue

Console