Стек, дек и очередь неограниченного размера

Задачи: Стек, Очередь и Дек

Решение:

Код для задачи на неограниченный стек:

Код для задачи на неограниченную очередь:

Код для задачи на неограниченный дек:

Засчитанные решения на сайте e-olimp: Стек, Очередь и Дек.

Идея решения: Каждый элемент в структуре должен хранить информацию о предыдущем и последующем. Для этого была организована структура Node. Для дека и очереди она одинаково реализована, а для стека можно было хранить только предыдущий элемент. Во всех 3х задачах была реализована требуемая структура данных.

Однако в каждой задаче требовалось возможность использования всей оперативной памяти под структуру. В моем решении каждый элемент занимает втрое больше памяти (я подозреваю) чем обычный int, а значит всю оперативную память под числа я использовать не смогу. Тогда можно использовать заранее созданный массив достаточно большого размера, чтобы занять всю выделенную память в 256 мб. Но это не будет считаться «неограниченным» размером. А если использовать ту же структуру с Node, но вместо одного элемента хранить массив? Тогда информацию о следующем и предыдущем массиве нужно так-же хранить, как и с отдельными элементами. Вроде бы меньше памяти будет тратится на хранение дополнительной информации, НО никто не может точно сказать, какого размера массивы должны быть. Если они будут слишком маленькие — большой выгоды такой способ не принесет. Если они будут слишком большими, то есть шанс, что мы не покроем большой кусок памяти, что тоже не очень хорошо.

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

Поэтому я реализовал всё без массивов (хотя вариант с маленькими массивами имеет место быть).

5 thoughts on “Стек, дек и очередь неограниченного размера

    • метки и рубрика добавлены. У очереди вышел двунаправленный список, так как во время написания очереди я уже думал над деком.

      • Ну, мало ли о чем думает юноша, во время написания очереди 🙂
        Не нужно плодить избыточные сущности. Я хочу сказать, что программа с очередью вводи некоторые поля и связи, поддерживает их целостность, но никогда ими не пользуется за ненадобностью. Это не только непроизводительно расходует память, но и увеличивает вероятность ошибки в коде, которые не может быть протестирован.

        • А вдруг я буду думать о неправильных вещах и у меня плохо получится дек? 🙂
          Избыточные сущности убрал, перетестировал код и поменял ссылку на засчитанное решение.

Добавить комментарий