Data Structures Series #2: Queue - Implementation & Use Cases

Introduction

Welcome back to my tech blog series on data structures! Today, we're diving into Queues, another fundamental data structure that follows the First In, First Out (FIFO) principle. We'll implement queues in JavaScript, explore practical examples, and see how they power real-world applications.

---

What is a Queue?

A Queue is a linear data structure that follows the First In, First Out (FIFO) principle, meaning the first item added is the first one to be removed. Think of a line at a coffee shop—the first person in line gets served first, and new customers join at the back.

Key Operations in a Queue:

1. Enqueue – Adds an element to the rear (back) of the queue.
2. Dequeue – Removes an element from the front of the queue.
3. Front – Returns the front element without removing it.
4. Rear – Returns the rear element without removing it.
5. isEmpty – Checks if the queue is empty.
6. Size – Returns the number of elements in the queue.

---

Implementing a Queue in JavaScript

1. Using an Array (Simple but Inefficient)

While arrays can implement queues using push() and shift() methods, this approach has O(n) time complexity for dequeue operations due to array shifting.

class Queue {
  constructor() {
    this.items = [];
  }

  enqueue(element) {
    this.items.push(element);
  }

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items.shift(); // O(n) operation
  }

  front() {
    return this.isEmpty() ? null : this.items[0];
  }

  rear() {
    return this.isEmpty() ? null : this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

// Usage example
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.front()); // 10
console.log(queue.dequeue()); // 10
console.log(queue.size()); // 2

2. Using Two Pointers (Optimized Array Approach)

This approach maintains front and rear pointers to avoid the shifting overhead, providing O(1) operations.

class Queue {
  constructor() {
    this.items = [];
    this.frontIndex = 0;
    this.rearIndex = 0;
  }

  enqueue(element) {
    this.items[this.rearIndex] = element;
    this.rearIndex++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }
    const item = this.items[this.frontIndex];
    delete this.items[this.frontIndex];
    this.frontIndex++;

    // Reset indices when queue becomes empty
    if (this.frontIndex === this.rearIndex) {
      this.frontIndex = 0;
      this.rearIndex = 0;
    }

    return item;
  }

  front() {
    return this.isEmpty() ? null : this.items[this.frontIndex];
  }

  rear() {
    return this.isEmpty() ? null : this.items[this.rearIndex - 1];
  }

  isEmpty() {
    return this.frontIndex === this.rearIndex;
  }

  size() {
    return this.rearIndex - this.frontIndex;
  }
}

3. Using a Linked List (Most Efficient)

Linked list implementation provides O(1) operations for both enqueue and dequeue without memory waste.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.length = 0;
  }

  enqueue(value) {
    const newNode = new Node(value);

    if (this.isEmpty()) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }

    this.length++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }

    const dequeuedValue = this.front.value;
    this.front = this.front.next;

    if (!this.front) {
      this.rear = null; // Queue is now empty
    }

    this.length--;
    return dequeuedValue;
  }

  frontValue() {
    return this.isEmpty() ? null : this.front.value;
  }

  rearValue() {
    return this.isEmpty() ? null : this.rear.value;
  }

  isEmpty() {
    return this.length === 0;
  }

  size() {
    return this.length;
  }
}

// Usage example
const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
console.log(queue.frontValue()); // 10
console.log(queue.dequeue()); // 10
console.log(queue.size()); // 2

---

Real-World Use Cases of Queues

1. Print Queue Management

Printers use queues to manage print jobs in the order they were received.

class PrintQueue {
  constructor() {
    this.queue = new Queue();
  }

  addPrintJob(document) {
    this.queue.enqueue({
      document,
      timestamp: new Date(),
      id: Math.random().toString(36).substr(2, 9)
    });
    console.log(`Print job added: ${document}`);
  }

  processPrintJob() {
    const job = this.queue.dequeue();
    if (job) {
      console.log(`Printing: ${job.document} (Added: ${job.timestamp})`);
      return job;
    }
    console.log('No print jobs in queue');
    return null;
  }

  getPendingJobs() {
    return this.queue.size();
  }
}

// Usage
const printer = new PrintQueue();
printer.addPrintJob('Report.pdf');
printer.addPrintJob('Invoice.docx');
printer.processPrintJob(); // Prints: Report.pdf

2. Breadth-First Search (BFS) in Graphs

BFS algorithm uses a queue to explore nodes level by level.

class Graph {
  constructor() {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  addEdge(v1, v2) {
    this.adjacencyList[v1].push(v2);
    this.adjacencyList[v2].push(v1);
  }

  bfs(start) {
    const queue = new Queue();
    const visited = {};
    const result = [];

    queue.enqueue(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
      const vertex = queue.dequeue();
      result.push(vertex);

      this.adjacencyList[vertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.enqueue(neighbor);
        }
      });
    }

    return result;
  }
}

// Usage
const graph = new Graph();
['A', 'B', 'C', 'D', 'E'].forEach(v => graph.addVertex(v));
graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');

console.log(graph.bfs('A')); // ['A', 'B', 'C', 'D', 'E']

3. Task Scheduling and Job Processing

Operating systems and web servers use queues for task scheduling and processing requests.

class TaskScheduler {
  constructor() {
    this.taskQueue = new Queue();
    this.isProcessing = false;
  }

  addTask(task) {
    this.taskQueue.enqueue({
      id: Math.random().toString(36).substr(2, 9),
      task,
      addedAt: Date.now()
    });

    if (!this.isProcessing) {
      this.processNextTask();
    }
  }

  async processNextTask() {
    if (this.taskQueue.isEmpty()) {
      this.isProcessing = false;
      return;
    }

    this.isProcessing = true;
    const taskItem = this.taskQueue.dequeue();

    console.log(`Processing task: ${taskItem.id}`);

    try {
      await taskItem.task();
      console.log(`Task completed: ${taskItem.id}`);
    } catch (error) {
      console.error(`Task failed: ${taskItem.id}`, error);
    }

    // Process next task
    setTimeout(() => this.processNextTask(), 100);
  }

  getPendingTasks() {
    return this.taskQueue.size();
  }
}

// Usage
const scheduler = new TaskScheduler();

scheduler.addTask(() => new Promise(resolve => {
  setTimeout(() => {
    console.log('Sending email...');
    resolve();
  }, 1000);
}));

scheduler.addTask(() => new Promise(resolve => {
  setTimeout(() => {
    console.log('Processing payment...');
    resolve();
  }, 500);
}));

4. Buffer for Data Streams

Queues act as buffers in streaming applications, handling data flow between producers and consumers.

class StreamBuffer {
  constructor(maxSize = 10) {
    this.buffer = new Queue();
    this.maxSize = maxSize;
    this.consumers = [];
  }

  // Producer adds data
  produce(data) {
    if (this.buffer.size() >= this.maxSize) {
      console.log('Buffer full, dropping oldest data');
      this.buffer.dequeue(); // Drop oldest
    }

    this.buffer.enqueue({
      data,
      timestamp: Date.now()
    });

    this.notifyConsumers();
  }

  // Consumer subscribes to data
  subscribe(callback) {
    this.consumers.push(callback);
  }

  notifyConsumers() {
    if (!this.buffer.isEmpty()) {
      const item = this.buffer.dequeue();
      this.consumers.forEach(callback => callback(item));
    }
  }

  getBufferStatus() {
    return {
      size: this.buffer.size(),
      maxSize: this.maxSize,
      utilization: (this.buffer.size() / this.maxSize * 100).toFixed(1) + '%'
    };
  }
}

// Usage
const streamBuffer = new StreamBuffer(5);

// Subscribe a consumer
streamBuffer.subscribe(item => {
  console.log(`Consuming: ${item.data} (${new Date(item.timestamp)})`);
});

// Produce data
setInterval(() => {
  streamBuffer.produce(`Data packet ${Math.floor(Math.random() * 100)}`);
}, 2000);

5. Web Server Request Handling

Web servers use queues to manage incoming HTTP requests during high traffic.

class WebServerQueue {
  constructor(maxConcurrent = 3) {
    this.requestQueue = new Queue();
    this.activeRequests = 0;
    this.maxConcurrent = maxConcurrent;
  }

  handleRequest(request) {
    this.requestQueue.enqueue({
      ...request,
      receivedAt: Date.now(),
      id: Math.random().toString(36).substr(2, 9)
    });

    this.processQueue();
  }

