1. Eine Warteschlange kann als geordnete Liste definiert werden, die die Ausführung von Einfügevorgängen an einem aufgerufenen Ende ermöglicht HINTEREN und Löschvorgänge, die an einem anderen Ende ausgeführt werden sollen, werden aufgerufen VORDERSEITE .
2. Die Warteschlange wird als „First In First Out“-Liste bezeichnet.
3. Zum Beispiel bilden Menschen, die in der Schlange auf ein Bahnticket warten, eine Schlange.
Anwendungen der Warteschlange
Aufgrund der Tatsache, dass die Warteschlange Aktionen nach dem Prinzip „Wer zuerst kommt, mahlt zuerst“ ausführt, ist die Reihenfolge der Aktionen recht fair. Es gibt verschiedene Anwendungen von Warteschlangen, die im Folgenden erläutert werden.
- Warteschlangen werden häufig als Wartelisten für eine einzelne gemeinsam genutzte Ressource wie Drucker, Festplatte oder CPU verwendet.
- Warteschlangen werden bei der asynchronen Datenübertragung verwendet (wobei Daten nicht mit der gleichen Geschwindigkeit zwischen zwei Prozessen übertragen werden), z. B. Pipes, Datei-IO, Sockets.
- Warteschlangen werden in den meisten Anwendungen wie MP3-Media-Playern, CD-Playern usw. als Puffer verwendet.
- Warteschlangen werden verwendet, um die Wiedergabeliste in Mediaplayern zu verwalten und Lieder zur Wiedergabeliste hinzuzufügen und daraus zu entfernen.
- Warteschlangen werden in Betriebssystemen zur Verarbeitung von Interrupts verwendet.
Komplexität
| Datenstruktur | Zeitkomplexität | Raumvollständigkeit | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Durchschnitt | Am schlimmsten | Am schlimmsten | |||||||
| Zugang | Suchen | Einfügen | Streichung | Zugang | Suchen | Einfügen | Streichung | ||
| Warteschlange | In) | In) | ich(1) | ich(1) | An) | An) | O(1) | O(1) | An) |