Multiple Queue

What is a Multiple Queue?

A Multiple Queue is a data structure that consists of several individual queues managed together. This approach allows for better organization of data with different priorities or categories while maintaining the standard FIFO (First-In-First-Out) property within each individual queue.

Key Characteristics

Multiple queues have these fundamental properties:

  1. Multiple FIFO structures: Contains several independent queues
  2. Priority management: Queues can represent different priority levels
  3. Flexible operations:
    • enqueue(item, queueNum) - Add to specific queue
    • dequeue(queueNum) - Remove from specific queue
    • multiDequeue() - Remove following priority rules
  4. Dynamic allocation: Queues can grow/shrink independently

Visual Example

Operation sequence with 3 queues:

  1. enqueue(A, 0): Queue0 [A] | Queue1 [] | Queue2 []
  2. enqueue(B, 1): Queue0 [A] | Queue1 [B] | Queue2 []
  3. enqueue(C, 0): Queue0 [A, C] | Queue1 [B] | Queue2 []
  4. dequeue(0): Returns A → Queue0 [C] | Queue1 [B] | Queue2 []
  5. enqueue(D, 2): Queue0 [C] | Queue1 [B] | Queue2 [D]
  6. multiDequeue(): Returns B (higher priority) → Queue0 [C] | Queue1 [] | Queue2 [D]

Implementation Variations

Common implementation approaches:

  1. Array of Queues:
    • Fixed number of queues
    • Simple to implement
    • Static memory allocation
  2. Dynamic Array of Linked Lists:
    • Flexible queue sizes
    • Efficient memory usage
    • More complex implementation
  3. Priority-based Implementation:
    • Queues represent priority levels
    • Automatic routing of dequeue operations

Time Complexity

  • enqueue(item, queueNum): O(1)
  • dequeue(queueNum): O(1)
  • multiDequeue(): O(k) where k is number of queues
  • peek(queueNum): O(1)
  • isEmpty(queueNum): O(1)

Applications

Multiple queues are used in:

  • Operating Systems: Process scheduling with multiple priority levels
  • Network Traffic Management: Different queues for different packet types
  • Print Spooling: Separate queues for different printer priorities
  • Customer Service Systems: VIP vs regular customer queues
  • Multi-level Feedback Queues: Adaptive scheduling algorithms

Special Cases

Interesting multiple queue variations:

  • Priority Multi-Queue: Automatic dequeue from highest priority non-empty queue
  • Dynamic Multi-Queue: Queues can be added/removed at runtime
  • Bounded Multi-Queue: Each queue has individual capacity limits
  • Inter-Queue Transfer: Items can move between queues under certain conditions

The multiple queue structure provides an efficient way to manage categorized or prioritized data streams while maintaining the simplicity of FIFO operations within each category. Its versatility makes it particularly valuable in systems where different types of data or requests need separate but coordinated handling.

Visualize Multiple Queue (Deque) Operations with Animations

Deque is empty
FrontRear
Deque is empty

Test Your Knowledge before moving forward!

Queue Quiz Challenge

How it works:

  • +1 point for each correct answer
  • 0 points for wrong answers
  • -0.5 point penalty for viewing explanations
  • Earn stars based on your final score (max 5 stars)

Multiple Queue Implementation

// Multiple Queue Implementation in JavaScript
class MultiQueue {
  constructor(numQueues, sizePerQueue) {
    this.queues = Array(numQueues).fill().map(() => ({
      items: Array(sizePerQueue),
      front: -1,
      rear: -1,
      size: 0,
      capacity: sizePerQueue
    }));
  }

  // Enqueue to specific queue
  enqueue(queueIndex, item) {
    if (this.isFull(queueIndex)) {
      return false;
    }
    const queue = this.queues[queueIndex];
    if (queue.front === -1) {
      queue.front = 0;
    }
    queue.rear = (queue.rear + 1) % queue.capacity;
    queue.items[queue.rear] = item;
    queue.size++;
    return true;
  }

  // Dequeue from specific queue
  dequeue(queueIndex) {
    if (this.isEmpty(queueIndex)) {
      return null;
    }
    const queue = this.queues[queueIndex];
    const item = queue.items[queue.front];
    if (queue.front === queue.rear) {
      queue.front = queue.rear = -1;
    } else {
      queue.front = (queue.front + 1) % queue.capacity;
    }
    queue.size--;
    return item;
  }

  // Check if specific queue is empty
  isEmpty(queueIndex) {
    return this.queues[queueIndex].size === 0;
  }

  // Check if specific queue is full
  isFull(queueIndex) {
    return this.queues[queueIndex].size === this.queues[queueIndex].capacity;
  }

  // Peek at front of specific queue
  peek(queueIndex) {
    if (this.isEmpty(queueIndex)) {
      return null;
    }
    return this.queues[queueIndex].items[this.queues[queueIndex].front];
  }
}

// Usage
const mq = new MultiQueue(3, 5); // 3 queues, each with capacity 5
mq.enqueue(0, 10); // Add to queue 0
mq.enqueue(1, 20); // Add to queue 1
console.log(mq.dequeue(0)); // 10
console.log(mq.peek(1));    // 20

Explore Other Types

Single Ended Queue

Circular Queue

Double Ended Queue

Priority Queue