Algorithmen und Datenstrukturen · Middle · Frage 23 von 75
Welche Struktur bietet Einfügen und Entfernen in O(1) an beiden Enden?
- 1Ein balancierter binärer Suchbaum
- 2Eine Deque (doppelseitige Queue)
- 3Ein sortiertes Array mit binärer Suche
Antwort zeigen
Richtige Antwort: Eine Deque (doppelseitige Queue)
Erklärung
Eine Deque ist meist ein Ringpuffer oder eine doppelt verkettete Liste. Sie ist die Schlüsselstruktur für „Maximum im Schiebefenster“ in O(n): sie hält Kandidaten-Indizes in fallender Reihenfolge der Werte.