In der Informatik bezeichnet eine Warteschlange (Queue) eine verkettete Liste von Datenelementen. Die Datenelemente werden nach dem FIFO-Prinzip (First In - First Out) in die Warteschlange gelegt und von da wieder entnommen. Dazu werden die Operationen PUSH zum hinzufügen und POP zum entnehmen der Elemente implementiert. Das oberste Element im Stapel besitzt einen Next-Zeiger, welcher auf das nächste Element in der Warteschlange zeigt. Der Next-Zeiger des letzten Elementes in der Schlange zeigt auf NULL. Bei POP wird immer das unterste Element entnommen, welches als erstes mit PUSH eingefügt wurde.
Aufgabe: Eine Vorrangwarteschlange (Priority Queue) ist eine Spezialisierung der Warteschlange. Die Elemente werden nicht mehr nach dem FIFO-Prinzip eingefügt und entnommen, sondern gemäß einer festgelegten Priorität. Dadurch ergibt sich eine von vorne herein sortierte Warteschlange. Entnommen werden die Elemente mit der höchsten Priorität. Implementiere in Pseudo-Code eine Prozedur INSERT, die Elemente sortiert nach ihrem Wert einfügt.