Priority Queues könnten z.B. mit den folgenden Datenstrukturen realisiert werden:
- einer doppelt verketteten Liste (siehe Programmieraufgabe)
- einem absteigend sortierten Array. Dieses Array soll keine Lücken aufweisen, das Element mit der höchsten Priorität soll sich immer an Position 0 befinden.
- einem Array in Form eines Max-Heaps.
Beschreiben Sie für 2. und 3. jeweils wie die Methoden add() und pop() implementiert würden. Gegeben eine Queue mit n Elementen, geben Sie dann für alle 3 Implementierungen die Komplexität von add() und pop() im Best Case und Worst Case an und begründen Sie.