Problem Statement:

You are given a queue of integers and an integer k. You need to reverse the first k elements of the queue while leaving the rest of the elements in the same order.

Example:

• Input: queue = [10, 20, 30, 40, 50, 60], k = 2
• Output: queue = [20, 10, 30, 40, 50, 60]

Approach:

The approach involves using a stack to reverse the first k elements. Stacks work on a Last-In-First-Out (LIFO) basis, which is perfect for reversing the order of elements.

Step-by-Step Explanation:

1. Edge Case Handling:

   • If k is less than or equal to 0 or greater than the size of the queue, there’s nothing to reverse, so we return immediately.

2. Push First k Elements onto the Stack:

   • We pop the first k elements from the front of the queue and push them onto the stack. This will reverse their order when we pop them back into the queue.

3. Pop Elements from the Stack Back to the Queue:

   • Since stacks reverse the order, popping elements from the stack and pushing them back to the queue will reverse the first k elements.

4. Rearrange Remaining Elements:

   • After reversing the first k elements, we need to push the remaining n - k elements (where n is the size of the queue) to the back of the queue to maintain their original order.

Code Implementation : 

#include <queue>
#include <stack>
#include <iostream>
using namespace std;

// Function to reverse the first k elements of the queue
void reverseKElements(queue<int>& q, int k) {
    // Edge case: If k is not valid, return immediately
    if (k <= 0 || k > q.size()) {
        return;
    }

    stack<int> s;

    // Step 1: Push the first k elements of the queue onto the stack
    for (int i = 0; i < k; ++i) {
        int frontElement = q.front();
        q.pop();
        s.push(frontElement);
    }

    // Step 2: Pop elements from the stack back to the queue
    while (!s.empty()) {
        q.push(s.top());
        s.pop();
    }

    // Step 3: Move the remaining n-k elements from the front to the back of the queue
    int remainingElements = q.size() - k; 
   // Remaining elements after reversing the first k
    for (int i = 0; i < remainingElements; ++i) {
        int frontElement = q.front();
        q.pop();
        q.push(frontElement);
    }
}

// Helper function to print the elements of the queue
void printQueue(queue<int> q) {
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
}

int main() {
    queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);
    q.push(40);
    q.push(50);
    q.push(60);

    cout << "Original Queue: ";
    printQueue(q);

    reverseKElements(q, 2); // Reverse the first 2 elements

    cout << "Queue after reversing the first 2 elements: ";
    printQueue(q);

    return 0;
}

Detailed Explanation:

1. Edge Case Check:

   if (k <= 0 || k > q.size()) {
       return;
   }
   

   Copy

   Why this check?: If k is invalid (either k <= 0 or k is larger than the size of the queue), we don't need to reverse anything, so we return immediately.

    

2. Reversing the First k Elements:

   for (int i = 0; i < k; ++i) {
       int frontElement = q.front();
       q.pop();
       s.push(frontElement);
   }
   

   Copy
   • Step-by-Step:
     • We loop k times.
     • Each iteration, we remove the front element of the queue and push it onto the stack.
     • This means the first element of the queue becomes the last element in the stack, reversing their order.

    

3. Restoring the Reversed Elements to the Queue: 

   while (!s.empty()) {
       q.push(s.top());
       s.pop();
   }

   Copy
   • How it works: As we pop elements from the stack back into the queue, they come out in reverse order. This completes the reversal of the first k elements.

4. Rearranging Remaining Elements:

    

   int remainingElements = q.size() - k;
   // Remaining elements after reversing the first k
   for (int i = 0; i < remainingElements; ++i) {
       int frontElement = q.front();
       q.pop();
       q.push(frontElement);
   }
   

   Copy
   • Why this is necessary: After reversing the first k elements, the remaining elements in the queue (those that were not reversed) need to be shifted to the back to maintain their order.

Final Thoughts:

• Time Complexity: O(n), where n is the number of elements in the queue. Each element is enqueued and dequeued at most twice.
• Space Complexity: O(k) for the stack, where k is the number of elements to be reversed.

This approach efficiently reverses the first k elements of the queue while keeping the rest of the elements intact. It’s a simple and effective way to achieve the desired outcome.