Problem

Submissions

Hints & solutions

Discuss

Reversing Queue

Easy

0/40

Average time to solve is 15m

Contributed by

23 upvotes

Asked in companies

Problem statement

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.

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

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

Sample Input 1:

Sample Output 1:

1 3 2
3 2 9 8 6

Explanation For Sample Input 1:

In the first test case, after reversing the queue, the resultant elements of the reversed queue will be 1 3 2.

In the second test case, after reversing the queue, the resultant elements of the reversed queue will be 3 2 9 8 6.

Sample Input 2:

2
7
6 8 9 11 15 2 3
4
1 2 3 4

Sample Output 2:

3 2 15 11 9 8 6
4 3 2 1

Explanation For Sample Input 2:

In the first test case, after reversing the queue, the resultant elements of the reversed queue will be 3 2 15 11 9 8 6.

In the second test case, after reversing the queue, the resultant elements of the reversed queue will be 4 3 2 1.

Hint 1

Hint 2

Hint 3

Can you think about using an array

Approaches (3)

Approach 1

Approach 2

Approach 3

Using Array

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.

Time Complexity

O(N), where N is the size of the queue.

In the worst case, we require ‘N’ enqueue and ‘N’ dequeue operations. So, the overall time complexity is O(N).

Space Complexity

O(N), where N is the size of the queue.

Extra space is required by the array to store the elements of the queue.

(100% EXP penalty)

Reversing Queue

Console