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
- Initialize an empty stack
s
. - Iterate through the first
k
elements of the queue, pushing them onto the stack and popping them from the queue. - Pop elements from the stack and enqueue them back into the queue to reverse the order of the initial
k
elements. - Iterate through the remaining elements of the queue and enqueue them back into the queue.
- Print the queue using the
printQueue
function.
Code Solution
/*
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;
}
Output
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);
}
}
Output
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();
}
}
Output
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()
Output
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()
Output
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
- Reverse Element Operation: O(k) - Reversing the first
k
elements using the stack. - Enqueue and Dequeue Operations: O(n) - Iterating through the entire queue.
- 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.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment