如何在单个数组中高效地实现 k 个队列？

---

在某些情况下，我们需要实现我们自己的数据结构以获得更好的可用性和自定义。在这里，我们需要使用单个数组实现 K 个队列。

首先想到的解决方案是将数组分成 N/K 部分，并将数组的每一部分用作一个队列。这里，N 是数组长度。此解决方案的问题在于我们无法正确利用数组的空间。如果数组未满，但任何第 M 个队列索引已满，则无法将元素插入到第 M 个队列中。因此，我们需要一种优化的方案。

高效的方法使用循环数组来避免浪费数组空间。我们可以使用 next[] 数组将每个数组元素连接到下一个元素。因此，我们可以获得当前队列的下一个元素。如果我们想启动一个新队列，我们可以使用任何空闲槽来启动一个新队列。

问题陈述 - 我们得到一个长度为 N 的数组。我们需要在给定的数组中实现 K 个队列。

方法 1

此方法将使用 que_arr[] 存储队列元素。此外，我们将使用以下三个数组来跟踪队列元素。

• start[] = 用于存储每个队列的起始指针。

• last[] = 用于存储每个队列的最后一个指针。

• next[] = 用于存储每个队列的每个元素的下一个指针。

在这里，我们可以使用任何空闲槽来启动一个新队列，我们将在 next[] 数组中用 -1 表示空闲槽。此外，我们将实现检查队列是否为空或已满的功能。

算法

步骤 1 - 定义 'customQueue' 类。在 'customQueue' 类中，定义整数类型的 'que_arr'、'start'、'last' 和 'next' 指针。此外，定义 n 和 k 以存储数组长度、队列总数和 'freeslot' 变量以跟踪可用槽的下一个索引。

步骤 2 - 此外，在类中声明构造函数和方法。

步骤 3 - 接下来，定义类的成员函数。首先，我们将定义类的构造函数。

步骤 3.1 - 初始化 n 和 K 变量。此外，使用长度为 N 的数组初始化 que_arr 和 next 指针，并使用长度为 K 的数组初始化 start 和 last 指针。

步骤 3.2 - 将 start[] 数组的所有值更新为 -1，因为所有索引都可用于启动队列。此外，将 'freeSlot' 更新为 0。

步骤 3.3 - 接下来，将 next[p] 更新为 p + 1，以将每个元素与下一个元素连接起来。

步骤 4 - 现在，定义 enq() 成员函数以将元素插入到任何队列中。它将元素和队列号作为参数。

步骤 4.1 - 如果队列已满，则相应地打印消息。如果 freeSlot 值为 -1，则队列已满。

步骤 4.2 - 否则，将 'freeSlot' 值存储在 p 中以获取下一个空闲槽。

步骤 4.3 - 将 'freeSlot' 更新为 next[p]，表示当前槽的下一个指针。

步骤 4.4 - 如果队列为空，则将 start[q_num] 更新为 p。否则，将 next[last[q_num]] 更新为 p。

步骤 4.5 - 将 next[p] 更新为 -1。此外，将当前队列的最后一个指针更新为 'p'，并将给定元素添加到 que_arr 中的 'p' 索引处。

步骤 5 - 定义 deq() 函数以从任何队列中删除元素。

步骤 5.1 - 如果队列为空，则相应地打印消息。如果 start[q_num] 为 -1，我们可以说队列为空。

步骤 5.2 - 获取队列的起始指针，并将起始指针更新为下一个指针，因为我们需要删除队列的第一个元素。

步骤 5.3 - 将 next[p] 更新为 'freeslot' 值，并将 'freeslot' 更新为 p。

步骤 5.4 - 返回 que_arr[p] 元素。

步骤 6 - 在 main() 函数中，使用 enq() 方法将不同的值添加到不同的队列中。

步骤 7 - 之后，对每个队列执行 deq() 方法并观察输出。

示例

#include <iostream>
#include <climits>
using namespace std;

// Class to create a custom queue
class 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 n
customQueue::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;
}

输出

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

时间复杂度 - 入队和出队的 O(1)。

空间复杂度 - O(N) 用于存储队列中的元素。

使用循环数组实现的 K 个队列节省了空间，但我们需要完美地处理每个队列的起始、结束和下一个指针。否则，它可能会产生随机错误。

然而，它比朴素方法更复杂，但在实时开发中节省内存是最重要的。