Typescript Data Structure: Queue

TypeScript queues, unlike their LIFO (Last-in-First-out) cousins the stacks, operate on a "First-in-First-out" (FIFO) principle. Imagine them as orderly lines where the person (or data element) at the front is served first.

Building a Basic Queue

class Queue<T> { private data: T[]; constructor() { this.data = []; } enqueue(element: T): void { this.data.push(element); } dequeue(): T undefined { return this.data.shift(); } peek(): T undefined { return this.data[0]; } isEmpty(): boolean { return this.data.length === 0; } } const myQueue = new Queue<number>(); myQueue.enqueue(10); myQueue.enqueue(20); myQueue.enqueue(30); console.log(myQueue.dequeue()); // Outputs: 10 console.log(myQueue.peek()); // Outputs: 20 console.log(myQueue.isEmpty()); // Outputs: false

This example demonstrates a basic queue implementation using an array and class with methods for enqueuing (adding to the back), dequeuing (removing from the front), peeking, and checking emptiness. We again utilize a generic type T for flexibility.

Practical Applications of Queues

Task Scheduling

Queues are used in task scheduling systems, where tasks are added to a queue and processed in the order they are received.

Breadth-First Search (BFS)

In graph algorithms, queues are fundamental for performing breadth-first searches. Nodes are explored level by level, and the queue ensures that nodes at the same level are processed before moving deeper into the graph.

Print Queue

In printing systems, documents are typically processed in the order they are sent to the printer. A queue ensures fairness in document printing.

Message Queues

Queues are frequently used in message-driven architectures where messages are produced by one part of the system and consumed by another. This ensures that messages are processed in the order they are received.

class MessageQueue<T> { private messages: T[] = []; enqueue(message: T): void { this.messages.push(message); } dequeue(): T undefined { return this.messages.shift(); } peek(): T undefined { return this.messages[0]; } isEmpty(): boolean { return this.messages.length === 0; } } // Example usage: const messageQueue = new MessageQueue<string>(); messageQueue.enqueue("Hello"); messageQueue.enqueue("World"); console.log(messageQueue.dequeue()); // Outputs: "Hello" console.log(messageQueue.peek()); // Outputs: "World" Using Generics and Advanced Implementation interface Customer { name: string; arrivalTime: number; } const serviceQueue: Customer[] = []; function serveCustomer(customer: Customer): void { // Simulate service time console.log(`Serving customer ${customer.name}`); const serviceTime = Math.random() * 5; // Random service time in seconds setTimeout(() => console.log(`Finished serving ${customer.name}`), serviceTime * 1000); } serviceQueue.push({ name: "John", arrivalTime: 0 }); serviceQueue.push({ name: "Alice", arrivalTime: 2 }); serviceQueue.push({ name: "Bob", arrivalTime: 5 }); while (serviceQueue.length > 0) { const customer = serviceQueue.shift(); if (customer) { console.log(`Now serving: ${customer.name} (arrived at ${customer.arrivalTime})`); serveCustomer(customer); } }

This example showcases a more complex queue application, managing customer service with arrival times and dynamic processing. We again use generics for the Customer interface and demonstrate iterating through the queue while serving customers in the FIFO order they arrived.

Combining Queues with Other Data Structures

Queues can be used alongside stacks for implementing undo/redo functionality, where undone actions are pushed onto a stack and redoing pops them back into the queue for processing.

Queues can be used with priority queues, where elements with higher priority are served first, enabling differentiated handling of urgent tasks.

Conclusion

Queues in TypeScript provide an effective way to manage data with a First-In-First-Out order. They are crucial in scenarios where maintaining order is essential, such as task scheduling, breadth-first search algorithms, and message-driven systems. TypeScript's type system enhances the safety and clarity of queue implementations.






Related Topics
  1. TypeScript Stack
  2. TypeScript Set
  3. TypeScript Map
  4. TypeScript Linked List
  1. Typescript Tree