Reverse the first “K” elements of a queue

Easy

0/40

Average time to solve is 20m

Contributed by

13 upvotes

Asked in companies

Problem statement

You have been given a queue and an integer ‘K’. You need to reverse the order of the first ‘K’ elements of the queue.

Note :

The relative order of other elements should be maintained.

For example :

If Q = [ 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 ]
and ‘K’ = 4 
then the output will be
Q = [ 40, 30, 20, 10, 50, 60, 70, 80, 90, 100]

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

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains an integer ‘N’ which denotes the size of the queue.

The second line of each test case contains elements of the queue. The line consists of values of elements of the queue separated by a single space.

The third line of each test case contains an integer ‘K’ which denotes the number of elements to be reversed in the queue.

Output Format:

For each test case, print a single line containing space-separated integers denoting elements of the queue after reversing the first ‘K’ elements.

The output of each test case will be printed in a separate line.

Note:

You don't need to print anything, It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 100
0 <= DATA <= 10 ^ 4
0 <= K <= N

Where ‘T’ is the number of test cases, ‘N’ is the size of the queue, “DATA” is the value of the element of the queue and ‘K’ is the number of elements to be reversed.

Time limit: 1 sec.

Sample Input 1:

1
10
10 20 30 40 50 60 70 80 90 100
4

Sample Output 1:

40 30 20 10 50 60 70 80 90 100

Sample Input 2:

1
10
10 20 30 40 50 60 70 80 90 100
3

Sample Output 2:

30 20 10 40 50 60 70 80 90 100

Hint 1

Can we use some data structure to reverse the order?

Approaches (1)

Approach 1

Brute-Force

The basic idea is to use a stack to reverse the elements of the queue.

Create an empty stack.
One by one deque the first ‘K’ elements of the queue and push the dequeued elements in the auxiliary stack.
Enqueue the elements of the stack at the back of the queue.
Dequeue the remaining (size-K) elements from the front and enqueue them one by one to the same queue (enqueue operation in queue happens from the back/rear side).

Time Complexity

O(N + K), where ‘N’ is the size of the queue and ‘K’ is the number of elements to be reversed.

The reason is, firstly the whole queue is emptied into the stack and after that first ‘K’ elements are emptied and enqueued in the same way.

Space Complexity

O(N), where ‘N’ is the size of the stack.

Stack of size ‘N’ is used to reverse the elements of the queue.

(100% EXP penalty)

Reverse the first “K” elements of a queue

Console