Algorytmy i struktury danych · Middle · Pytanie 23 z 75
Która struktura daje wstawianie i usuwanie w O(1) na obu końcach?
- 1Zbalansowane binarne drzewo poszukiwań
- ✓Poprawna odpowiedź: Deque (kolejka dwustronna)
- 3Posortowana tablica z wyszukiwaniem binarnym
Wyjaśnienie
Deque to zwykle bufor cykliczny lub lista dwukierunkowa. To kluczowa struktura dla „maksimum w przesuwanym oknie” w O(n): trzyma kandydatów w kolejności malejących wartości.