Алгоритми та структури даних · Middle · Запитання 22 з 75
Як реалізувати чергу на двох стеках, щоб кожна операція була амортизовано O(1)?
- 1Копіювати один стек в інший при кожному додаванні
- 2Тримати обидва стеки відсортованими й знімати з меншого
- ✓Правильна відповідь: Класти в "in", знімати з "out", поповнюючи його з "in", коли він порожній
Пояснення
Перенесення розвертає порядок, тож найстаріший елемент опиняється на вершині "out". Кожен елемент переносять щонайбільше раз, тож n операцій разом коштують O(n).