Queue Implementations (Array-based, Linked List-based)

Queue Implementations: Array-based vs. Linked List-based

Just as with stacks, queues can be implemented using either arrays or linked lists. However, the FIFO (First-In, First-Out) nature of queues introduces unique challenges and optimizations, particularly for array-based approaches. Understanding these differences is key to choosing the most efficient implementation for your needs.

---

1. Array-based Queue Implementation

Implementing a queue using a standard array requires careful consideration to maintain O(1) performance for both enqueue and dequeue operations.

The Challenge with Simple Arrays

If you use a basic JavaScript array (or similar dynamic array in other languages) and simply use push() for enqueue (adding to the end) and shift() for dequeue (removing from the beginning), you'll encounter a performance bottleneck:

• push() is O(1).
• shift() is O(N) because all remaining elements in the array have to be re-indexed (shifted) to fill the gap left by the removed element.

This O(N) dequeue operation makes a simple array-based queue inefficient for many use cases.

The Solution: Circular Array

To achieve O(1) for both enqueue and dequeue with an array, we use a circular array (or ring buffer). This technique treats the array as if its ends are connected, allowing elements to "wrap around."

• Concept:

  • We maintain two pointers: front (or headIndex) and rear (or tailIndex).
  • enqueue adds an element at rear and moves rear forward.
  • dequeue removes an element at front and moves front forward.
  • Both pointers move cyclically using the modulo (%) operator to wrap around when they reach the array's end.
  • The size of the queue is also tracked to differentiate between an empty and a full queue when front and rear point to the same index.

• Illustration:

  Array (Capacity 5): [ _ , _ , _ , _ , _ ]
  Front: 0, Rear: 0, Size: 0
  
  Enqueue(A): [ A , _ , _ , _ , _ ]
  Front: 0, Rear: 1, Size: 1
  
  Enqueue(B): [ A , B , _ , _ , _ ]
  Front: 0, Rear: 2, Size: 2
  
  Dequeue(): (returns A) [ _ , B , _ , _ , _ ]
  Front: 1, Rear: 2, Size: 1
  
  Enqueue(C): [ _ , B , C , _ , _ ]
  Front: 1, Rear: 3, Size: 2
  
  Enqueue(D): [ _ , B , C , D , _ ]
  Front: 1, Rear: 4, Size: 3
  
  Enqueue(E): (wraps around) [ E , B , C , D , _ ]
  Front: 1, Rear: 0 (after modulo), Size: 4
  

• JavaScript Example (Conceptual Circular Array Logic):

  class CircularArrayQueue {
    constructor(capacity) {
      this.capacity = capacity;
      this.items = new Array(capacity); // Pre-allocate array
      this.front = 0; // Index of the front element
      this.rear = 0;  // Index where the next element will be inserted
      this.size = 0;
    }
  
    enqueue(element) {
      if (this.isFull()) {
        console.log("Queue is full!");
        return false;
      }
      this.items[this.rear] = element;
      this.rear = (this.rear + 1) % this.capacity; // Move rear, wrap around
      this.size++;
      return true;
    }
  
    dequeue() {
      if (this.isEmpty()) {
        console.log("Queue is empty!");
        return null;
      }
      const element = this.items[this.front];
      this.items[this.front] = undefined; // Optional: clear the spot
      this.front = (this.front + 1) % this.capacity; // Move front, wrap around
      this.size--;
      return element;
    }
  
    peek() {
      if (this.isEmpty()) {
        return null;
      }
      return this.items[this.front];
    }
  
    isEmpty() {
      return this.size === 0;
    }
  
    isFull() {
      return this.size === this.capacity;
    }
  
    getSize() {
      return this.size;
    }
  
    printQueue() {
      let str = "";
      if (this.isEmpty()) {
        console.log("Queue is empty.");
        return;
      }
      let current = this.front;
      for (let i = 0; i < this.size; i++) {
        str += this.items[current] + " ";
        current = (current + 1) % this.capacity;
      }
      console.log(str.trim());
    }
  }
  
  // Example Usage:
  const q = new CircularArrayQueue(3);
  q.enqueue(10); // [10, _, _] front=0, rear=1
  q.enqueue(20); // [10, 20, _] front=0, rear=2
  q.printQueue(); // 10 20
  console.log("Dequeued:", q.dequeue()); // Dequeued: 10. Queue: [_, 20, _] front=1, rear=2
  q.enqueue(30); // [30, 20, _] (wrapped around if capacity reached) -> actually [_, 20, 30] front=1, rear=0 (conceptually)
  q.printQueue(); // 20 30
  q.enqueue(40); // Queue is full, as size becomes 3. (If capacity 3: [40, 20, 30] front=1, rear=1 (full))
  q.printQueue(); // 20 30 (because 40 wasn't added if full check is strict)
  

• Time Complexity (Circular Array):

  • enqueue(): O(1)
  • dequeue(): O(1)
  • peek(), isEmpty(), isFull(), getSize(): O(1)

