Algorytmy i struktury danych · Middle · Pytanie 22 z 75
Jak zbudować kolejkę na dwóch stosach, aby każda operacja była zamortyzowanie O(1)?
- 1Kopiować jeden stos do drugiego przy każdym dodaniu
- 2Trzymać oba stosy posortowane i zdejmować z mniejszego
- ✓Poprawna odpowiedź: Wkładać do "in", zdejmować z "out", uzupełniając go z "in", gdy jest pusty
Wyjaśnienie
Przenoszenie odwraca kolejność, więc najstarszy element ląduje na szczycie "out". Każdy element jest przenoszony najwyżej raz, więc n operacji kosztuje razem O(n).