• 408644
  • 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
996

Загрузка...
Loading...

Комментарии

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

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

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

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

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

Инструкция для аллергиков. Как бороться с аллергией в период обострения

Инструкция для аллергиков. Как бороться с аллергией в период обострения

Я аллергик с детства. Имею аллергию на пыльцу березы, липы, полыни (выяснил это благодаря кожным пробам), а также пищевую аллергию на горчицу. Свои проблемы знаю, однако это меня не спасло.
Romeo_17
15 авг. 2017 / 17:21
  • 38685
  • 63
СМИ – ассистент провокаторов? Как гости из соседних стран сеют раздор в Казахстане

СМИ – ассистент провокаторов? Как гости из соседних стран сеют раздор в Казахстане

Инцидент с пьяным киргизским гостем на борту Air Astana, наверное, остался бы только во внутренних сводках авиакомпании, если бы г-н Доган, не поднял громкий крик о государственном языке.
openqazaqstan
17 авг. 2017 / 14:43
  • 10540
  • 173
Алматы предложили сделать центром секс-туризма

Алматы предложили сделать центром секс-туризма

Известный политолог России Андрей Карпов предложил сделать Алматы центром секс-туризма. Но для этого сперва нужно легализовать проституцию в стране.
tala03
13 авг. 2017 / 14:48
Казахский национализм раньше выглядел несовременно. Теперь он другой

Казахский национализм раньше выглядел несовременно. Теперь он другой

Националисты стали совсем другими. По-английски хорошо говорят, русскую классику цитируют. Очень современные, образованные, адекватные. А после Крыма в националисты уже чуть ли не любой казах готов был записаться.
Aidan_Karibzhanov
16 авг. 2017 / 16:52
Имеющий уши да услышит. Латиница касается только казахского языка

Имеющий уши да услышит. Латиница касается только казахского языка

Президент Назарбаев наконец-то разъяснил для всех, кто ещё не понял, очевидный вопрос, который всем в Казахстане очевиден. Елбасы повторил: на латиницу мы переводим казахский язык, и это не означает отказ от русского языка.
openqazaqstan
18 авг. 2017 / 16:23
  • 2488
  • 44
«Доехать до Алтын Орды» – как мошенники обманывают алматинцев

«Доехать до Алтын Орды» – как мошенники обманывают алматинцев

Из множества грустных откровений постепенно сложился перечень самых распространённых уловок охотников за нашими деньгами. В нём ожидаемо лидировали профессиональные попрошайки.
caravan_kz
16 авг. 2017 / 15:05
  • 2018
  • 2
В Кокшетау строят два парка для молодёжи. Будут учтены интересы и любителей спорта

В Кокшетау строят два парка для молодёжи. Будут учтены интересы и любителей спорта

Общая площадь парка составляет 25 гектаров. На территории предусмотрено устройство прогулочных дорожек, площадок для установки аттракционов и павильонов различного назначения, цветников.
zhasakmola
17 авг. 2017 / 17:13
  • 1881
  • 1
Недоразумение с грантами в ВУЗы: «медалисты» до сих пор имеют преимущество

Недоразумение с грантами в ВУЗы: «медалисты» до сих пор имеют преимущество

Многие способные выпускники без Алтын Белги готовились к тестированию, чтобы в честной борьбе попытать счастья на гранты без ущемления со стороны якобы "золотых" выпускников.
DanaJarlygapova
14 авг. 2017 / 14:35
Новый конкурс на грантовое финансирование – разочарование для казахстанских ученых

Новый конкурс на грантовое финансирование – разочарование для казахстанских ученых

Обсуждение новых условий началось ещё давно, но стоит ли ожидать качественного улучшения результатов научно-исследовательской деятельности, если система управления наукой не была модернизирована?
ermekuss
17 авг. 2017 / 12:23
  • 1712
  • 1