• Advantages:

  • Memory Efficiency: No overhead for pointers per element.
  • Cache Locality: Elements are stored contiguously.
  • Constant Time Operations: Achieves O(1) for all primary operations.

• Disadvantages:

  • Fixed Size: Typically requires a predefined capacity. If the queue tries to exceed its capacity, it will "overflow" unless a resizing mechanism (which adds O(N) complexity) is implemented.
  • Implementation Complexity: More complex to implement correctly than using built-in array methods for stacks or a linked list, especially managing front, rear, and size for edge cases (empty, full).

---

2. Linked List-based Queue Implementation

A linked list provides a natural and flexible way to implement a queue, as it easily supports additions at one end and removals from the other without complex indexing or shifting.

• Concept:

  • We maintain two pointers: front (pointing to the head of the list) and rear (pointing to the tail of the list).
  • enqueue adds a new node at the rear.
  • dequeue removes the node at the front.

• Illustration:

  Empty Queue: Front -> null, Rear -> null
  
  Enqueue(A): A (Front -> A, Rear -> A)
  
  Enqueue(B): A -> B (Front -> A, Rear -> B)
  
  Enqueue(C): A -> B -> C (Front -> A, Rear -> C)
  
  Dequeue(): (removes A) B -> C (Front -> B, Rear -> C)
  

• JavaScript Example:

  class Node {
    constructor(value) {
      this.value = value;
      this.next = null;
    }
  }
  
  class LinkedListQueue {
    constructor() {
      this.front = null; // Head of the list
      this.rear = null;  // Tail of the list
      this.size = 0;
    }
  
    enqueue(element) {
      const newNode = new Node(element);
      if (this.isEmpty()) {
        this.front = newNode;
        this.rear = newNode;
      } else {
        this.rear.next = newNode; // Old rear points to new node
        this.rear = newNode;     // New node becomes the new rear
      }
      this.size++;
    }
  
    dequeue() {
      if (this.isEmpty()) {
        console.log("Queue is empty!");
        return null;
      }
      const removedValue = this.front.value;
      this.front = this.front.next; // Move front to the next node
  
      if (this.front === null) {
        // If the last element was removed, rear also becomes null
        this.rear = null;
      }
      this.size--;
      return removedValue;
    }
  
    peek() {
      if (this.isEmpty()) {
        return null;
      }
      return this.front.value;
    }
  
    isEmpty() {
      return this.size === 0; // Or this.front === null
    }
  
    getSize() {
      return this.size;
    }
  
    printQueue() {
      let current = this.front;
      let str = "";
      while (current) {
        str += current.value + " ";
        current = current.next;
      }
      console.log(str.trim());
    }
  }
  
  // Example Usage:
  const llq = new LinkedListQueue();
  llq.enqueue('Task A');
  llq.enqueue('Task B');
  llq.printQueue(); // Task A Task B
  console.log("Next task:", llq.peek()); // Next task: Task A
  console.log("Processing:", llq.dequeue()); // Processing: Task A
  llq.printQueue(); // Task B
  llq.enqueue('Task C');
  llq.printQueue(); // Task B Task C
  

• Time Complexity:

  • enqueue(): O(1)
  • dequeue(): O(1)
  • peek(), isEmpty(), getSize(): O(1)

• Advantages:

  • Dynamic Size: Naturally grows and shrinks as needed without fixed capacity limits or resizing overhead.
  • No Shifting: Elements are not shifted in memory, avoiding O(N) operations.

• Disadvantages:

  • Memory Overhead: Each element (node) requires extra memory for its next pointer, which can be significant for queues storing many small elements.
  • Cache Performance: Less favorable cache performance compared to contiguous array storage.

---

3. Choosing the Right Implementation

The best choice for a queue implementation depends on the specific requirements of your application:

Feature	Array-based Queue (Circular)	Linked List-based Queue
Size	Fixed capacity (unless resized)	Dynamic, grows/shrinks naturally
Memory	More efficient per element	Higher overhead per element
Performance	O(1) for all ops; good cache locality	O(1) for all ops; poorer cache
Use Case	When max queue size is known/bounded	When queue size is unpredictable
Complexity	More complex pointer logic (%)	Simpler to manage front/rear

In JavaScript, where arrays are dynamic and optimized for many operations, you might sometimes see queues implemented using just push() and shift(). However, be aware of the O(N) performance for shift() with large queues. For true O(1) operations across the board, especially if the queue can become very large and frequent dequeue operations are expected:

• A custom circular array implementation is best for fixed-size scenarios where efficiency is paramount.
• A custom linked list implementation is ideal when the queue size is highly dynamic and unpredictable.

For most typical applications where the queue won't grow astronomically large or where dequeue isn't exceptionally frequent, even a dynamic array (using push and shift for simplicity or a custom front pointer and then periodically cleaning/splicing) might suffice, but understanding the O(N) implications is crucial.

---