Given a queue q[] of even size. Rearrange the elements by interleaving the first half with the second half.
Note: Interleaving means take one element from the first half, then one element from the second half, then the next element from the first half, then the next element from the second half, and continue this process until the queue is fully rearranged.
Examples:
Input: q[] = [2, 4, 3, 1]
Output: [2, 3, 4, 1]
Explanation: We place the first element of the first half 2 and after that place the first element of second half 3 and after that repeat the same process one more time so the resulting queue will be [2, 3, 4, 1]Input: q[] = [3, 5]
Output: [3, 5]
Explanation: We place the first element of the first half 3 and first element of the second half 5 so the resulting queue is [3, 5]
Try it on GfG Practice
Table of Content
[Expected Approach 1] Using Stack - O(n) Time and O(n) Space
The idea is to place the first half of the elements into a stack (so that the top holds the first element) and keep the second half in the queue
- First, we want the first half of the queue to be reversed so that we can interleave properly. To do this, we push the first half into a stack (stack naturally reverses order).
- But since we need them later in their original order for interleaving, we enqueue them back and then dequeue the first half again. This ensures when we push them into the stack this time, they end up in the right sequence for interleaving.
- Finally, we take elements alternately from the stack and the queue and insert them back into the queue, which produces the interleaved arrangement.
Note : In JavaScript, there is no built-in queue data structure, so we create a custom queue class.
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
void rearrangeQueue(queue<int>& q){
stack<int> s;
int halfSize = q.size() / 2;
// Push first half elements into the stack
for (int i = 0; i < halfSize; i++) {
s.push(q.front());
q.pop();
}
// enqueue back the stack elements
while (!s.empty()) {
q.push(s.top());
s.pop();
}
// dequeue the first half elements of
// queue and enqueue them back
for (int i = 0; i < halfSize; i++) {
q.push(q.front());
q.pop();
}
// Again push the first half elements into the stack
for (int i = 0; i < halfSize; i++) {
s.push(q.front());
q.pop();
}
// interleave the elements of queue and stack
while (!s.empty()) {
q.push(s.top());
s.pop();
q.push(q.front());
q.pop();
}
}
int main() {
queue<int> q;
q.push(2);
q.push(4);
q.push(3);
q.push(1);
rearrangeQueue(q);
int length = q.size();
for (int i = 0; i < length; i++) {
cout << q.front() << " ";
q.pop();
}
return 0;
}
import java.util.Queue;
import java.util.LinkedList;
import java.util.Stack;
import java.util.ArrayDeque;
class GfG {
public static void rearrangeQueue(Queue<Integer> q) {
Stack<Integer> s = new Stack<>();
int halfSize = q.size() / 2;
// Push first half elements into the stack
for (int i = 0; i < halfSize; i++) {
s.push(q.poll());
}
// enqueue back the stack elements
while (!s.isEmpty()) {
q.add(s.pop());
}
// dequeue the first half elements of queue and enqueue them back
for (int i = 0; i < halfSize; i++) {
q.add(q.poll());
}
// Again push the first half elements into the stack
for (int i = 0; i < halfSize; i++) {
s.push(q.poll());
}
// interleave the elements of queue and stack
while (!s.isEmpty()) {
q.add(s.pop());
q.add(q.poll());
}
}
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.add(2);
q.add(4);
q.add(3);
q.add(1);
rearrangeQueue(q);
int length = q.size();
for (int i = 0; i < length; i++) {
System.out.print(q.poll() + " ");
}
}
}
from collections import deque
def rearrangeQueue(q):
stack = []
halfSize = len(q) // 2
# Push first half elements into the stack
for _ in range(halfSize):
stack.append(q.popleft())
# enqueue back the stack elements
while stack:
q.append(stack.pop())
# dequeue the first half elements of queue and enqueue them back
for _ in range(halfSize):
q.append(q.popleft())
# Again push the first half elements into the stack
for _ in range(halfSize):
stack.append(q.popleft())
# interleave the elements of queue and stack
while stack:
q.append(stack.pop())
q.append(q.popleft())
if __name__ == "__main__":
q = deque([2, 4, 3, 1])
rearrangeQueue(q)
print(" ".join(map(str, q)))
using System;
using System.Collections.Generic;
class GfG {
static void rearrangeQueue(Queue<int> q) {
// Initialize an empty stack of int type
Stack<int> s = new Stack<int>();
int halfSize = q.Count / 2;
// Push first half elements into the stack
for (int i = 0; i < halfSize; i++) {
s.Push(q.Dequeue());
}
// Enqueue back the stack elements
while (s.Count > 0) {
q.Enqueue(s.Pop());
}
// Dequeue the first half elements of queue and enqueue them back
for (int i = 0; i < halfSize; i++) {
q.Enqueue(q.Dequeue());
}
// Again push the first half elements into the stack
for (int i = 0; i < halfSize; i++) {
s.Push(q.Dequeue());
}
// Interleave the elements of queue and stack
while (s.Count > 0) {
q.Enqueue(s.Pop());
q.Enqueue(q.Dequeue());
}
}
static void Main() {
Queue<int> q = new Queue<int>();
q.Enqueue(2);
q.Enqueue(4);
q.Enqueue(3);
q.Enqueue(1);
rearrangeQueue(q);
int length = q.Count;
for (int i = 0; i < length; i++) {
Console.Write(q.Dequeue() + " ");
}
}
}
// Node class
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Custom Queue class
class Queue {
constructor() {
this.front = this.rear = null;
this.size = 0;
}
isEmpty() { return this.front === null; }
enqueue(data) {
const node = new Node(data);
if (this.isEmpty()) {
this.front = this.rear = node;
} else {
this.rear.next = node;
this.rear = node;
}
this.size++;
}
dequeue() {
if (this.isEmpty()) return null;
this.front = this.front.next;
if (!this.front) this.rear = null;
this.size--;
}
peek() { return this.front ? this.front.data : null; }
len() { return this.size; }
}
// Rearrange queue function using custom queue
function rearrangeQueue(q) {
let s = [];
let halfSize = Math.floor(q.len() / 2);
// Push first half into stack
for (let i = 0; i < halfSize; i++) {
s.push(q.peek());
q.dequeue()
}
// Enqueue back stack elements
while (s.length > 0) {
q.enqueue(s.pop());
}
// Move first half to back
for (let i = 0; i < halfSize; i++) {
q.enqueue(q.peek());
q.dequeue();
}
// Push first half into stack again
for (let i = 0; i < halfSize; i++) {
s.push(q.peek());
q.dequeue();
}
// Interleave stack and queue
while (s.length > 0) {
q.enqueue(s.pop());
q.enqueue(q.peek());
q.dequeue();
}
}
// Driver Code
let q = new Queue();
q.enqueue(2);
q.enqueue(4);
q.enqueue(3);
q.enqueue(1);
rearrangeQueue(q);
let arr = [];
while (!q.isEmpty()) {
arr.push(q.peek());
q.dequeue();
}
console.log(arr.join(' '));
Output
2 3 4 1
[Expected Approach 2] Using Queue - O(n) Time and O(n) Space
The idea is to split the queue into two halves. Move the first half of the elements into a new queue firstHalf, and the remaining elements into another queue secondHalf. Then, alternately take one element from firstHalf and one from secondHalf and push them back into the original queue.
Note: In JavaScript, there is no built-in queue data structure, so we create a custom queue class.
#include <iostream>
#include <queue>
#include<algorithm>
using namespace std;
void rearrangeQueue(queue<int>& q) {
int n = q.size();
queue<int> firstHalf, secondHalf;
// Split the queue into two halves
for (int i = 0; i < n / 2; i++) {
firstHalf.push(q.front());
q.pop();
}
// Move the remaining elements to the second half
while (!q.empty()) {
secondHalf.push(q.front());
q.pop();
}
// Interleave the elements from both halves
while (!firstHalf.empty() && !secondHalf.empty()) {
q.push(firstHalf.front());
firstHalf.pop();
q.push(secondHalf.front());
secondHalf.pop();
}
}
int main() {
queue<int> q;
q.push(2);
q.push(4);
q.push(3);
q.push(1);
rearrangeQueue(q);
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
return 0;
}
import java.util.LinkedList;
import java.util.Queue;
class GfG {
public static void rearrangeQueue(Queue<Integer> q) {
int n = q.size();
Queue<Integer> firstHalf = new LinkedList<>();
Queue<Integer> secondHalf = new LinkedList<>();
// Split the queue into two halves
for (int i = 0; i < n / 2; i++) {
firstHalf.add(q.peek());
q.remove();
}
// Move the remaining elements to the second half
while (!q.isEmpty()) {
secondHalf.add(q.peek());
q.remove();
}
// Interleave the elements from both halves
while (!firstHalf.isEmpty() && !secondHalf.isEmpty()) {
q.add(firstHalf.peek());
firstHalf.remove();
q.add(secondHalf.peek());
secondHalf.remove();
}
}
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.add(2);
q.add(4);
q.add(3);
q.add(1);
rearrangeQueue(q);
while (!q.isEmpty()) {
System.out.print(q.peek() + " ");
q.remove();
}
}
}
from collections import deque
def rearrangeQueue(q):
n = len(q)
firstHalf = deque()
secondHalf = deque()
# Split the queue into two halves
for i in range(n // 2):
firstHalf.append(q.popleft())
# Move the remaining elements to the second half
while q:
secondHalf.append(q.popleft())
# Interleave the elements from both halves
while firstHalf and secondHalf:
q.append(firstHalf.popleft())
q.append(secondHalf.popleft())
if __name__ == "__main__":
q = deque()
q.append(2)
q.append(4)
q.append(3)
q.append(1)
rearrangeQueue(q)
while q:
print(q.popleft(), end=" ")
using System;
using System.Collections.Generic;
class GfG {
public static void rearrangeQueue(Queue<int> q) {
int n = q.Count;
Queue<int> firstHalf = new Queue<int>();
Queue<int> secondHalf = new Queue<int>();
// Split the queue into two halves
for (int i = 0; i < n / 2; i++) {
firstHalf.Enqueue(q.Dequeue());
}
// Move the remaining elements to the second half
while (q.Count > 0) {
secondHalf.Enqueue(q.Dequeue());
}
// Interleave the elements from both halves
while (firstHalf.Count > 0 && secondHalf.Count > 0) {
q.Enqueue(firstHalf.Dequeue());
q.Enqueue(secondHalf.Dequeue());
}
}
public static void Main()
{
Queue<int> q = new Queue<int>();
q.Enqueue(2);
q.Enqueue(4);
q.Enqueue(3);
q.Enqueue(1);
rearrangeQueue(q);
while (q.Count > 0)
{
Console.Write(q.Dequeue() + " ");
}
}
}
// Node class
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Custom Queue class
class Queue {
constructor() {
this.front = this.rear = null;
this.size = 0;
}
isEmpty() {
return this.front === null;
}
enqueue(data) {
const node = new Node(data);
if (this.isEmpty()) {
this.front = this.rear = node;
} else {
this.rear.next = node;
this.rear = node;
}
this.size++;
}
dequeue() {
if (this.isEmpty()) return null;
const val = this.front.data;
this.front = this.front.next;
if (!this.front) this.rear = null;
this.size--;
return val;
}
peek() {
return this.front ? this.front.data : null;
}
len() {
return this.size;
}
}
function rearrangeQueue(q) {
let n = q.len();
let firstHalf = new Queue();
let secondHalf = new Queue();
// Split the queue into two halves
for (let i = 0; i < Math.floor(n / 2); i++) {
firstHalf.enqueue(q.peek());
q.dequeue();
}
// Move remaining elements to second half
while (!q.isEmpty()) {
secondHalf.enqueue(q.peek());
q.dequeue();
}
// Interleave elements from both halves
while (!firstHalf.isEmpty() && !secondHalf.isEmpty()) {
q.enqueue(firstHalf.peek());
firstHalf.dequeue();
q.enqueue(secondHalf.peek());
secondHalf.dequeue();
}
}
// Driver code
const q = new Queue();
q.enqueue(2);
q.enqueue(4);
q.enqueue(3);
q.enqueue(1);
rearrangeQueue(q);
while (!q.isEmpty()) {
process.stdout.write(q.dequeue() + " ");
}
Output
2 3 4 1
[Expected Approach 3] Getting Result in an Array - O(n) Time and O(n) Space
The approach works by splitting the queue into two halves and then placing their elements alternately into a result array. Elements from the first half are placed at even positions, while elements from the second half are placed at odd positions. This way, the final array naturally forms an interleaved order of the two halves.
Note: In JavaScript, there is no built-in queue data structure, so we create a custom queue class.
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void rearrangeQueue(queue<int>& q) {
int n = q.size();
vector<int> arr(n);
// Copy elements from queue to array
for (int i = 0; i < n; i++) {
arr[i] = q.front();
q.pop();
}
// Interleave elements back into the queue
for (int i = 0; i < n / 2; i++) {
q.push(arr[i]);
q.push(arr[i + n / 2]);
}
}
int main() {
queue<int> q;
q.push(2);
q.push(4);
q.push(3);
q.push(1);
rearrangeQueue(q);
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
return 0;
}
import java.util.Queue;
import java.util.LinkedList;
class GFG {
public static void rearrangeQueue(Queue<Integer> q) {
int n = q.size();
int[] arr = new int[n];
// Copy elements from queue to array
for (int i = 0; i < n; i++) {
arr[i] = q.poll();
}
// Interleave elements back into the queue
for (int i = 0; i < n / 2; i++) {
q.add(arr[i]);
q.add(arr[i + n / 2]);
}
}
public static void main(String[] args) {
Queue<Integer> q = new LinkedList<>();
q.add(2);
q.add(4);
q.add(3);
q.add(1);
rearrangeQueue(q);
while (!q.isEmpty()) {
System.out.print(q.poll() + " ");
}
}
}
from collections import deque
def rearrangeQueue(q):
n = len(q)
# copy elements to temporary array
arr = list(q)
q.clear()
# Interleave elements back into the queue
for i in range(n // 2):
q.append(arr[i])
q.append(arr[i + n // 2])
if __name__ == '__main__':
q = deque([2, 4, 3, 1])
rearrangeQueue(q)
print(' '.join(map(str, q)))
using System;
using System.Collections.Generic;
class GFG {
static void rearrangeQueue(Queue<int> q) {
int n = q.Count;
// copy elements to temporary array
int[] arr = q.ToArray();
q.Clear();
for (int i = 0; i < n/2; i++) {
q.Enqueue(arr[i]);
q.Enqueue(arr[i + n/2]);
}
}
static void Main() {
Queue<int> q = new Queue<int>();
q.Enqueue(2);
q.Enqueue(4);
q.Enqueue(3);
q.Enqueue(1);
rearrangeQueue(q);
foreach (int num in q) {
Console.Write(num + " ");
}
}
}
// Node class
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
// Custom Queue class
class Queue {
constructor() {
this.front = this.rear = null;
this.size = 0;
}
isEmpty() {
return this.front === null;
}
enqueue(data) {
const node = new Node(data);
if (this.isEmpty()) {
this.front = this.rear = node;
} else {
this.rear.next = node;
this.rear = node;
}
this.size++;
}
dequeue() {
if (this.isEmpty()) return null;
const val = this.front.data;
this.front = this.front.next;
if (!this.front) this.rear = null;
this.size--;
return val;
}
peek() {
return this.front ? this.front.data : null;
}
len() {
return this.size;
}
}
function rearrangeQueue(q) {
const n = q.size;
const arr = [];
// Copy elements to temporary array
while (!q.isEmpty()) {
arr.push(q.peek());
q.dequeue();
}
// Interleave first and second halves
for (let i = 0; i < n / 2; i++) {
q.enqueue(arr[i]);
q.enqueue(arr[i + n / 2]);
}
}
// Driver code
const q = new Queue();
q.enqueue(2);
q.enqueue(4);
q.enqueue(3);
q.enqueue(1);
rearrangeQueue(q);
while (!q.isEmpty()) {
process.stdout.write(q.dequeue() + " ");
}
Output
2 3 4 1