Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Reversing First K Elements Queue

Last Updated on May 11, 2023 by Prepbytes

Reverse the first k elements in the queue is a common problem in data structures and algorithms. A queue is a data structure that follows the FIFO (First In First Out) principle. In a queue, elements are inserted from one end called the "rear" and removed from the other end called the "front". So, reversing the first K elements of a queue means that we need to dequeue the first K elements from the front of the queue, reverse them, and then enqueue them back to the front of the queue.

Reversing First K Elements Queue

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

What is Queue?

Linear data structures include queues. First in, First out, or FIFO, applies to the queue. The element that goes in first is the element that comes out first, in other words.

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 to Reverse the K Elements of Queue

  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.

Code Implementation to Reverse the K Elements of Queue

#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).

Conclusion
Reverse the first k elements in the queue is an important problem in computer science and has practical applications in various domains. It can be used to reorder the elements in a queue, ensuring that the most recently accessed elements are kept at the front for faster retrieval. This problem can be solved using various algorithms, such as by using a stack to reverse the elements, or by using recursion. Efficiently solving this problem requires a good understanding of the underlying data structures and algorithms. Overall, this problem serves as a good exercise in data structure manipulation and can help improve algorithmic thinking skills.

Frequently Asked Questions

Q1. What is the time complexity of reversing the first K elements of a queue?
Ans. The time complexity of reversing the first K elements of a queue is O(K), as we need to dequeue the first K elements and then enqueue them back to the front of the queue after reversing them.

Q2. Can we solve this problem without using a stack?
Ans. Yes, we can solve this problem without using a stack. One way to do this is by using recursion, where we dequeue the first element, recursively reverse the remaining elements, and then enqueue the first element to the end of the reversed elements.

Q3. What is the space complexity of reversing the first K elements of a queue?
Ans. The space complexity of reversing the first K elements of a queue depends on the implementation. If we use a stack, the space complexity would be O(K), as we need to store the first K elements in the stack. If we use recursion, the space complexity would be O(K) as well, as we need to store K stack frames.

Q4. What are the practical applications of reversing the first K elements of a queue?
Ans. Reversing the first K elements of a queue can be used in various applications such as web caching, job scheduling, and data stream processing. It can also be used to reorder elements in a queue according to some criteria.

Q5. Is it possible to reverse a queue in place?
Ans. No, it is not possible to reverse a queue in place, as we need to dequeue the elements to reverse them, which changes the original queue. We can only create a new queue to store the reversed elements and then enqueue them back to the original queue.

Leave a Reply

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