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], изначально инициализированные нулем.

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

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

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

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