Tutorialspoint.dev

Interleave the first half of the queue with second half

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.

Only a stack can be used as an auxiliary space.

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

Following are the steps to solve the problem:
1.Push the first half elements of queue to stack.
2.Enqueue back the stack elements.
3.Dequeue the first half elements of the queue and enqueue them back.
4.Again push the first half elements into the stack.
5.Interleave the elements of queue and stack.

C++

// C++ program to interleave the first half of the queue
// with the second half
#include <bits/stdc++.h>
using namespace std;
  
// Function to interleave the queue
void interLeaveQueue(queue<int>& q)
{
    // To check the even number of elements
    if (q.size() % 2 != 0)
        cout << "Input even number of integers." << endl;
  
    // Initialize an empty stack of int type
    stack<int> s;
    int halfSize = q.size() / 2;
  
    // Push first half elements into the stack
    // queue:16 17 18 19 20, stack: 15(T) 14 13 12 11
    for (int i = 0; i < halfSize; i++) {
        s.push(q.front());
        q.pop();
    }
  
    // enqueue back the stack elements
    // queue: 16 17 18 19 20 15 14 13 12 11
    while (!s.empty()) {
        q.push(s.top());
        s.pop();
    }
  
    // dequeue the first half elements of queue
    // and enqueue them back
    // queue: 15 14 13 12 11 16 17 18 19 20
    for (int i = 0; i < halfSize; i++) {
        q.push(q.front());
        q.pop();
    }
  
    // Again push the first half elements into the stack
    // queue: 16 17 18 19 20, stack: 11(T) 12 13 14 15
    for (int i = 0; i < halfSize; i++) {
        s.push(q.front());
        q.pop();
    }
  
    // interleave the elements of queue and stack
    // queue: 11 16 12 17 13 18 14 19 15 20
    while (!s.empty()) {
        q.push(s.top());
        s.pop();
        q.push(q.front());
        q.pop();
    }
}
  
// Driver program to test above function
int main()
{
    queue<int> q;
    q.push(11);
    q.push(12);
    q.push(13);
    q.push(14);
    q.push(15);
    q.push(16);
    q.push(17);
    q.push(18);
    q.push(19);
    q.push(20);
    interLeaveQueue(q);
    int length = q.size();
    for (int i = 0; i < length; i++) {
        cout << q.front() << " ";
        q.pop();
    }
    return 0;
}

Java

// Java program to interleave
// the first half of the queue
// with the second half
import java.util.*;
  
class GFG 
{
  
// Function to interleave the queue
static void interLeaveQueue(Queue<Integer>q)
{
    // To check the even number of elements
    if (q.size() % 2 != 0)
        System.out.println("Input even number of integers." );
  
    // Initialize an empty stack of int type
    Stack<Integer> s = new Stack<>();
    int halfSize = q.size() / 2;
  
    // Push first half elements into the stack
    // queue:16 17 18 19 20, stack: 15(T) 14 13 12 11
    for (int i = 0; i < halfSize; i++)
    {
        s.push(q.peek());
        q.poll();
    }
  
    // enqueue back the stack elements
    // queue: 16 17 18 19 20 15 14 13 12 11
    while (!s.empty()) 
    {
        q.add(s.peek());
        s.pop();
    }
  
    // dequeue the first half elements of queue
    // and enqueue them back
    // queue: 15 14 13 12 11 16 17 18 19 20
    for (int i = 0; i < halfSize; i++) 
    {
        q.add(q.peek());
        q.poll();
    }
  
    // Again push the first half elements into the stack
    // queue: 16 17 18 19 20, stack: 11(T) 12 13 14 15
    for (int i = 0; i < halfSize; i++)
    {
        s.push(q.peek());
        q.poll();
    }
  
    // interleave the elements of queue and stack
    // queue: 11 16 12 17 13 18 14 19 15 20
    while (!s.empty())
    {
        q.add(s.peek());
        s.pop();
        q.add(q.peek());
        q.poll();
    }
}
  
// Driver code
public static void main(String[] args) 
{
    Queue<Integer> q = new java.util.LinkedList<>();
    q.add(11);
    q.add(12);
    q.add(13);
    q.add(14);
    q.add(15);
    q.add(16);
    q.add(17);
    q.add(18);
    q.add(19);
    q.add(20);
    interLeaveQueue(q);
    int length = q.size();
    for (int i = 0; i < length; i++) 
    {
        System.out.print(q.peek() + " ");
        q.poll();
    }
}
}
  
// This code contributed by Rajput-Ji

Python3

# Python3 program to interleave the first 
# half of the queue with the second half 
from queue import Queue 
  
# Function to interleave the queue 
def interLeaveQueue(q):
      
    # To check the even number of elements 
    if (q.qsize() % 2 != 0): 
        print("Input even number of integers.")
  
    # Initialize an empty stack of int type 
    s = []
    halfSize = int(q.qsize() / 2
  
    # put first half elements into 
    # the stack queue:16 17 18 19 20, 
    # stack: 15(T) 14 13 12 11
    for i in range(halfSize):
        s.append(q.queue[0]) 
        q.get()
  
    # enqueue back the stack elements 
    # queue: 16 17 18 19 20 15 14 13 12 11 
    while len(s) != 0
        q.put(s[-1]) 
        s.pop()
  
    # dequeue the first half elements of 
    # queue and enqueue them back 
    # queue: 15 14 13 12 11 16 17 18 19 20
    for i in range(halfSize):
        q.put(q.queue[0]) 
        q.get()
  
    # Again put the first half elements into 
    # the stack queue: 16 17 18 19 20,
    # stack: 11(T) 12 13 14 15 
    for i in range(halfSize):
        s.append(q.queue[0]) 
        q.get()
  
    # interleave the elements of queue and stack 
    # queue: 11 16 12 17 13 18 14 19 15 20 
    while len(s) != 0
        q.put(s[-1]) 
        s.pop() 
        q.put(q.queue[0]) 
        q.get()
  
# Driver Code
if __name__ == '__main__':
    q = Queue()
    q.put(11
    q.put(12
    q.put(13
    q.put(14
    q.put(15
    q.put(16
    q.put(17
    q.put(18
    q.put(19
    q.put(20
    interLeaveQueue(q) 
    length = q.qsize()
    for i in range(length):
        print(q.queue[0], end = " "
        q.get()
  
# This code is contributed by PranchalK


Output:

11 16 12 17 13 18 14 19 15 20 

Time complexity: O(n).
Auxiliary Space: O(n).

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter