How to Efficiently Implement k Queues in a Single Array? (2024)

How to Efficiently Implement k Queues in a Single Array? (1)

  • Trending Categories
  • Data Structure
  • Networking
  • RDBMS
  • Operating System
  • Java
  • MS Excel
  • iOS
  • HTML
  • CSS
  • Android
  • Python
  • C Programming
  • C++
  • C#
  • MongoDB
  • MySQL
  • Javascript
  • PHP
  • Physics
  • Chemistry
  • Biology
  • Mathematics
  • English
  • Economics
  • Psychology
  • Social Studies
  • Fashion Studies
  • Legal Studies
  • Selected Reading
  • UPSC IAS Exams Notes
  • Developer's Best Practices
  • Questions and Answers
  • Effective Resume Writing
  • HR Interview Questions
  • Computer Glossary
  • Who is Who

Data StructureProgrammingData Structure and Algorithms

';

In some cases, we need to implement our own data structure for better usability and customization. Here, we need to implement the K Queues using the single array.

The first solution that comes to mind is dividing the array into N/K parts and using each part of the array as a queue. Here, N is the array length. The problem with this solution is that we can’t utilize the array's space properly. If the array is not full, but any Mth queue indexes are full, we can’t insert an element to the Mth queue. So, we need an optimized approach.

The efficient approach uses the circular array to avoid wasting the array space. We can connect each array element to the next element using the next[] array. So we can get the next element of the current queue. We can start a new queue with any empty slot if we want to start a new queue.

Problem statement − We have given an array of length N. We need to implement the K queues in the given array.

Approach 1

This approach will use the que_arr[] to store the queue elements. Also, we will use the three arrays below to track the queue elements.

  • start[] = To store the starting pointer of each queue.

  • last[] = To store the last pointer of each queue.

  • next[] = To store the next pointer of each element of each queue.

Here, we can use any free slots to start a new queue, and we will present free slots with −1 in the next[] array. Also, we will implement the functionalities to check whether the queue is empty or full.

Algorithm

Step 1 − Define the ‘customQueue’ class. Inside the ‘customQueue’ class, define the ‘que_arr’, ‘start’, ‘last’, and ‘next’ pointers of integer type. Also, define the n and k to store the array length, the total number of queues, and the ‘freeslot’ variable to track the next index of the available slot.

Step 2 − Also, declare the constructor and methods into the class.

Step 3 − Next, define the member functions of the class. First, we will define the constructor for the class.

Step 3.1 − Initialize the n and K variables. Also, initialize the que_arr and next pointer with the array of length N, and start and last pointer with the array of the length K.

Step 3.2 − Update all values of the start[] array with −1, as all indexes are available to start the queue. Also, update the ‘freeSlot’ with 0.

Step 3.3 − Next, update the next[p] with p + 1 to connect each element with the next element.

Step 4 − Now, define the enq() member function to insert an element into any queue. It takes the element and que number as a parameter.

Step 4.1 − If the queue is full, print the message accordingly. If the freeSlot value is −1, the que is full.

Step 4.2 − Otherwise, store the ‘freeSlot’ value in p to get the next free slot.

Step 4.3 −Update the ‘freeSlot’ with the next[p], representing the next pointer of the current slot.

Step 4.4 − If the queue is empty, update the start[q_num] with p. Else, update the next[last[q_num]] with p.

Step 4.5 − Update the next[p] with −1. Also, update the last pointer of the current queue with the ‘p’ and add the given element at the ‘p’ index in que_arr.

Step 5 − Define the deq() function to remove the element from any queue.

Step 5.1 − If the queue is empty, print the message accordingly. If start[q_num] is −1, we can say the queue is empty.

Step 5.2 − Get the starting pointer of the queue, and update the start pointer with the next pointer as we need to remove the first element of the queue.

Step 5.3 − Update the next[p] with the ‘freeslot’ value and ‘freeslot’ with the p.

Step 5.4 − Return the que_arr[p] element.

Step 6 − In the main() function, use the enq() method to add different values to the different queues.

Step 7 − After that, execute the deq() method for each queue and observe the output.

Example

#include <iostream>#include <climits>using namespace std;// Class to create a custom queueclass customQueue { // Array for a queue int *que_arr; // start pointer int *start; // End ponter int *last; // Next pointer int *next; int n, k; // For storing indexes of free slots in que_arr int freeslot;public: // Constructor customQueue(int k, int n); // To check whether any space is available or not bool isQueFull() { return (freeslot == -1); } // Method declaration to enqueue an ele void enq(int ele, int q_num); // Method declaration to dequeue an ele int deq(int q_num); // For checking whether queue number 'q_num' is empty or not bool isQueueEmpty(int q_num) { return (start[q_num] == -1); }};// Constructor to create k queues in an array of size ncustomQueue::customQueue(int totalQueues, int arr_len) { // Initialize n and k, and allocate // memory for all arrays k = totalQueues, n = arr_len; que_arr = new int[n]; start = new int[k]; last = new int[k]; next = new int[n]; // Initially, all queues are available for (int p = 0; p < k; p++) start[p] = -1; freeslot = 0; // Connect current slot with next slot for (int p = 0; p < n - 1; p++) next[p] = p + 1; next[n - 1] = -1; // last slot is free slot}void customQueue::enq(int ele, int q_num) { if (isQueFull()) { cout << "
Queue is full!
"; return; } // Get an index of free slot int p = freeslot; // Current slot is filled. So, the next slot will be free freeslot = next[p]; // Set the index of the free slot as start if the queue is empty1 if (isQueueEmpty(q_num)) start[q_num] = p; else next[last[q_num]] = p; // Next slot is last pointer of current queue next[p] = -1; // mark as a free slot // last pointer for the current queue last[q_num] = p; // Enqueue element que_arr[p] = ele;}int customQueue::deq(int q_num) { if (isQueueEmpty(q_num)) { cout << "
Queue is empty!
"; return INT_MAX; } // get the start index int p = start[q_num]; // We remove the first element from the queue. So, the next of the current element will be the starting point of the queue start[q_num] = next[p]; // Update the next slot with a free slot next[p] = freeslot; freeslot = p; // return the element return que_arr[p];}int main() { // queue of size 4 and array of size 15 int k = 4, n = 15; customQueue que(k, n); // Insert in first queue que.enq(54, 0); que.enq(98, 0); // Insert in second queue que.enq(93, 1); que.enq(23, 1); que.enq(12, 1); // Insert in third queue que.enq(1, 2); que.enq(97, 2); que.enq(27, 2); // Insert in fourth queue que.enq(54, 3); que.enq(23, 3); que.enq(65, 3); cout << "After removing the element from 1st queue is " << que.deq(1) << endl; cout << "After removing the element from 2nd queue is " << que.deq(2) << endl; cout << "After removing the element from 0th queue is " << que.deq(0) << endl; cout << "After removing the element from 3rd queue is " << que.deq(3) << endl; return 0;}

Output

After removing the element from 1st queue is 93After removing the element from 2nd queue is 1After removing the element from 0th queue is 54After removing the element from 3rd queue is 54

Time complexity − O(1) for the enqueue and deque.

Space complexity − O(N) to store the elements in a queue.

The K queue implementation using the circular array saves space, but we need to handle each queue's start, end, and next pointer perfectly. Otherwise, it can give random errors.

However, it is more complex to implement than the naïve approach, but saving memory is most important in real0−time development.

Shubham Vora

Updated on: 21-Jul-2023

208 Views

  • Related Articles
  • Implement Stack using Queues in C++
  • Python Program to Implement Queues using Stacks
  • Python Program to Implement Stack Using Two Queues
  • C++ Program to Implement Stack Using Two Queues
  • How can I most efficiently check for the existence of a single value in an array of thousands of values in PHP?
  • Array element moved by k using single moves?
  • How to implement Single Responsibility Principle using C#?
  • How to iterate efficiently through an array of integers of unknown size in C#
  • Implement multiple COUNT() in a single MySQL query
  • How to Use Customer Data Efficiently?
  • How to define a single-dimensional array in C Sharp?
  • Implement multiple LIKE operators in a single MySQL query
  • How to Map multi-dimensional arrays to a single array in java?
  • Single-Sign ON (SSO): How Does It Work, How to Implement, Advantages
  • Unable to implement $addToSet in MongoDB to fetch values of a single field?
Kickstart Your Career

Get certified by completing the course

Get Started

How to Efficiently Implement k Queues in a Single Array? (31)

Advertisements

';

How to Efficiently Implement k Queues in a Single Array? (2024)

FAQs

How to Efficiently Implement k Queues in a Single Array? ›

Approach 1: Implement K Queues in a Single Array

How to efficiently implement k queues in a single array in C? ›

A simple way to implement k queues is to divide the array in k slots of size n/k each, and fix the slots for different queues, i.e., use arr[0] to arr[n/k-1] for the first queue, and arr[n/k] to arr[2n/k-1] for queue2 where arr[] is the array to be used to implement two queues and size of array be n.

How to implement 3 stacks in one array? ›

For three stacks, following is required: An auxiliary array to maintain the parent for each node. Variables to store the current top of each stack. With these two in place, data from all the stacks can be interspersed in the original array and one can still do push/pop/size operations for all the stacks.

Why is linear implementation of queue using array inefficient? ›

Drawbacks of Queue Implementation Using Array

This is because all the elements in the array need to be shifted to add the new front element. In the array implementation of a queue, memory is allocated for the maximum size of the queue, even if the queue is not full. This can result in inefficient use of memory.

How is a queue implemented in an array? ›

