Aufgabenwarteschlangen in TypeScript: Vollständiger Leitfaden für Anfänger

Einführung in Aufgabenwarteschlangen in TypeScript

Eine Aufgabenwarteschlange (Queue) ist eine der grundlegenden Datenstrukturen in der Programmierung, die nach dem FIFO-Prinzip (First In, First Out – „Wer zuerst kommt, mahlt zuerst") arbeitet. Stellen Sie sich eine normale Schlange im Geschäft vor: Der erste Kunde, der sich anstellt, wird zuerst bedient. In der Programmierung wird die Aufgabenwarteschlange überall eingesetzt: von der Verarbeitung von Anfragen auf dem Server bis zur Verwaltung asynchroner Operationen im Browser.

In diesem Artikel werden wir uns ansehen, wie man eine Aufgabenwarteschlange in TypeScript erstellt und verwendet. Sie erfahren, wie Sie die Warteschlange typisieren, die grundlegenden Methoden implementieren und sie in realen Projekten anwenden. Das Material richtet sich an Anfänger-Entwickler, die mit den Grundlagen von TypeScript vertraut sind.

Grundlegende Operationen mit der Warteschlange

Jede Aufgabenwarteschlange sollte mehrere grundlegende Operationen unterstützen:

• enqueue (Element am Ende der Warteschlange hinzufügen);
• dequeue (Element vom Anfang der Warteschlange entfernen);
• peek (das erste Element ansehen, ohne es zu entfernen);
• isEmpty (prüfen, ob die Warteschlange leer ist);
• size (die Anzahl der Elemente ermitteln).

In TypeScript können wir eine Warteschlange basierend auf einem Array oder einer verketteten Liste implementieren. Der Einfachheit halber beginnen wir mit einem Array.

Implementierung einer Warteschlange basierend auf einem Array

Erstellen wir eine Klasse Queue<T> mit Generics – dies ermöglicht das Speichern von Daten beliebigen Typs:

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

    // Element am Ende der Warteschlange hinzufügen    enqueue(element: T): void {        this.items.push(element);    }

    // Erstes Element entfernen und zurückgeben    dequeue(): T | undefined {        return this.items.shift();    }

    // Erstes Element ansehen, ohne es zu entfernen    peek(): T | undefined {        return this.items[0];    }

    // Prüfen, ob die Warteschlange leer ist    isEmpty(): boolean {        return this.items.length === 0;    }

    // Größe der Warteschlange abrufen    size(): number {        return this.items.length;    }}

Jetzt können wir eine Warteschlange für beliebige Datentypen erstellen:

// Warteschlange von Zeichenkettenconst stringQueue = new Queue<string>();stringQueue.enqueue('Aufgabe 1');stringQueue.enqueue('Aufgabe 2');console.log(stringQueue.dequeue()); // 'Aufgabe 1'

// Warteschlange von Zahlenconst numberQueue = new Queue<number>();numberQueue.enqueue(10);numberQueue.enqueue(20);console.log(numberQueue.peek()); // 10

Nachteile der Array-Implementierung

Die Methode shift() in JavaScript/TypeScript hat eine Komplexität von O(n), da nach dem Entfernen des ersten Elements alle anderen verschoben werden. Für große Datenmengen ist dies ineffizient. Die Lösung besteht darin, eine Warteschlange basierend auf einem Objekt oder einer verketteten Liste zu implementieren.

Optimierte Warteschlange mit einem Objekt

Um das Verschieben von Elementen zu vermeiden, speichern wir die Elemente in einem Objekt und verfolgen die Indizes von Anfang und Ende:

class OptimizedQueue<T> {    private items: Record<number, T> = {};    private head: number = 0;    private tail: number = 0;

    enqueue(element: T): void {        this.items[this.tail] = element;        this.tail++;    }

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

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

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

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

Jetzt werden die Operationen enqueue und dequeue in O(1) ausgeführt – konstanter Zeitaufwand, unabhängig