N-Queue using Array — Editorial

Opening the reading…

Intuitionthe array stores nodes, not permanently reserved queue segments

Each logical queue needs FIFO behavior, but the storage belongs to all queues together. Reserving a fixed segment for every queue would make one queue fail as soon as its segment is full, even when other segments are empty. Instead, treat every array position as a reusable node. A queue is represented by the index of its first node and the index of its last node.

The nodes belonging to one queue form a linked list through a next-index array. When you enqueue, take any available array position, write the value there, and link it after that queue's rear. When you dequeue, move the queue's front forward and put the removed position onto a separate free list. The physical positions may be unrelated, but the links preserve the logical order.

Logical queue links and the free-slot links share the same next array.

Approach

Create front and rear arrays of length n, initially set to -1, because an empty queue has no first or last node and each queue needs its own endpoints.

Create value and next arrays of length s, and link every slot to the following slot to form the initial free list; without this list, finding an unused shared position would require scanning the storage array.

Keep freeHead at the first unused slot. For an enqueue, fail immediately when freeHead is -1, because that means every shared slot is currently occupied.

Remove the slot at freeHead, advance freeHead to its next slot, store the new value, and set the new node's next index to -1 so an old free-list link cannot leak into the queue.

If the selected queue is empty, make the new slot both its front and rear; otherwise, link the current rear to the new slot and then update rear, because appending only at the rear preserves FIFO order.

For a dequeue, fail with -1 when the queue front is -1; otherwise save the front slot, advance front to its next node, and return the saved value.

When the dequeue leaves the queue empty, reset its rear to -1 as well, because a later enqueue must use the empty-queue path instead of linking through a removed node.

Add the removed slot to the front of the free list by setting next[slot] to freeHead and then moving freeHead to slot, so the storage becomes reusable in constant time.

Complexityevery operation follows a constant number of indices

MEASURE	BOUND	WHY
Time	O(q)	Each query performs only a fixed number of array reads, writes, and endpoint updates. No operation scans a queue, the free list, or the storage array, so the total work is proportional to the number of queries.
Space	O(n + s) extra	The front and rear arrays use O(n), while value and next use O(s). The returned answer strings are required output and are excluded from the auxiliary-space bound; the worst input shape can place all s occupied nodes in one queue, but no traversal is needed.

Here q is the number of queries, n is the number of queues, and s is the shared storage capacity.

Annotated solutionC++ · linked indices in one shared array

CPPUse one index-linked node array for all queues and one free list for reusable slots.

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    vector<string> processQueries(int n, int s, vector<vector<int>> queries) {
        vector<int> front(n, -1), rear(n, -1);
        vector<int> next(s, -1), value(s);

        for (int i = 0; i + 1 < s; ++i) {
            next[i] = i + 1;
        }
        int freeHead = (s == 0 ? -1 : 0);
        vector<string> answer;

        for (const vector<int>& query : queries) {
            if (query[0] == 1) {
                int x = query[1];
                int queueId = query[2] - 1;

                if (freeHead == -1) {
                    answer.push_back("False");
                    continue;
                }

                int slot = freeHead;
                freeHead = next[slot];
                value[slot] = x;
                next[slot] = -1;

                if (front[queueId] == -1) {
                    front[queueId] = slot;
                } else {
                    next[rear[queueId]] = slot;
                }
                rear[queueId] = slot;
                answer.push_back("True");
            } else {
                int queueId = query[1] - 1;

                if (front[queueId] == -1) {
                    answer.push_back("-1");
                    continue;
                }

                int slot = front[queueId];
                front[queueId] = next[slot];
                if (front[queueId] == -1) {
                    rear[queueId] = -1;
                }

                next[slot] = freeHead;
                freeHead = slot;
                answer.push_back(to_string(value[slot]));
            }
        }

        return answer;
    }
};

The line that clears next[slot] during enqueue separates two roles for the same array: before allocation, next[slot] belongs to the free list; after allocation, it belongs to a logical queue. The line that writes next[slot] = freeHead during dequeue performs the reverse transition. Keeping those transitions explicit prevents stale links from connecting unrelated structures.