Exploring Queue Data Structure in TypeScript: Implementation and Applications

A queue is first-in, first-out. Think of a line at a coffee shop. The first person in line gets served first. No cutting.

That FIFO behavior makes queues essential for anything that processes items in order: task schedulers, message brokers, breadth-first search, print spoolers.

Implementation

class Queue<T> {
  private items: T[];

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

  enqueue(item: T): void {
    this.items.push(item);
  }

  dequeue(): T | undefined {
    return this.items.shift();
  }

  peek(): T | undefined {
    return this.items[0];
  }

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

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

enqueue adds to the back. dequeue removes from the front. peek looks at the front without removing.

The Performance Problem

This implementation uses an array. push is O(1). But shift is O(n) because it moves every remaining element forward by one position.

For small queues, this doesn't matter. For high-throughput systems processing millions of items, it does. A proper implementation uses a linked list or a circular buffer to achieve O(1) for both operations:

class EfficientQueue<T> {
  private items: Map<number, T>;
  private head: number;
  private tail: number;

  constructor() {
    this.items = new Map();
    this.head = 0;
    this.tail = 0;
  }

  enqueue(item: T): void {
    this.items.set(this.tail, item);
    this.tail++;
  }

  dequeue(): T | undefined {
    if (this.isEmpty()) return undefined;
    const item = this.items.get(this.head);
    this.items.delete(this.head);
    this.head++;
    return item;
  }

  peek(): T | undefined {
    return this.items.get(this.head);
  }

  isEmpty(): boolean {
    return this.head === this.tail;
  }

  size(): number {
    return this.tail - this.head;
  }
}

This version uses a Map with head/tail pointers. Both enqueue and dequeue are O(1).

Where Queues Show Up

• Task scheduling: Operating systems use queues to manage CPU time. Processes wait in a queue for their turn.
• BFS traversal: Breadth-first search explores graph nodes level by level using a queue. Each level's neighbors are enqueued for the next iteration.
• Message queues: Systems like RabbitMQ, SQS, and Kafka are sophisticated queues. Producers enqueue messages, consumers dequeue them. This decouples services and handles load spikes.
• Rate limiting: Queue incoming requests and process them at a controlled rate.
• Print spoolers: Documents queue up and print in order.

Variations

Priority Queue: Elements have priorities. Higher-priority items dequeue first regardless of arrival order. Typically implemented with a heap, not a simple queue.

Double-ended Queue (Deque): Supports insertion and removal at both ends. Useful when you need both stack and queue behavior.

The queue is one of the simplest data structures, but it underpins some of the most important patterns in distributed systems. Message queues alone are responsible for keeping half the internet running.