Suppose you are arranging your bookshelf, and you need to reverse the order in which the books are kept. How would you do it? You would pick the books off the shelf individually and place them onto a stack on the floor. Then, from the beginning of the stack of books, you would start placing them back on the shelf, which would give you a reversed order. We do something similar while trying to Reverse first k elements of a queue while programming. In this Blog, we will explore how to reverse the first k elements of a queue using different programs.
If we are given an integer k, and a queue consisting of integers, we need to reverse the order of the first k elements in the queue such that the elements after the kth element are undisturbed, and the first k elements are now in the reverse order of their original positions in the queue.
What is Queue?
A queue is a data structure that follows the FIFO principle, First in, First out, which means that the queue stores elements in the order in which they are added to it. The element that goes in first is the element that comes out first, in other words.
Basic Operations of Queue:
Enqueue:
This operation adds a new element to the back of the queue.
Dequeue:
This operation removes the element at the front of the queue.
isEmpty():
This operation returns True if the queue has no elements, and false if it has even one or more elements in it.
isFull():
This operation returns True if the queue is full (if the queue has a fixed size), otherwise it returns false.
Peek():
This operation returns the element at the front of the queue without removing it from the queue.
How to Reverse the First K Elements of the Queue?
Now that you understand what a queue is and how it operates on the FIFO principle, let’s come to the most important question, what can we do in order to reverse the order of first k elements of a queue?
We use a data structure called ‘stack’, which follows the LIFO (Last In First Out) principle. This works exactly in the way we place our books on the stack; the last book placed on the stack is at the top, whereas the first one is at the bottom of the stack. Hence the first k elements of our queue also get reversed when we use a stack and place them into the stack in the determined order.
But what if we only need to reverse the order of the first k elements, and not all of the elements in our queue? Here, k refers to an integer that refers to the number of elements we want. Let’s say we have the colours of the rainbow - VIBGYOR.
If we want to reverse the order of say, only the first 4 colours, we put only the first 4 colours into the stack, and then place them back in the rainbow, one by one. Thus we get the result in the image.
Similarly, we can reverse the order of any given number of elements, k, in our queue (provided that k is not larger than the number of elements present in the queue.).
Let’s consider the algorithm for reversing the first k elements of a queue.
Assume a queue, [10,20,30,40,50], and k=3.
We perform this using the stack and queue data structures available. Programming languages such as python include libraries for direct implementation of queues and stacks.
Pseudocode for Reversing the K Elements of Queue
Step 1: Check whether k has a valid value
We can not reverse more elements than the amount already present in our queue, hence we need to check whether the value k satisfies the condition, k < {size of queue}. Also, k needs to be a positive integer greater than zero, as we can not reverse 0 or negative number of elements. For this, we add the condition, k>0.
Since we assumed k=3, k satisfies both conditions.
This step is also known as the input validation step of the algorithm.
Syntax for C++ language
if (q.size() < k || k <= 0) {
cout<<"Invalid value for k.";
return;
}Syntax for Python language
if q.qsize() < k or k <= 0:
raise ValueError("Invalid value for k.")Syntax for Java language
if (q.size() < k || k <= 0) {
System.out.println("Invalid value for k.");
return;
}Step 2: Use a stack to reverse the first k elements
We create an empty stack that can be used to store our elements. Then, one by one, we add the first k elements from our queue into the stack. The operation of removing elements from a queue is called a ‘dequeue’ element, and the operation to insert elements onto the stack is called a ‘push’ element. Once we have ‘pushed’ k elements onto the stack, we can move to the next step.
Stack: [30,20,10] Queue:[40,50]
Syntax for C++ language:
stack<int> s;
for (int i = 0; i < k; ++i) {
s.push(q.front());
q.pop();
}Syntax for Python language:
stack = []
for _ in range(k):
stack.append(q.get())Syntax for Java language:
Stack<Integer> s = new Stack<>();
for (int i = 0; i < k; ++i) {
s.push(q.peek()); // Push the front of the queue onto the stack
q.poll(); // Remove the front element from the queue
}Step 3: Insert elements from stack back into the queue
We now remove the element from the top of the stack one by one, and add it to the back of the queue. Removing the elements from the stack uses an operation called ‘pop’, and adding it to the queue is called ‘enqueue’. We do this until the stack becomes empty and the reversed elements are now present at the back of the queue, whereas the unchanged elements after the first k elements are still present at the beginning of the queue.
Stack: [] Queue: [40,50,30,20,10]
Syntax for C++ language:
while (!s.isEmpty()) {
q.add(s.peek()); // Add the top element of the stack to the queue
s.pop(); // Remove the top element from the stack
}Syntax for Python:
while stack:
q.put(stack.pop())Syntax for Java language:
while (!s.isEmpty()) {
q.add(s.peek()); // Add the top element of the stack to the queue
s.pop(); // Remove the top element from the stack
}Step 4: Move remaining elements to the back of the queue
To maintain the order of the elements, we need to move the elements that come after the first k elements ( (queue size - k)th element onwards) to the back of the queue, so they come after the reversed elements, as in the original order.
In order to do this, we remove, or dequeue the first element of the current queue and add it, or enqueue it to the back of the queue. We continue this operation (n-k) times, where n is the size of the queue. This ensures that the reversed elements are restored to the beginning of the queue, and the unchanged elements to the end of the queue, their order preserved.
Queue: [30,20,10,40,50]
Syntax for C++ language:
int size = q.size();
for (int i = 0; i < size - k; ++i) {
q.push(q.front());
q.pop();
}Syntax for Python language:
size = q.qsize()
for _ in range(size - k):
q.put(q.get())Syntax for Java language:
int size = q.size();
for (int i = 0; i < size - k; ++i) {
q.add(q.peek()); // Add the front element of the queue to the back
q.poll(); // Remove the front element from the queue
}Now that we have understood how the algorithm works in pieces, let’s see how all the steps are functioning in a code together. The complete code for the application of the algorithm is as follows:
Implementation of C++ code:
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
void reverseFirstKElements(queue<int>& q, int k) {
if (q.size() < k || k <= 0) {
cout<<"Invalid value for k.";
return;
}
stack<int> s;
// Step 1: Push the first k elements into the stack
for (int i = 0; i < k; ++i) {
s.push(q.front());
q.pop();
}
// Step 2: Enqueue elements from the stack back into the queue
while (!s.empty()) {
q.push(s.top());
s.pop();
}
// Step 3: Move the remaining elements (queue size - k) to the back
int size = q.size();
for (int i = 0; i < size - k; ++i) {
q.push(q.front());
q.pop();
}
}
void printQueue(queue<int> q) {
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
int main() {
queue<int> q;
q.push(10);
q.push(20);
q.push(30);
q.push(40);
q.push(50);
cout << "Original Queue: ";
printQueue(q);
int k = 3;
reverseFirstKElements(q, k);
cout << "Queue after reversing first " << k << " elements: ";
printQueue(q);
return 0;
}Explanation of standard operations:
enqueue(x) : Adds an item x to the rear of the queue.
dequeue() : Removes an item from the front of the queue.
size() : Returns the number of elements in the queue.
front() : Finds the item at the front of the queue.
Output:
Original Queue: 10 20 30 40 50
Queue after reversing first 3 elements: 30 20 10 40 50Time and Space complexity:
Time Complexity:
Step 1: Pushing first k elements into the stack:
- Time complexity: O(k)
Step 2: Popping elements from the stack and enqueuing back to the queue:
- Time complexity: O(k)
Step 3: Moving remaining elements in the queue (size - k):
- Time complexity: O(n−k), where n is the total number of elements in the queue.
Total Time Complexity: O(k+(n−k))=O(n)
Space Complexity:
1. Stack Storage:
- Space complexity: O(k) (for storing the first k elements in the stack)
2. Queue Operations:
- The queue already exists; no additional space is required.
Total Space Complexity: O(k)
Implementation of Python code:
from queue import Queue
def reverse_first_k_elements(q, k):
if q.qsize() < k or k <= 0:
print("Invalid value for k or queue size is insufficient.")
return
stack = []
# Step 1: Push the first k elements into the stack
for _ in range(k):
stack.append(q.get())
# Step 2: Enqueue elements from the stack back into the queue
while stack:
q.put(stack.pop())
# Step 3: Move the remaining elements (queue size - k) to the back
size = q.qsize()
for _ in range(size - k):
q.put(q.get())
return q
# function to print the queue
def print_queue(q):
temp = []
while not q.empty():
item = q.get()
temp.append(item)
q.put(item) # Enqueue again to preserve order
print("Queue:", temp)
# Example
q = Queue()
elements = [10, 20, 30, 40, 50]
for elem in elements:
q.put(elem)
print("Original Queue:")
print_queue(q)
k = 3
q = reverse_first_k_elements(q, k)
print(f"Queue after reversing first {k} elements:")
print_queue(q)Explanation of standard operations:
q.put(x): Used to add an element to the end of the queue
q.get(): Used to remove the element at the front of the queue
q.qsize(): Returns the size of the queue
Output:
Original Queue:
Queue: [10, 20, 30, 40, 50]
Queue after reversing first 3 elements:
Queue: [30, 20, 10, 40, 50]Time and Space complexity:
Time Complexity:
Step 1: Pushing first k elements into the stack:
- O(k) (For k calls to q.get())
Step 2: Popping elements from the stack and enqueuing back to the queue:
- O(k) (For k calls to stack.pop() and q.put())
Step 3: Moving the remaining elements in the queue (size - k):
- O(n−k), where n is the total number of elements in the queue.
Total Time Complexity: O(k+(n−k))=O(n)
Space Complexity:
1. Stack Storage:
- O(k) (to store the first k elements)
2. Queue Operations:
- The queue already exists; no additional space is required.
Total Space Complexity: O(k)
Implementation of Java Code:
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class ReverseFirstKElements {
public static void reverseFirstKElements(Queue<Integer> q, int k) {
if (q.size() < k || k <= 0) {
System.out.println("Invalid value for k.");
return;
}
Stack<Integer> s = new Stack<>();
// Step 1: Push the first k elements into the stack
for (int i = 0; i < k; ++i) {
s.push(q.poll()); // Remove front element from queue and push onto stack
}
// Step 2: Enqueue elements from the stack back into the queue
while (!s.isEmpty()) {
q.add(s.pop()); // Pop from stack and add to the queue
}
// Step 3: Move the remaining elements (queue size - k) to the back
int size = q.size();
for (int i = 0; i < size - k; ++i) {
q.add(q.poll()); // Remove front and add it to the back
}
}
public static void printQueue(Queue<Integer> q) {
for (int element : q) {
System.out.print(element + " ");
}
System.out.println();
}
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.add(10);
q.add(20);
q.add(30);
q.add(40);
q.add(50);
System.out.println("Original Queue: ");
printQueue(q);
int k = 3;
reverseFirstKElements(q, k);
System.out.println("Queue after reversing first " + k + " elements: ");
printQueue(q);
}
}Explanation of Basic Operations:
q.add(x): Adds a new element to the queue
q.poll(): Removes the element at the front of the queue
q.size(): Returns the size of the queue
q.peek(): Used to view the front element of the queue
Output:
Original Queue:
10 20 30 40 50
Queue after reversing first 3 elements:
30 20 10 40 50 Time and Space complexity:
Time Complexity:
Step 1: Pushing first k elements into the stack:
- O(k) (For k calls to q.poll() and s.push())
Step 2: Popping elements from the stack and enqueuing back to the queue:
- O(k) (For k calls to s.pop() and q.add())
Step 3: Moving the remaining elements in the queue (size - k):
- O(n−k), where n is the total number of elements in the queue.
Total Time Complexity: O(k+(n−k))=O(n)
Space Complexity:
1. Stack Storage:
- O(k) (to temporarily store the first k elements)
2. Queue Operations:
- No additional space is required for the queue since the operations are performed in place.
Total Space Complexity: O(k)
It is important to note that the pop() and dequeue() operations always remove the element from the top of a stack, or the beginning of a queue, respectively. Similarly, the push() or the enqueue() operations always insert an element to the top of a stack {push} , whereas in a queue the element is inserted at the last position {enqueue}.
This algorithm is versatile and can be applied in systems where partial reordering or priority based operations are required. Some examples for the same are provided below:
- In task scheduling systems used by operating systems, where a priority queue is used, this algorithm can rearrange tasks in the priority queue to prioritize urgent tasks in reverse order.
- In multiplayer games or simulations, reversing actions or player orders for the next round of gameplay can be implemented.
- Customer service systems reorder customers based on urgency or other criteria for the first k people in line, reversing their order.
- In call centers or ticket counters, we can prioritize certain customer groups by reversing specific queue segments.
- In networking, this algorithm can be used to reorder packets or process specific data packets in reverse order without altering the rest.
- It can be used to reverse the order of flights temporarily in a queue due to changes in priority or schedules.
Reversing the first k elements of a queue is a simple yet powerful algorithm that uses the principles of stacks and queues. By combining the LIFO (Last In First Out) nature of stacks with the FIFO (First In First Out) nature of queues, the algorithm performs partial reordering while preserving the overall structure, efficiently. This makes it a valuable tool for a wide range of applications in computing, networking, and scheduling operations.
Using a stack to reverse the desired segment and reordering the remaining elements prevents disruption to the original queue. The algorithm is efficient, with a time complexity of O(n), where n is the size of the queue, and a space complexity of O(k), thus making it suitable for real world scenarios.
Practical applications can be explored across diverse fields, from task scheduling in operating systems to dynamic player management in gaming, packet reordering in networking, and customer service optimization. These use cases show the algorithm’s ability in managing priorities, reordering tasks, and improving system efficiency.
This algorithm is not just a theoretical concept in programming, but a solution that addresses real world problems where partial reversal or reordering is essential. It's simple, efficient, and practical, making it a fundamental technique to any programmer learning system design.
1. How to reverse a queue?
To reverse a queue, use a stack. Dequeue elements from the front of the queue and push them onto the stack. Then, pop elements from the stack and enqueue them back into the queue.
2. What is the reverse() method on python?
The reverse() method in Python reverses the elements of a list in place, modifying the original list.
3. What is reverse() function in java?
In Java, the reverse() method reverses the order of characters in a StringBuilder or StringBuffer.
4. How to create a list in Python?
In Python, you can create a list by enclosing elements in square brackets [], separated by commas.
5. What is slicing in Python?
Slicing in Python allows you to extract a portion of a list, string, or tuple by specifying a range of indices in the format start:stop:step.
