Reversing first k elements Queue

Problem Statement:

Given a queue, we have to reverse the first k elements which are present in it.

What is Queue?

A Queue is a linear data structure. Queue follows the FIFO rule i.e. First in First out. In other words we can say the element that goes in first is the element that comes out first.
For Example A ticket Queue outside a cinema hall where the person enters the queue first will get the ticket first.

Basic Operations of Queue:

  • Enqueue: This operation is used to Insert an element at the end of the queue.
  • Dequeue: This operation is used to remove and return an element from the front of the queue.
  • isEmpty(): This operation is used to check whether the queue is empty or not.
  • isFull(): This operation is used to check whether the queue is full or not.
  • Peek(): This operation is used to get the value of the element from the front of the queue.

Example for reversing the first k elements of the queue:
Input: Q = [5, 10, 15, 20, 25]
K = 3
Output: [15, 10, 5, 20, 25]

How to reverse the first k elements of the queue?

For reversing the first k elements of the queue, we will use an auxiliary stack for it. Firstly, we will start a for loop for k number of times. In the loop, remove the first element from the queue and push it in the stack. After pushing k elements in the stack, now pop the top element from the stack and enqueue that element in the queue on the rear end. After insertion of k elements in the queue, now start a for loop for n – k times, and in that loop dequeue the element from the front and and then enqueue that element back in the queue from the rear end. After all, the final queue will be our result.

Algorithm:

  1. Create an empty stack.
  2. Dequeue the k elements from the queue and push the dequeued element into the stack.
  3. Now, pop the top element from the stack and enqueue it in the queue on the rear end.
  4. Atlast, dequeue (n – k) elements from the front end of the queue and enqueue them back on the rear end.
#include <bits/stdc++.h>
using namespace std;

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

  stack<int> Stack;

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

  while (!Stack.empty()) {
    Queue.push(Stack.top());
    Stack.pop();
  }

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

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

int main()
{
  queue<int> Queue;
  Queue.push(5);
  Queue.push(10);
  Queue.push(15);
  Queue.push(20);
  Queue.push(25);
  
  int k = 3;
  reverseQueueFirstKElements(k, Queue);
  Print(Queue);
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

class Reverse_k_element_queue {
 
 static Queue<Integer> queue;
 static void reverseQueueFirstKElements(int k)
  {
    if (queue.isEmpty() == true
      || k > queue.size())
      return;
    if (k <= 0)
      return;

    Stack<Integer> stack = new Stack<Integer>();

    for (int i = 0; i < k; i++) {
      stack.push(queue.peek());
      queue.remove();
    }

    while (!stack.empty()) {
      queue.add(stack.peek());
      stack.pop();
    }

    for (int i = 0; i < queue.size() - k; i++) {
      queue.add(queue.peek());
      queue.remove();
    }
  }

  static void Print()
  {
    while (!queue.isEmpty()) {
      System.out.print(queue.peek() + " ");
      queue.remove();
    }
  }

  public static void main(String args[])
  {
    queue = new LinkedList<Integer>();
    queue.add(5);
    queue.add(10);
    queue.add(15);
    queue.add(20);
    queue.add(25);
    
    int k = 3;
    reverseQueueFirstKElements(k);
    Print();
  }
}
from queue import Queue

def reverseQueueFirstKElements(k, Queue):
  if (Queue.empty() == True or
      k > Queue.qsize()):
    return
  if (k <= 0):
    return

  Stack = []

  for i in range(k):
    Stack.append(Queue.queue[0])
    Queue.get()

  while (len(Stack) != 0 ):
    Queue.put(Stack[-1])
    Stack.pop()

  for i in range(Queue.qsize() - k):
    Queue.put(Queue.queue[0])
    Queue.get()

def Print(Queue):
  while (not Queue.empty()):
    print(Queue.queue[0], end =" ")
    Queue.get()

if __name__ == '__main__':
  Queue = Queue()
  Queue.put(5)
  Queue.put(10)
  Queue.put(15)
  Queue.put(20)
  Queue.put(25)

  k = 3
  reverseQueueFirstKElements(k, Queue)
  Print(Queue)

Complexity Analysis:

Time complexity: The time complexity of reversing the first k elements of the queue will be O(n + k) where n is the number of elements in the queue and k is the number of elements which is to be reversed from the front end of the queue.
Space complexity: The space complexity will be O(n).

This article tried to discuss the concept of Reversing first k elements Queue. Hope this blog helps you understand the concept. To practice problems you can check out MYCODE | Competitive Programming at Prepbytes

Leave a Reply

Your email address will not be published. Required fields are marked *