Eine priorisierte Warteschlange ist eine Variante der gewöhnlichen Warteschlange (engl. Queue), die Elemente in einer Liste nach dem FIFO-Prinzip (first in, first out) organisiert. In einer gewöhnlichen Queue wird jedes neue Element immer am Ende einsortiert, so daß kein Element bevorzugt behandelt wird, denn schließlich wird ein Element immer nur vom Anfang der Queue entnommen.

Eine Priority Queue hingegen funktioniert anders: Bevor ein Element in die Queue eingereiht wird, muß anhand der dem Element assoziierten Priorität ein passender Platz gefunden werden. Dabei wird ein Element mit höherer Priorität vor Elementen mit niedrigerer Priorität eingeordnet, jedoch hinter bereits vorhandene Elemente mit gleicher Priorität.

Weiter »