如何在單個數組中高效地實現 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 個佇列節省了空間，但我們需要完美地處理每個佇列的起始、結束和下一個指標。否則，它可能會產生隨機錯誤。

然而，它比樸素方法更復雜，但在即時開發中節省記憶體是最重要的。