Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Problem Statement 
1.2.
Sample Examples 
2.
Brute Force Approach 
2.1.
Steps of Algorithm 
2.2.
Implementation in C++
2.3.
Implementation in Python
2.4.
Complexity analysis
3.
Frequently Asked Questions
3.1.
What are the types of queues in data structures?
3.2.
What are the basic queue data structures operations? 
3.3.
Mention some applications of the queue?
4.
Conclusion
Last Updated: Mar 27, 2024

Interleave the first half of the queue with second half

Author Shivani Singh
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Here in this blog, we are asked to see various approaches to interleave the first half of the queue with the second half. As we are already familiar with the queue data structures. The queue is a linear data structure that has the property of first in first out. That means the element which will first enter the queue will also be the first one to come out. Let's see how we can solve this problem statement. So, let's dig a little deeper into this blog.

Problem Statement 

In this problem, we are provided a queue data structure and we are asked to interleave the first half of the queue with the second half. The point to be noted here is that the queue length will always be even. We will see how we will be using the second half of the queue to get this problem solved. Let us understand the problem statement with the help of an example. We need to recall the property of queue data structures i.e. FIFO. the various operations which are performed on queue like enqueue, dequeue, etc need to be kept in mind while approaching the problem. 

Sample Examples 

From the above diagram, we can clearly understand the problem statement. We can see how we are interleaving the first half of the queue using the second half. 

Brute Force Approach 

This approach is very simple to implement and straightforward. We will first push the first half elements of the queue to stack. And after that, we will push back the stack elements. And then delete the first half elements of the queue and enqueue them back. Then again we will push the first half elements into the stack. And as the last step, with the help of the second half, we will Interleave the elements of queue and stack.

Let us see its algorithm. 

Steps of Algorithm 

Step 1: Enqueue the first half element from the queue to the stack.

Step 2: Remove elements from the stack and enqueue them back to the queue.

Step 3: Move the first half elements of the queue to the end of the queue.

Step 4: Enqueue the first half of the elements to the stack.

Step 5: In interleave fashion, write the elements of the stack to the queue.

Source: brute force approach

 

Let us see the implementation of this approach in the next section of this blog.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;
void inter_Leave_Queue(queue<int>& que)
{
         if (que.size() % 2 != 0)  // if size is even or not
                 cout << "Input even number of integers." << endl;
         stack<int> s;
         int halfSize = que.size() / 2;
         for (int i = 0; i < halfSize; i++)
         {
              s.push(que.front());
              que.pop();
         }
         while (!s.empty()) 
         {  // enqueue back the stack elements
              que.push(s.top());
              s.pop();
         }
         for (int i = 0; i < halfSize; i++) 
         { // dequeue the first half elements of queue and enqueue them back
              que.push(que.front());
              que.pop();
         }
         for (int i = 0; i < halfSize; i++) 
         { //Again push the first half elements into the stack
              s.push(que.front());
              que.pop();
         }
         while (!s.empty()) 
         { //interleave the elements of queue and stack
              que.push(s.top());
              s.pop();
              que.push(que.front());
              que.pop();
         }
}
int main()
{
          queue<int> que;
          que.push(3);
          que.push(4);
          que.push(7);
          que.push(8);  //printing the elements in interleave fashion
          cout<<"The elements of the queue in an interleaving fashion are: "<<endl;
          inter_Leave_Queue(que);
          int length = que.size();
          for (int i = 0; i < length; i++) 
          {
                  cout << que.front() << " ";
                  que.pop();
          }
          return 0;
}

 

Output:

The elements of the queue in an interleaving fashion are: 
3 7 4 8

 

Implementation in Python

from queue import Queue
def inter_Leave_Queue(que):
         if (que.qsize() % 2 != 0): #check if size is even or not
                  print("Input even number of integers.")
         s = []
         halfSize = int(que.qsize() / 2)
         for i in range(halfSize): #put first half elements into the stack
                  s.append(que.queue[0])
                  que.get()
         while len(s) != 0: ## enqueue back the stack elements
                  que.put(s[-1])
                  s.pop()
         for i in range(halfSize): #dequeue the first half elements of queue and enqueue them back
                  que.put(que.queue[0])
                  que.get()
         for i in range(halfSize): #Again put the first half elements into the stack
                  s.append(que.queue[0])
                  que.get()
         while len(s) != 0:  #interleave function
                  que.put(s[-1])
                  s.pop()
                  que.put(que.queue[0])
                  que.get()
if __name__ == '__main__':
          que = Queue()
          que.put(3)
          que.put(4)
          que.put(7)
          que.put(8)  #printing the elements in interleave fashion
          print("The elements of the queue in an interleaving fashion are: ")
          inter_Leave_Queue(que)
          length = que.qsize()
          for i in range(length):
                 print(que.queue[0], end = " ")
                 que.get()

 

Output:

The elements of the queue in an interleaving fashion are: 
3 7 4 8 

 

Let us analyze the time and complexity of this approach.

Complexity analysis

Time complexity

This approach will take O(N) where n is the size of the queue. Because in this approach, the loop is iterating N/2 times and we are using the loops 5 times here in the program. So it will take O(N) time complexity.  

Space complexity

And it will take O(N). Since we are using a stack data structure to store it as an auxiliary space. 

Read about Application of Queue in Data Structure here.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What are the types of queues in data structures?

There are four types of queues: 

Simple Queue: It is the most basic queue in which an item is inserted at the front of the queue and deleted at the back. 

Circular Queue: The last node in a circular node is linked to the first node. Because all of the ends are connected to one another, it is also known as a Ring Buffer. Insertion occurs at the front of the queue, and deletion occurs at the back.

Priority Queue: The nodes in a priority queue will have a predetermined priority in the priority queue. The node with the lowest priority will be removed from the queue first.

Double-Ended Queue (Dequeue): Insertion and deletion can occur at both the front and back ends of a double-ended queue. 

What are the basic queue data structures operations? 

The basic queue operations are: enqueue(), dequeue(), peek(), isfull(), isempty().

Mention some applications of the queue?

  • Managing requests against a single shared resource, such as CPU and disc scheduling
  • Handling interrupts in hardware or real-time systems
  • Controlling website traffic
  • Routers and switches in networking devices.
  • Keeping the playlist in the media players

Conclusion

To conclude this blog, firstly we discussed the problem statement on how to interleave the first half of the queue with the second half. And different examples to understand the problem statement. For the brute force approach, we discussed its algorithm, implementations, and complexities. 

For more content, Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Sorting of Queue
Next article
Implementation of Queue using Arrays in C++
Live masterclass