e-olimp 6130. Дек неограниченного размера.

Задача:

Реализуйте структуру данных «дек«.  Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Размер дека должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций pop_frontpop_backfrontback программа должна проверять, содержится ли в деке хотя бы один элемент. Если во входных данных встречается операция pop_frontpop_backfrontback, и при этом дек пуст, то программа должна вместо числового значения вывести строку error.

Результат на C++

Результат на Java

Код на C++:

Код на Java:

 

Пояснение:

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

Трудности возникли тогда, когда количество элементов в деке сравнялось с вместимостью базового массива. В таком случае необходимо величить вместимость дека. Сделать это можно следующим образом. Нужно создать новый массив, перенести в него элементы старого массива, а после присвоить указателю на старый массив указатель на новый. После увеличения вместимости дека возник вопрос: Куда указывают указатели? Мы их не меняли, а значит они имеют прежние значения, что уже не актуально. Так как первый элемент в новом массиве находится на нулевой позиции, меняем значение указателя на первый элемент (front_) на нуль. Указатель на последний элемент (back_) теперь должен иметь значение равное, уменьшенному на единицу, количеству элементов. Осталось только изменить значение вместимости (capacity), у меня вместимость увеличивается вдвое.

Такая реализация является одной из самых простых. По сравнению с двусвязным списком, она приблизительно в три раза проигрывает в скорости выполнения. Но за счет того, что мы храним только один int на каждый элемент (вместо трех, которые были у списка), такая реализация использует заметно меньше памяти.

 

 

 

2 thoughts on “e-olimp 6130. Дек неограниченного размера.

  1. Зачтено.
    Больное место реализаций с изменением размера массива — это стратегия наращивания. Редко точно известно как именно будет расти дека (очередь, стек) и на сколько или во сколько раз его увеличивать. Сделайте, пожалуйста, ссылку на аналогичную работу Игоря Вустянюка. Там используется более эффективная система списка массивов. Правда пока не циклических.

  2. Игорь Евгеньевич прав — изменение размера структуры — это проблема. Вы увеличиваете вместимость — это хорошо, но нигде не происходит уменьшение вместимости — даже clear ее не уменьшает. Вообще-то по хорошему clear должен сбрасывать вместимость на первоначальную (если она больше первоначальной). И еще, первоначальная вместимость 100 у Вас магическое число.

    Так что пока 10 баллов зачесть не могу — 7 баллов.

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