Reverse first k elements of queue

The problem addressed in this code is the reversal of the first k elements of a queue using C++. A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, where elements are added at the rear and removed from the front.

Problem Statement

The task is to reverse the order of the first k elements in a queue without changing the order of the remaining elements. This operation is essential in scenarios where you need to process the initial k elements in reverse order while keeping the rest of the elements unchanged.

Explanation with an Example

Imagine you are at a bookstore, and you have a queue of books that you want to read. The queue represents the order in which you plan to read the books. However, you decide that you want to read the first few books in reverse order before continuing with the rest of the queue. This scenario can be modeled using this problem.

Idea to Solve

To solve this problem, we use a stack to temporarily store the first k elements from the queue. We then pop elements from the stack and enqueue them back into the queue to reverse the order of the initial k elements. Finally, we enqueue the remaining elements back into the queue after the reversed portion.

Pseudocode

reverseElement(q, k):
    Create an empty stack `s`
    Initialize a counter `counter` to 0
    Loop while `counter` is less than `k` and queue is not empty:
        Push front element of queue `q` to stack `s`
        Pop front element from queue `q`
        Increment `counter`

    Loop while stack `s` is not empty:
        Push top element of stack `s` to queue `q`
        Pop top element from stack `s`

    Initialize `counter` back to 0
    Loop while `counter` is less than `n - k` and queue is not empty:
        Push front element of queue `q` to queue `q`
        Pop front element from queue `q`
        Increment `counter`

printQueue(q):
    Loop while queue `q` is not empty:
        Print front element of queue `q`
        Pop front element from queue `q`

Main:
    Initialize a queue `q`
    Enqueue elements into queue `q`
    Print the initial queue
    Initialize `k` as the number of elements to reverse
    Call `reverseElement` to reverse the first `k` elements
    Print the modified queue

Algorithm Explanation

1. Initialize an empty stack s.
2. Iterate through the first k elements of the queue, pushing them onto the stack and popping them from the queue.
3. Pop elements from the stack and enqueue them back into the queue to reverse the order of the initial k elements.
4. Iterate through the remaining elements of the queue and enqueue them back into the queue.
5. Print the queue using the printQueue function.

Code Solution

• C++
• Java
• C#
• Python
• Ruby

/*
    C++ program 
    Reverse first k elements of queue
*/
#include <iostream>
#include <stack>
#include <queue>

using namespace std;
// Handles the request to reverse initial k elements
void reverseElement(queue <int> &q, int k)
{
    if (q.size() < k || q.empty())
    {
        return;
    }
    // Create an stack
    stack < int > s;
    int n = q.size();
    int counter = 0;
    // Add initial k queue element into stack
    while (counter < k)
    {
        s.push(q.front());
        // Remove a front node of queue
        q.pop();
        counter++;
    }
    // Add inserting stack element back to queue
    while (!s.empty())
    {
        q.push(s.top());
        s.pop();
    }
    counter = 0;
    // Reverse inital  n - k queue element
    while (counter < n - k)
    {
        q.push(q.front());
        q.pop();
        counter++;
    }
}
// Handles the request of printing queue elements
void printQueue(queue <int> q)
{
    // Display Queue element
    while (!q.empty())
    {
        cout <<"  "<< q.front() ;
        q.pop();
    }
}
int main(int argc, char const *argv[])
{
    queue < int > q;
    // Add element into queue
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);
    q.push(5);
    q.push(6);
    q.push(7);
    cout << "\n Before Reverse "<< endl;
    printQueue(q);
    int k = 3;
    // Reverse the initially k element
    reverseElement(q, k);
    cout << "\n After Reverse initial " << k << " Element" <<endl;
    printQueue(q);
    return 0;
}

 Before Reverse
  1  2  3  4  5  6  7
 After Reverse initial 3 Element
  3  2  1  4  5  6  7

/*
    Java Program 
    Reverse first k elements of queue
*/
import java.util.Queue;
import java.util.Stack;
import java.util.LinkedList;
public class Reverse
{
	// Handles the request to reverse initial k elements
	public void reverseElement(Queue <Integer> q, int k)
	{
		if (q.size() < k || q.isEmpty())
		{
			return;
		}
		// Create an stack
		Stack <Integer> s = new Stack <Integer> ();
		// Get number of element in queue
		int n = q.size();
		int counter = 0;
		// Add initial k queue element into stack
		while (counter < k)
		{
			s.push(q.peek());
			// Remove a front node of queue
			q.remove();
			counter++;
		}
		// Add inserting stack element back to queue
		while (!s.empty())
		{
			q.add(s.peek());
			s.pop();
		}
		counter = 0;
		// Reverse inital  n - k queue element
		while (counter < n - k)
		{
			q.add(q.peek());
			q.remove();
			counter++;
		}
	}
	// Handles the request of printing queue elements
	public void printQueue(Queue <Integer> q)
	{
		for (Integer item: q)
		{
			System.out.print("  " + item);
		}
	}
	public static void main(String[] args)
	{
		Reverse task = new Reverse();
		Queue <Integer> q = new LinkedList<Integer> ();
		q.add(1);
		q.add(2);
		q.add(3);
		q.add(4);
		q.add(5);
		q.add(6);
		q.add(7);
		System.out.println("\n Before Reverse ");
		task.printQueue(q);
		int k = 3;
		task.reverseElement(q, k);
		System.out.println("\n After Reverse intial " + k);
		task.printQueue(q);
	}
}

 Before Reverse
  1  2  3  4  5  6  7
 After Reverse intial 3
  3  2  1  4  5  6  7

