• 405574
  • 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
948

Загрузка...

Комментарии

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

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

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

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

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

Обратная сторона Астаны. Девять худших и проблемных районов столицы Казахстана

Обратная сторона Астаны. Девять худших и проблемных районов столицы Казахстана

Несмотря на то, что Астана столица, и один из самых красивых и современных городов Казахстана, здесь все равно есть места, за которые стыдно и даже как-то неудобно перед гостями.
Washington
12 янв. 2017 / 12:25
  • 20601
  • 26
Расписание Универсиады в Алматы. Что стоит посетить?

Расписание Универсиады в Алматы. Что стоит посетить?

Путеводитель по соревнованиям Универсиады с рекомендациями, какие соревнования Универсиады никак нельзя пропустить. До встречи на Универсиаде!
olympic
11 янв. 2017 / 10:40
  • 18448
  • 7
Господин министр, что означает ваша фраза «Хорошо, не открывайте, мы найдем другой способ проверить»?

Господин министр, что означает ваша фраза «Хорошо, не открывайте, мы найдем другой способ проверить»?

Это что, совет? Рекомендация? Или это угроза? Чего нам ждать? Чего нам бояться? Мы – законопослушные граждане Республики Казахстан, мы ЗА ужесточение законодательства в части борьбы с терроризмом, но при этом...
AliyaSadyrbaeva
10 янв. 2017 / 21:02
  • 15762
  • 32
Как мы «скидываемся» на красивую жизнь мажоров. Воровство пенсионных денег

Как мы «скидываемся» на красивую жизнь мажоров. Воровство пенсионных денег

Официальные спикеры КНБ РК рассказали о ходе расследования, раскрыв общественности схему, которую использовало руководство ЕНПФ для воровства 5 миллиардов тенге пенсионных накоплений.
openqazaqstan
13 янв. 2017 / 11:30
  • 13832
  • 12
«Ещё раз на те же грабли». Премьер Сагинтаев о временной регистрации

«Ещё раз на те же грабли». Премьер Сагинтаев о временной регистрации

Казахстанцы по-прежнему с нескрываемым возмущением и сарказмом комментируют нововведения в миграционное законодательство. Проблема, как это ни парадоксально, в том, что мы, казахстанцы – народ законопослушный.
openqazaqstan
12 янв. 2017 / 10:07
  • 11056
  • 26
Так и думал, что 2017-й начнется отвратительно. Каково вообще таким как я, квартирантам?

Так и думал, что 2017-й начнется отвратительно. Каково вообще таким как я, квартирантам?

В городе у меня нет совершенно никого, поэтому ни прописки, ни регистрации у меня нет, а живу я в съемной, как и многие. К сожалению, далеко не каждый человек готов прописать, хоть и временно, своего квартиранта.
MrVladimirLV
10 янв. 2017 / 15:21
  • 6858
  • 81
Наверное, я себя почувствовала человеком именно в Корее. Не в Казахстане

Наверное, я себя почувствовала человеком именно в Корее. Не в Казахстане

Если я останусь в Казахстане, то идти мне здесь некуда, пахать за копейки на госслужбе? Прожить всю жизнь в однокомнатной вместе с котом и мамой?
savira6
13 янв. 2017 / 9:44
  • 4675
  • 28
Айсулу Салгарина. Решил пойти в гости к той, что вызывает гордость за казахских девушек

Айсулу Салгарина. Решил пойти в гости к той, что вызывает гордость за казахских девушек

Прошло около 2 лет. За эти годы в моей жизни многое изменилось. И мне стало интересно, какие же изменения произошли в жизни тех, у кого я когда-то брал интервью...
DastanIskakov
14 янв. 2017 / 11:43
  • 4181
  • 4
Сейчас даже дяденьки и тетеньки в 20-27 лет живут с родителями. Безработица в Алматы

Сейчас даже дяденьки и тетеньки в 20-27 лет живут с родителями. Безработица в Алматы

Наверняка, все знают крылатую фразу Ленина "Кто не работает - тот не ест" В то время за безработицу осуждали, а кормили народ за счет предприятия - славные были времена, пусть я и застала их лишь...
DoZa
13 янв. 2017 / 9:54
  • 3749
  • 43