e-olymp 6128. Простой дек

Задача. Простой дек

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

push_front

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

push_back

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

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

pop_back

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

front

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

back 

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

size

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

clear

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

exit

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

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции:

  • pop_front
  • pop_back
  • front
  • back

всегда корректны.

Объяснение: Количество элементов во всех структурах данных не превышает 10000, если это не указано особо.

Тесты

 №  Входные данные  Выходные данные
 1

 push_back 3

push_back 14

size

clear

push_front 1

back

push_back 2

front

pop_back

size

pop_front

size

exit

 ok

ok

2

ok

ok

1

ok

1

2

1

1

0

bye

 2  size

push_back 8

push_front 4

size

front

back

push_back 3

pop_front

front

pop_back

back

exit

0

ok

ok

2

4

8

ok

4

8

3

8

bye

Решение

Алгоритм решения

Реализация двусторонней очереди идет посредством векторов [latex]box1[/latex] и [latex]box2[/latex], поэтому нет необходимости делать проверку на переполнение. Команды [latex]push_front[/latex] и [latex]push_back[/latex] соответственно добавляют в концы векторов [latex]box1[/latex] и [latex]box2[/latex] элементы и увеличивают размер дека box_size (на единицу за каждый добавленный элемент). Рассмотрим команду [latex]front[/latex]. Проверяя присутствие элементов в [latex]box1[/latex] мы выводим последний элемент вектора, так как добавляли элемент с помощью [latex]push_front[/latex] в конец вектора [latex]box1[/latex]. Если же вектор [latex]box1[/latex] пуст, то выводим первый элемент вектора [latex]box2[/latex], который в случае пустого вектора [latex]box1[/latex] является первым элементом дека. Команда [latex]back[/latex] относительно [latex]front[/latex] с векторами работает инверсивно. Т.е. Проверяя присутствие элементов в [latex]box2[/latex] выводим последний элемент данного вектора. Если же вектор [latex]box2[/latex] пуст, то выводим первый элемент вектора [latex]box1[/latex] , который в случае пустого вектора [latex]box2[/latex] является последним элементом дека. С командами [latex]pop_front[/latex] и [latex]pop_back[/latex] работают идентично [latex]front[/latex] и [latex]back[/latex]. Отличие лишь в том, что команды [latex]pop[/latex] в дополнении к выводу элемента удаляют его, уменьшая размер дека [latex]box_size[/latex] (на единицу за каждый удаленный элемент). Команда [latex]size[/latex] выводит размер дека [latex]box_size[/latex]. Команда clear удаляет все элементы векторов [latex]box1[/latex], [latex]box2[/latex] и обнуляет размер дека. Команда [latex]exit[/latex] выводит «bye» и завершает работу программы. Команды принимаются из потока ввода посредством строки s.

Ссылка на код.

e-olymp.

 

Related Images:

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

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

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

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

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

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

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

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

 

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

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

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

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

 

 

Related Images: