• 403590
  • 633
  • 53
Нравится блог?
Подписывайтесь!

стек + стек = очередь

Хочу рассказать об одном интересном и полезном, с моей точки зрения, для общего развития применении таких базовых структур данных, как стек и очередь, на которые, к сожалению, неоправданно забивают многие будущие программисты при обучении. Первый раз оно было встречено на зимних сборах 2008 года в Петрозаводске (огромное спасибо Андрею Станкевичу за разбор), а вскоре к нему неожиданно свелась задача для Республиканской олимпиады школьников (правда, там для облегчения проходило и не самое оптимальное решение, но это, увы, не сильно помогло участникам).

Примерная суть задачи:

Дан массив A из N целых чисел (N порядка 108) и целое K (K < 106). Необходимо для каждого i от 1 до N - K + 1 найти min(A[i], A[i + 1], … A[i + K - 1]). Иначе говоря, в каждых K последовательных элементах массива найти минимальный. Время работы 2-3 секунды.

Лобовое решение имеет временную оценку примерно O(NK). Более умное, с использованием дерева отрезков, сбалансированных двоичных деревьев или чего-то подобного — O(NlogK). Но, к сожалению, это не достаточно быстро — необходима строго линейная зависимость времени работы от размера входных данных.

Для начала слегка преобразуем задачу. Пойдем по данному массиву слева направо и будем добавлять его элементы в очередь. При этом, если в размер очереди становится ровно K + 1, будем сразу выбрасывать из нее один элемент. Теперь задача в следующем: в каждый момент нам нужно уметь за константное (O(1)) время находить минимум в очереди. Как это сделать?

Сначала научимся делать то же самое в стеке. Для этого, параллельно со стеком S1, где хранятся сами элементы, заведем еще один — S2. При помещении числа X в первый стек, во второй будем помещать min(X, top(S2)), где top(S2) — элемент, находящийся на вершине стека S2. Тогда в каждый момент времени i-й элемент (считая снизу) в стеке S2 будет минимумом из нижних i элементов стека S1, а, следовательно элемент на вершине стека S2 будет минимумом из всех элементов стека S1. Очевидно, что это свойство также будет сохраняться при одновременном выталкивании элементов из стеков. Так как получение верхнего элемента стека осуществляется за константное время, то для стека задача решена.

Теперь попробуем применить полученный результат к нашей задаче. Идея указана в заголовке статьи — смоделируем очередь двумя стеками T1 и T2. Класть новые элементы будем только в T1. Забирать — только из T2. При этом, если в стеке T2 пусто, то нужно перенести в него все элементы из T1. Очевидно, что над каждым элементом выполняется максимум 3 константные операции, и, как следствие, получаем амортизированную линейную зависимость времени работы от количества операций.

Далее — дело техники: найти минимум в каждом из стеков мы уже можем, а минимум в очереди будет min(min(T1), min(T2)), где min(T1), min(T2) — минимум в стеке T1 или T2 соответственно.

Кросспост с моего блога.

7 июля 2008, 21:16
911

Загрузка...

Комментарии

Огромное спасибо за статью, будем пробовать. Со стеком мне приходилось встречаться, а вот с очередями пока что нет (хотя на мой взгляд они похожи, может я ошибаюсь).
arti
0
0
Похожи. Разница лишь в том, куда класть и откуда забирать.
Darmen
0
0
Ну, не ново, но спасибо
san
0
0
что именно не ново? стек и очередь?
или сама идея комбинации?
Darmen
0
0
и то, и то, и то =)
smerch
0
0
arti, вы просто светлый луч! спасибо, хорошо написано!

Оставьте свой комментарий

Спасибо за открытие блога в Yvision.kz! Чтобы убедиться в отсутствии спама, все комментарии новых пользователей проходят премодерацию. Соблюдение правил нашей блог-платформы ускорит ваш переход в категорию надежных пользователей, не нуждающихся в премодерации. Обязательно прочтите наши правила по указанной ссылке: Правила

Также можно нажать Ctrl+Enter

Популярные посты

Что дал Казахстану переход к трехступенчатой судебной системе?

Что дал Казахстану переход к трехступенчатой судебной системе?

С 1 января 2016 года Казахстан перешел на трехступенчатую судебную систему. Данные изменения действуют уже более 8 месяцев, и в данной публикации мы попробуем разобраться, что это дало Казахстану?
RuSnake
24 сент. 2016 / 11:50
  • 12595
  • 3
В октябре 2016 года состоится VII съезд судей Казахстана

В октябре 2016 года состоится VII съезд судей Казахстана

Проведение съездов судей позволяет принимать стратегические решения по вопросам развития судебной системы и способствует укреплению принципов независимости судейского сообщества.
elawkz
23 сент. 2016 / 13:45
  • 10757
  • 0
О законе законов: Замолвите слово о справедливости

О законе законов: Замолвите слово о справедливости

Акимат г. Астаны предлагал собственнику компенсацию...4 тенге 13 тиын за землю. Потолкуем о справедливости?
mirabeisenova
23 сент. 2016 / 16:39
  • 10470
  • 5
Я –живой пример того, что для начала собственного дела не нужны большие деньги

Я –живой пример того, что для начала собственного дела не нужны большие деньги

Сегодня утром ко мне позвонила тетя и сообщила, что хочет открыть свое дело, но не знает с чего начать и не уверена, хватит ли ей первоначального капитала. Вы не представляете, как она удивилась, когд
toskanbayev_a
21 сент. 2016 / 16:45
  • 10098
  • 27
Кызылорда: перезагрузка, или что изменилось за последние несколько лет

Кызылорда: перезагрузка, или что изменилось за последние несколько лет

В преддверии Дня города мы решили вспомнить, как росла и развивалась наша родная Кызылорда в последние годы. Хотим поделиться своей любовью к родному городу с читателями Юви в этой фотоподборке ...
socium_kzo
22 сент. 2016 / 10:09
  • 6699
  • 8
Сватовство в Казахстане или Заберите скорее мою дочь к себе

Сватовство в Казахстане или Заберите скорее мою дочь к себе

Всю мою сознательную жизнь мне приходилось ходить в гости. В гостях неплохо, не спорю. Бесплатная еда и напитки. В особо продвинутых семьях ещё предоставляются услуги Free Wi-Fi. В особо весёлых...
almatinec_92
23 сент. 2016 / 9:33
25 годовщину независимости от колониального гнета Киргизия встретила вот так...

25 годовщину независимости от колониального гнета Киргизия встретила вот так...

Трехлетний Исхак стал звездой киргизских СМИ и соцсетей на прошлой неделе. Его фотография, спящего на улице среди окурков на картонке, вызвала шок в обществе. В принципе это подобное фото можно...
Shpak
20 сент. 2016 / 15:52
Apple – это уже прошлое. XIAOMI тихо стал настоящим и будущим

Apple – это уже прошлое. XIAOMI тихо стал настоящим и будущим

Безусловно мы все относимся с большим уважением с Стив Джобсу. Но его уже больше 5 лет нет с нами. Бессмысленно продолжать фанатеть от продукции Apple...
GALAN
22 сент. 2016 / 23:19
  • 3576
  • 13
Оралманка из Китая! Надеюсь, ты встретила того, кто по достоинству оценил тебя...

Оралманка из Китая! Надеюсь, ты встретила того, кто по достоинству оценил тебя...

В один прекрасный день я все же подошел к ней и попытался с ней нормально поговорить и пригласить куда-нибудь погулять или поужинать. Мы разговаривали с ней минут 20, я использовал весь свой...
Timurkhan
23 сент. 2016 / 12:26
  • 3244
  • 9