e-olimp 6130. Дек неограниченного размера (как список деков)

Как пишет Википедия в статье Double-Ended Queue, есть три основных способа реализации двухсторонней очереди (она же — дек, дека и т.д.):

— хранить дек в циклическом буфере и расширять при переполнении (при таком подходе реже нужны расширения);

— хранить содержимое дека в массиве, начиная от его центра, и при переполнении расширять массив (например, создавать новый массив и копировать туда содержимое старого);

— хранить дек в виде многих малых массивов, добавляя новые массивы с того или другого конца при необходимости.

Здесь приведу свою реализацию третьим способом: малые деки хранятся в виде двусвязного списка и добавляются/удаляются в соответствующих ситуациях.; конструктор основного дека создаёт единственный малый дек, который заполняется от центра к краям.

Соответствующая задача на e-olimp: 6130  и зачтённое решение.

В этом блоге можно увидеть картинку, иллюстрирующую рассматриваемый метод, и краткое описание того, как можно снабдить дек индексированием, чтобы быстро получать доступ к элементу дека по его индексу (как в массиве).

 

О плюсах и минусах

Расширения нужно (в теории) производить чаще, чем при первом подходе, но зато не нужно полностью копировать содержимое дека при расширении.

Отмечу, что если хранить в узлах двусвязного списка не малые деки, а отдельные элементы, то тратится в три раза больше памяти, что должно быть чувствительно при необходимости хранить большое количество элементов в деке.

Основным преимуществом рассматриваемого подхода, по сравнению с двумя другими, я считаю как раз более эффективный расход памяти. Основной же недостаток, на мой взгляд, состоит в том, что при цепочке удалений-вставок, приводящей к постоянному переполнению/очищению одного из крайних малых деков, будут очень часто создаваться/удаляться малые деки, что может привести к бОльшим временным затратам, чем при реализации дека другими методами.

 

 

Вустянюк Ігор Дмитрович
Вустянюк Ігор Дмитрович

Latest posts by Вустянюк Ігор Дмитрович (see all)

2 thoughts on “e-olimp 6130. Дек неограниченного размера (как список деков)

  1. Зачтено. Отлично работает. Молодец!

    Но… есть замечание — массив печатается целиком, а не только заполненные элементы.

    … и вопрос.
    В этом примере использования

    единичка ползет по массиву до конца, потом создается новый массив и удаляется старый. И так будет снова и снова. Правильно?
    Т.е. с точки зрения эффективности лучше использовать циклические массивы в качестве элементарных дек списка. И это ничуть не сложнее, чем написано сейчас.

  2. Замечание очень актуальное. Я отметил этот недостаток в последнем абзаце раздела «О плюсах и минусах». К сожалению, при реализации столкнулся с техническими проблемами, когда пробовал использовать циклические буферы, поэтому оставил такой вариант — он работал!
    Печать я изначально использовал для промежуточных выводов на экран при добавлениях/удалениях: тогда нужно было выводить весь массив, а потом забыл подправить.