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

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

push_front

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

push_back

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

pop_front

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

pop_back

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

front

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

back

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

size

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

clear

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

exit

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

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

Тесты

Входные данные Выходные данные
push_front 1 ok
push_back 9 ok
push_front 2 ok
push_back 3 ok
size 4
pop_front 2
pop_back 3
size 2
front 1
back 9
clear ok
size 0
back error
exit bye

Описание решения задачи:
Для решения данной задачи использовался двунаправленный линейный список. Каждый узел ДЛС содержит два поля указателей — на следующий и на предыдущий узел. Для этого в задаче была создана структура [latex]Node[/latex]. Указателем на адрес начала списка и конца, соответственно, выступают узлы [latex]head[/latex] и [latex]tail[/latex], изначально инициализированные нулем.

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

Условие задачи
Код задачи на с++
Засчитанное решение

A302. Количество различных цифр числа в его десятичной записи

Задача

Дано натуральное число [latex]N[/latex]. Сколько различных цифр встречается в его десятичной записи?

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

Натуральное число [latex]N[/latex].

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

Количество различных цифр [latex]sum[/latex].

Тесты

Входные данные Выходные данные
[latex]N[/latex] [latex]sum[/latex]
12345678900987654321 sum:10
302 sum:3

Код программы с использованием deque

 

Решение

Создадим дэк [latex]folder[/latex] в котором будем хранить различные цифры десятичной записи. Добавляем первую цифру числа [latex]N[/latex] в дэк и делим [latex]N[/latex] на [latex]10[/latex]. Следующие цифры мы будем добавлять после проверки на отсутствие таких же в [latex]folder[/latex], если цифры совпадают заканчиваем цикл. В конце выводим размер [latex]folder[/latex] который и является [latex]sum[/latex].

Код программы с использованием массива

Решение

Создадим массив [latex]folder[/latex] в котором будем хранить кол-во встреч для различных цифр десятичной записи в соответствующих позициях массива. Увеличиваем на один значения соответствующей позиции массива и делим [latex]N[/latex] на [latex]10[/latex]. Для определения [latex]sum[/latex] делаем цикл и проверяем ненулевые значения массива [latex]folder[/latex].

Ссылки

Ideone через deque;
Ideone через массив;
Условие задачи (стр. 126).

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

Задача

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

  • push_front Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.
  • push_back Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.
  • pop_front Извлечь из дека первый элемент. Программа должна вывести его значение.
  • pop_back Извлечь из дека последний элемент. Программа должна вывести его значение.
  • front Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.
  • back Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.
  • size Вывести количество элементов в деке.
  • clear Очистить дек (удалить из него все элементы) и вывести ok.
  • exit Программа должна вывести bye и завершить работу.

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

pop_front,
pop_back,
front,
back
всегда корректны.

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

Описаны в условии. См. также пример входных данных.

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

Описаны в условии. См. также пример входных данных.

Тесты

Входные данные Выходные данные
push_back 3
push_front 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

Код программы на C++

Код программы на Java

Решение

Создадим массив [latex]folder[/latex] и целочисленные переменные [latex]start[/latex] и [latex]end[/latex] в качестве указателей на начало и конец нашего дека.

  • push_front  — сдвигаем указатель [latex]start[/latex] на [latex]1[/latex] назад, кладем значение в наш дек и выводим ok;
  • push_back  — кладем значение в наш дек, сдвигаем указатель [latex]end[/latex] на [latex]1[/latex] вперед и выводим ok;
  • pop_front  — выводим значение начала дека и перемещаем [latex]start[/latex] вперед на [latex]1[/latex];
  • pop_back  — перемещаем [latex]end[/latex] назад на [latex]1[/latex] и выводим значение конца дека;
  • front  — выводим значение начала дека;
  • back  — выводим значение перед [latex]end[/latex];
  • size  — отнимем от переменной [latex]end[/latex] переменную [latex]start[/latex];
  • clear  — приводим [latex]start[/latex] и [latex]end[/latex] к изначальным позициям;
  • exit  — выводим «bye» и заканчиваем программу.

Ссылки

Ideone C++
Ideone Java
решение e-olymp C++
решение e-olymp Java