/*
    C# Program 
    Reverse first k elements of queue
*/
// Include namespace system
using System;
using System.Collections;
public class Reverse
{
	public static Queue q = new Queue();
	// Handles the request to reverse initial k elements
	public void reverseElement(int k)
	{
		if (q.Count < k || q.Count == 0)
		{
			return;
		}
		// Create an stack
		Stack s = new Stack();
		// Get number of element in queue
		int n = q.Count;
		int counter = 0;
		// Add initial k queue element into stack
		while (counter < k)
		{
			s.Push(q.Peek());
			// Remove a front node of queue
			q.Dequeue();
			counter++;
		}
		// Add inserting stack element back to queue
		while (s.Count > 0)
		{
			q.Enqueue(s.Peek());
			s.Pop();
		}
		counter = 0;
		// Reverse inital  n - k queue element
		while (counter < n - k)
		{
			q.Enqueue(q.Peek());
			q.Dequeue();
			counter++;
		}
	}
	// Handles the request of printing queue elements
	public void printQueue()
	{
		foreach(var item in q)
		{
			Console.Write("  {0}", item);
		}
	}
	public static void Main(String[] args)
	{
		Reverse task = new Reverse();
		q.Enqueue(1);
		q.Enqueue(2);
		q.Enqueue(3);
		q.Enqueue(4);
		q.Enqueue(5);
		q.Enqueue(6);
		q.Enqueue(7);
		Console.WriteLine("\n Before Reverse ");
		task.printQueue();
		int k = 3;
		task.reverseElement(k);
		Console.WriteLine("\n After Reverse intial " + k);
		task.printQueue();
	}
}

 Before Reverse
  1  2  3  4  5  6  7
 After Reverse intial 3
  3  2  1  4  5  6  7

# Python 3 program
# Reverse first k elements of queue

from queue import Queue 

class Reverse :
    #  Handles the request to reverse initial k elements
    def reverseElement(self, q, k) :
        if (q.qsize() < k or q.empty()) :
            return
        
        #  Create an list
        s = []
        #  Get number of element in queue
        n = q.qsize()
        counter = 0
        #  Add initial k queue element into list
        while (counter < k) :
            s.append(q.get())
            #  Remove a front node of queue
            counter += 1
        
        #  Add inserting list element back to queue
        while (len(s)>0) :
            q.put(s.pop())
      
        
        counter = 0

        #  Reverse inital  n - k queue element
        while (counter < n - k) :
            q.put(q.get())
            
            counter += 1
        
    
    #  Handles the request of printing queue elements
    def printQueue(self, q) :
        n = q.qsize()
        for x in range(0,n):
            print("",q.queue[x],end="")
        

def main() :
    task = Reverse() 
    q = Queue()
    q.put(1)
    q.put(2)
    q.put(3)
    q.put(4)
    q.put(5)
    q.put(6)
    q.put(7)
    print("\n Before Reverse ")
    task.printQueue(q)
    k = 3
    task.reverseElement(q, k)
    print("\n After Reverse intial", k,"element")
    task.printQueue(q)

if __name__ == "__main__": main()

 Before Reverse
 1 2 3 4 5 6 7
 After Reverse intial 3 element
 3 2 1 4 5 6 7

#  Ruby program
#  Reverse first k elements of queue

class Reverse 
    #  Handles the request to reverse initial k elements
    def reverseElement(q, k) 
        if (q.length < k || q.length == 0 || k < 0) 
            return 
        end
        #  Create an array
        s = []
        #  Get number of element in q
        n = q.length
        counter = 0
        #  Add initial k (q) element into s
        while (counter < k) 
            s << (q.at(0))
            #  Remove a front node of q
            q.delete_at(0)
            counter += 1
        end
       
        #  Add inserting s element back to q
        while (s.length > 0) 
            q.insert(0,s.at(0))
            s.delete_at(0)
        end
    end

    #  Handles the request of printing queue elements
    def printQueue(q)
        i = 0 
        while (i < q.length) 
            print("  ", q.at(i))
            i = i + 1
        end
    end

end

def main() 
    task = Reverse.new() 
    q = []
    q << 1
    q << 2
    q << 3
    q << 4
    q << 5
    q << 6
    q << 7
    print("\n Before Reverse \n")
    task.printQueue(q)
    k = 3
    task.reverseElement(q, k)
    print("\n After Reverse intial ", k,"\n")
    task.printQueue(q)
end

main()

 Before Reverse 
  1  2  3  4  5  6  7
 After Reverse intial 3
  3  2  1  4  5  6  7

Resultant Output Explanation

Initially, the queue contains elements from 1 to 7. After reversing the first 3 elements (1, 2, and 3), the queue is modified to have the order 3, 2, 1, 4, 5, 6, 7.

Time Complexity

1. Reverse Element Operation: O(k) - Reversing the first k elements using the stack.
2. Enqueue and Dequeue Operations: O(n) - Iterating through the entire queue.
3. Printing Queue: O(n) - Printing all elements in the queue.

The overall time complexity of this solution is O(n), where n is the total number of elements in the queue. The algorithm efficiently reverses the first k elements of the queue while maintaining the order of the rest of the elements.