Stack: Reversing the first K elements of a Queue

Problem Statement:

You are given a queue and integer k.

Your task is to reverse the order of the first k element of the queue.

Leaving the other elements in the same relative order.

Example:

Input: q = 1 2 3 4 5, k = 3

Output: 3 2 1 4 5

Solution:

We use a temp stack.

Remove the first k elements from the queue and push the elements into the stack.

Then pop the elements from the stack and add them into the queue.

Then remove the remaining n-k elements from the queue and add them back again

Time Complexity: O(n+k)
Space Complexity: O(k)

Code Solution

#include <iostream> 
#include <stack> 
#include <queue> 

using namespace std;


void solution(queue<int>& q, int k)
{
    if (q.empty() == true || k > q.size())
        return;

    if (k <= 0)
        return;

    stack<int> s;

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

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

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

void print(queue<int>& q)
{
    while (!q.empty()) 
    {
        cout << q.front() << " ";
        q.pop();
    }
}

int main()
{
    queue<int> q;
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
    

    int k = 3;
    solution(q, k);
    print(q);
}

Output

3 2 1 4 5