Published: 18 Feb 2025 | Reading Time: 5 min read
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 article, 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.
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.
This operation adds a new element to the back of the queue.
This operation removes the element at the front of the queue.
This operation returns True if the queue has no elements, and false if it has even one or more elements in it.
This operation returns True if the queue is full (if the queue has a fixed size), otherwise it returns false.
This operation returns the element at the front of the queue without removing it from 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.
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.
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.
if (q.size() < k || k <= 0) {
cout<<"Invalid value for k.";
return;
}
if q.qsize() < k or k <= 0:
raise ValueError("Invalid value for k.")
if (q.size() < k || k <= 0) {
System.out.println("Invalid value for k.");
return;
}
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]
stack<int> s;
for (int i = 0; i < k; ++i) {
s.push(q.front());
q.pop();
}
stack = []
for _ in range(k):
stack.append(q.get())
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
}
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]
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
}
while stack:
q.put(stack.pop())
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
}
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]
int size = q.size();
for (int i = 0; i < size - k; ++i) {
q.push(q.front());
q.pop();
}
size = q.qsize()
for _ in range(size - k):
q.put(q.get())
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:
#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;
}
Original Queue: 10 20 30 40 50
Queue after reversing first 3 elements: 30 20 10 40 50
Step 1: Pushing first k elements into the stack:
Step 2: Popping elements from the stack and enqueuing back to the queue:
Step 3: Moving remaining elements in the queue (size - k):
Total Time Complexity: O(k+(n−k))=O(n)
1. Stack Storage:
2. Queue Operations:
Total Space Complexity: O(k)
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)
Original Queue:
Queue: [10, 20, 30, 40, 50]
Queue after reversing first 3 elements:
Queue: [30, 20, 10, 40, 50]
Step 1: Pushing first k elements into the stack:
Step 2: Popping elements from the stack and enqueuing back to the queue:
Step 3: Moving the remaining elements in the queue (size - k):
Total Time Complexity: O(k+(n−k))=O(n)
1. Stack Storage:
2. Queue Operations:
Total Space Complexity: O(k)
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);
}
}
Original Queue:
10 20 30 40 50
Queue after reversing first 3 elements:
30 20 10 40 50
Step 1: Pushing first k elements into the stack:
Step 2: Popping elements from the stack and enqueuing back to the queue:
Step 3: Moving the remaining elements in the queue (size - k):
Total Time Complexity: O(k+(n−k))=O(n)
1. Stack Storage:
2. Queue Operations:
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:
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.
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.
The reverse() method in Python reverses the elements of a list in place, modifying the original list.
In Java, the reverse() method reverses the order of characters in a StringBuilder or StringBuffer.
In Python, you can create a list by enclosing elements in square brackets [], separated by commas.
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.
What is Matrix Chain Multiplication? Concepts, Code and Practice - Understand the concept and implementation of Matrix Chain Multiplication to find the most efficient way to multiply a chain of matrices. (11 Jan 2026, 5 min read)
A* Algorithm in AI: Pathfinding Explained with Examples - Learn how the A* algorithm in AI works for pathfinding and graph traversal. Understand its logic, use cases, and implementation with easy examples. (11 Jan 2026, 5 min read)
Boyer–Moore Algorithm: Fast String Searching Explained - Learn the Boyer Moore algorithm for fast string matching, with simple explanations, examples, and time complexity analysis. (07 Jan 2026, 5 min read)
Insertion Sort Algorithm Explained with Examples - Learn Insertion Sort with step-by-step working, pseudocode, complexity analysis, and examples in C, C++, Java, Python, and JavaScript. (04 Jan 2026, 6 min read)
Understanding the Selection Sort Algorithm - A comprehensive guide to the Selection Sort Algorithm covering concepts, working steps, and hands-on coding examples for your learning needs. (04 Jan 2026, 8 min read)
Tree Topology: A Complete Guide - Learn tree topology with clear explanations, advantages, disadvantages, examples, and real-world uses in computer networks. (04 Jan 2026, 5 min read)
About NxtWave
NxtWave is an educational technology platform providing comprehensive programming courses and resources for students and professionals.
Contact Information:
Source: This content is provided by NxtWave and should be cited as such when referenced.