  async processQueue() {
    if (this.activeRequests >= this.maxConcurrent || this.requestQueue.isEmpty()) {
      return;
    }

    this.activeRequests++;
    const request = this.requestQueue.dequeue();

    console.log(`Processing request ${request.id}: ${request.method} ${request.url}`);

    try {
      // Simulate request processing
      await new Promise(resolve => setTimeout(resolve, Math.random() * 2000));
      console.log(`Request ${request.id} completed successfully`);
    } catch (error) {
      console.error(`Request ${request.id} failed:`, error);
    } finally {
      this.activeRequests--;
      this.processQueue(); // Process next request
    }
  }

  getQueueStatus() {
    return {
      pending: this.requestQueue.size(),
      active: this.activeRequests,
      maxConcurrent: this.maxConcurrent
    };
  }
}

// Usage
const server = new WebServerQueue(2);

// Simulate incoming requests
const requests = [
  { method: 'GET', url: '/api/users' },
  { method: 'POST', url: '/api/orders' },
  { method: 'GET', url: '/api/products' },
  { method: 'PUT', url: '/api/users/123' },
  { method: 'DELETE', url: '/api/orders/456' }
];

requests.forEach((req, index) => {
  setTimeout(() => server.handleRequest(req), index * 500);
});

---

Queue Variants

Circular Queue

A circular queue uses a fixed-size array where the rear wraps around to the beginning when it reaches the end.

class CircularQueue {
  constructor(size) {
    this.items = new Array(size);
    this.maxSize = size;
    this.front = -1;
    this.rear = -1;
    this.currentSize = 0;
  }

  enqueue(element) {
    if (this.isFull()) {
      throw new Error('Queue is full');
    }

    if (this.isEmpty()) {
      this.front = 0;
      this.rear = 0;
    } else {
      this.rear = (this.rear + 1) % this.maxSize;
    }

    this.items[this.rear] = element;
    this.currentSize++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }

    const item = this.items[this.front];
    this.items[this.front] = null;

    if (this.currentSize === 1) {
      this.front = -1;
      this.rear = -1;
    } else {
      this.front = (this.front + 1) % this.maxSize;
    }

    this.currentSize--;
    return item;
  }

  isFull() {
    return this.currentSize === this.maxSize;
  }

  isEmpty() {
    return this.currentSize === 0;
  }

  size() {
    return this.currentSize;
  }
}

Priority Queue

A priority queue where elements are dequeued based on priority rather than insertion order.

class PriorityQueue {
  constructor() {
    this.items = [];
  }

  enqueue(element, priority) {
    const queueElement = { element, priority };
    let added = false;

    for (let i = 0; i < this.items.length; i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }

    if (!added) {
      this.items.push(queueElement);
    }
  }

  dequeue() {
    return this.isEmpty() ? null : this.items.shift().element;
  }

  front() {
    return this.isEmpty() ? null : this.items[0].element;
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

// Usage - Lower numbers have higher priority
const pq = new PriorityQueue();
pq.enqueue('Low priority task', 3);
pq.enqueue('High priority task', 1);
pq.enqueue('Medium priority task', 2);

console.log(pq.dequeue()); // 'High priority task'
console.log(pq.dequeue()); // 'Medium priority task'

---

Time and Space Complexity

Operation	Array (Simple)	Array (Two Pointers)	Linked List
Enqueue	O(1)	O(1)	O(1)
Dequeue	O(n)	O(1)	O(1)
Front	O(1)	O(1)	O(1)
Space	O(n)	O(n)	O(n)

Best Implementation: Linked List provides the most consistent O(1) performance for all operations.

---

Conclusion

Queues are essential data structures that power many real-world applications, from task scheduling and web server request handling to graph algorithms and data streaming. Understanding their FIFO behavior and various implementations will help you choose the right approach for your specific use case.

The key takeaways:

• Use linked list implementation for optimal performance
• Circular queues for fixed-size scenarios
• Priority queues when order matters more than insertion time
• Queues excel in producer-consumer patterns and breadth-first processing

Stay tuned for the next post in this series, where we'll explore Binary Trees!

---

🔗 Connect with Me

If you found this post helpful, follow me on Dev.to for more insights on data structures and algorithms!

---