Given a queue of integers and a number k, reverse the order of the first k elements. The rest of the queue must keep its order.
DSA Animator › DSA Revision › Queue › Reversing First K Elements of a Queue
Remember: a stack reverses, a queue rotates. Reverse the first k, then rotate the rest to the back. The video solves Reversing First K Elements of a Queue (GFG, Medium) with the Queue + Stack pattern from the Queue topic, and you can replay every step in the interactive Reversing First K Elements of a Queue animation.
Given a queue of integers and a number k, reverse the order of the first k elements. The rest of the queue must keep its order.
For the queue 1, 2, 3, 4, 5 with k equal to 3, the result is 3, 2, 1, 4, 5.
A queue only lets you take from the front and add to the back. So you cannot simply reverse part of it in place.
A stack reverses order, so use one. Move the first k elements from the queue into the stack. Pop them all back into the queue, which adds them to the back in reversed order. Finally, rotate the other n minus k elements from the front to the back, so the reversed part is at the front again.
Dequeue 1, 2 and 3 into the stack. The queue holds 4 and 5. Pop 3, 2 and 1 back into the queue, giving 4, 5, 3, 2, 1. Now move 4 to the back, then 5. The queue is 3, 2, 1, 4, 5.
In code, dequeue k elements and push each one onto a stack. Then pop the stack and enqueue each element. Then dequeue and re-enqueue the first n minus k elements. Every element moves a constant number of times, so it's O of n time and O of k space.
Remember: a stack reverses, a queue rotates. Reverse the first k, then rotate the rest to the back.