To implement a queue using a simple array, create an array arr of size n and. take two variables front and rear which are initialized as 0 and -1 respectively. rear is the index up to which the elements are stored in the array including the rear index itself.

How to efficiently implement k queues in a single array in LeetCode? ›

It is always recommended to start with the simplest approach, the brute force approach, in an interview. A brute force solution for this problem is creating an array of size N and dividing it into k slots wherein each slot contains N/k elements. Use the array slots as follows: arr[0] to arr[N/k-1] for the first queue.

What is the most efficient way to implement priority queue? ›

Priority queue can be implemented using an array, a linked list, a heap data structure, or a binary search tree. Among these data structures, heap data structure provides an efficient implementation of priority queues.

Can we implement two stacks in a single array? ›

MAXSIZE] is used to implement two stacks. The two stacks grow from opposite ends of the array. Variables top1 and top2 (top1 < top2) point to the location of the topmost element in each of the stacks.

How many queues are required to implement a stack * 3? ›

A stack can be implemented using two queues.

How do I add multiple objects to a single array? ›

Here's an example of how to add multiple objects to an array:
  1. let myArray = [];
  2. let obj1 = { name: "John", age: 30 };
  3. let obj2 = { name: "Jane", age: 25 };
  4. let obj3 = { name: "Bob", age: 40 };
  5. myArray.push(obj1);
  6. myArray.push(obj2);
  7. myArray.push(obj3);
  8. console.log(myArray);
Aug 7, 2021

What is the major drawback of linear queue? ›

In a linear queue, the traversal through the queue is possible only once,i.e.,once an element is deleted, we cannot insert another element in its position. This disadvantage of a linear queue is overcome by a circular queue, thus saving memory.

What are the drawbacks of implementing queue using array? ›

Drawbacks of Queue Implementation Using Array

In Implementation of queue using array there is a wastage of memory. The available free space in the array can not be used for storing elements.

Why use queue instead of array? ›

Queues and stacks are dynamic while arrays are static. So when we require dynamic memory we use queue or stack over arrays. Stacks and queues are used over arrays when sequential access is required. To efficiently remove any data from the start (queue) or the end (stack) of a data structure.

What is the advantage of implementing a queue using an array? ›

Array-Based vs List-Based Queues:
PropertyArray-Based QueuesList-Based Queues
AdvantagesConstant Access Time, Efficient for Small QueuesDynamic Size, Efficient for Large Queues
DisadvantagesFixed Size, May Require Resizing, Inefficient for Large QueuesSlower Access Time, More Complex to Implement
5 more rows
May 2, 2023

How to implement priority queue using heap or array? ›

Heap-based implementation of a priority queue

To insert an element, you would add it to the end of the heap and then perform the necessary heap operations (such as swapping the element with its parent) to restore the heap property. To retrieve the highest priority element, you would simply return the root of the heap.

Is the queue FIFO or LIFO? ›

The primary difference between Stack and Queue Data Structures is that Stack follows LIFO while Queue follows FIFO data structure type.

How to implement multiple stacks using single array in C? ›

The idea to implement two stacks is to divide the array into two halves and assign two halves to two stacks, i.e., use arr[0] to arr[n/2] for stack1, and arr[(n/2) + 1] to arr[n-1] for stack2 where arr[] is the array to be used to implement two stacks and size of array be n.

How can you efficiently implement a circular queue using an array without wasting memory space? ›

Implement Circular Queue using Array:
  1. Initialize an array queue of size n, where n is the maximum number of elements that the queue can hold.
  2. Initialize two variables front and rear to -1.
  3. Enqueue: To enqueue an element x into the queue, do the following: ...
  4. Dequeue: To dequeue an element from the queue, do the following:
Jul 7, 2023

How to make a queue using array in C? ›

Implement Queue using Array in C
  1. Define a structure consisting of an array and two pointers front and rear.
  2. Initialize the array with MAX_SIZE.
  3. Initialize both the front and rear pointers to -1.
May 27, 2024

How to implement priority queue with array? ›

Array-based implementation of a priority queue:
  1. Create an array to store the elements of the priority queue.
  2. To insert an element into the priority queue, add the element to the end of the array.
  3. To remove the highest priority element (in a max heap) or the lowest priority element (in a min heap),
Mar 2, 2023

Top Articles
Latest Posts
Recommended Articles
Article information

Author: Roderick King

Last Updated:

Views: 5964

Rating: 4 / 5 (71 voted)

Reviews: 86% of readers found this page helpful

Author information

Name: Roderick King

Birthday: 1997-10-09

Address: 3782 Madge Knoll, East Dudley, MA 63913

Phone: +2521695290067

Job: Customer Sales Coordinator

Hobby: Gunsmithing, Embroidery, Parkour, Kitesurfing, Rock climbing, Sand art, Beekeeping

Introduction: My name is Roderick King, I am a cute, splendid, excited, perfect, gentle, funny, vivacious person who loves writing and wants to share my knowledge and understanding with you.