Given a queue of integers of even length, rearrange the elements by interleaving the first half of the queue with the second half of the queue. We are allowed to use only the queue data structure.
Examples:
Input : 1 2 3 4 Output : 1 3 2 4 Input : 11 12 13 14 15 16 17 18 19 20 Output : 11 16 12 17 13 18 14 19 15 20
Create two auxiliary queues q1 and q2. Insert first half in one queue q1 and another half in another queue q2. Now insert elements back to given queue by picking them from q1 and q2 alternatively.
CPP
// CPP program to interleave queue elements// using only queue data structure.#include <bits/stdc++.h>using namespace std;void interleave(queue<int> &q){ queue<int> q1, q2; int n = q.size(); // Insert first half in q1 for (int i = 0; i < n / 2; i++) { q1.push(q.front()); q.pop(); } // insert second half in q2 for (int i = 0; i < n / 2; i++) { q2.push(q.front()); q.pop(); } // Insert elements of q1 and q2 back // to q in alternate order. for (int i = 0; i < n/2; i++) { q.push(q1.front()); q1.pop(); q.push(q2.front()); q2.pop(); }}// Driver codeint main(){ // Creating an example queue with 10 // elements. queue<int> q; for (int i = 1; i <= 10; i++) q.push(i); interleave(q); // Printing queue elements int n = q.size(); for (int i = 0; i < n; i++) { cout << q.front() << " "; q.pop(); }} |
Java
// Java program to interleave queue elements// using only queue data structure.import java.util.LinkedList;import java.util.Queue;public class GFG { static void interleave(Queue<Integer> q) { Queue<Integer> q1, q2; q1 = new LinkedList<Integer>(); q2 = new LinkedList<Integer>(); int n = q.size(); // Insert first half in q1 for (int i = 0; i < n / 2; i++) { q1.add(q.peek()); q.poll(); } // insert second half in q2 for (int i = 0; i < n / 2; i++) { q2.add(q.peek()); q.poll(); } // Insert elements of q1 and q2 back // to q in alternate order. for (int i = 0; i < n / 2; i++) { q.add(q1.peek()); q1.poll(); q.add(q2.peek()); q2.poll(); } } // Driver code public static void main(String[] args) { // Creating an example queue with 10 // elements. Queue<Integer> q = new LinkedList<Integer>(); for (int i = 1; i <= 10; i++) q.add(i); interleave(q); // Printing queue elements int n = q.size(); for (int i = 0; i < n; i++) { System.out.print(q.peek() + " "); q.poll(); } }}// This code is contributed by jainlovely450 |
Python3
# Python3 program to interleave the first# half of the queue with the second halffrom queue import Queue# Function to interleave the queuedef interLeaveQueue(q): # Initialize an empty stack of int type q1 = Queue() q2 = Queue() halfSize = int(q.qsize() / 2) # Insert first half in q1 for i in range(halfSize): q1.put(q.queue[0]) q.get() # Insert second half in q2 for i in range(halfSize): q2.put(q.queue[0]) q.get() # Insert elements of q1 and q2 back # to q in alternate order for i in range(halfSize): q.put(q1.queue[0]) q1.get() q.put(q2.queue[0]) q2.get()# Driver Codeif __name__ == '__main__': q = Queue() q.put(1) q.put(2) q.put(3) q.put(4) q.put(5) q.put(6) q.put(7) q.put(8) q.put(9) q.put(10) interLeaveQueue(q) length = q.qsize() for i in range(length): print(q.queue[0], end=" ") q.get()# This code is contributed by jainlovely450 |
Javascript
// JS program to interleave queue elements// using only queue data structure.function interleave(q){ let q1 = []; let q2 = []; let n = q.length; // Insert first half in q1 for (let i = 0; i < n / 2; i++) { q1.push(q[0]); q.shift(); } // insert second half in q2 for (let i = 0; i < n / 2; i++) { q2.push(q[0]); q.shift(); } // Insert elements of q1 and q2 back // to q in alternate order. for (let i = 0; i < n / 2; i++) { q.push(q1[0]); q1.shift(); q.push(q2[0]); q2.shift(); }}// Driver code// Creating an example queue with 10// elements.let q = [];for (let i = 1; i <= 10; i++) q.push(i);interleave(q);// Printing queue elementslet n = q.length;for (let i = 0; i < n; i++) { console.log(q[0]); q.shift();}// This code is contributed by adityamaharshi21. |
C#
// C# program to interleave queue elements// using only queue data structure.using System;using System.Collections.Generic;class Program { static void Interleave(Queue<int> q) { Queue<int> q1 = new Queue<int>(); Queue<int> q2 = new Queue<int>(); int n = q.Count; // Insert first half in q1 for (int i = 0; i < n / 2; i++) { q1.Enqueue(q.Peek()); q.Dequeue(); } // insert second half in q2 for (int i = 0; i < n / 2; i++) { q2.Enqueue(q.Peek()); q.Dequeue(); } // Insert elements of q1 and q2 back // to q in alternate order. for (int i = 0; i < n / 2; i++) { q.Enqueue(q1.Peek()); q1.Dequeue(); q.Enqueue(q2.Peek()); q2.Dequeue(); } } // Driver code static void Main() { // Creating an example queue with 10 // elements. Queue<int> q = new Queue<int>(); for (int i = 1; i <= 10; i++) { q.Enqueue(i); } Interleave(q); // Printing queue elements int n = q.Count; for (int i = 0; i < n; i++) { Console.Write(q.Peek() + " "); q.Dequeue(); } }}// This code is contributed by shivamsharma215 |
Output:
1 6 2 7 3 8 4 9 5 10
Video Contributed by Parul Shandilya
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!