Условие задачи:
Реализуйте структуру данных «дек». Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
#include <iostream> #include <string> using namespace std; struct Node{ //структура звена списка int value; //передаваемое значение Node *next, *prev; //указатели на следующий и предыдущий элементы }; struct deque{ Node *head=nullptr; //инициализация начала и конца списка, размера дека Node *tail=nullptr; int count=0; void push_back(int num){ Node* element=new Node; //выделение памяти под новый элемент структуры element->value=num; //добавляем значение в структуру count++; if(!head){ //если список пуск head=element; //т.к элемент единственный, tail=head; //он является и хвостом и головой } else{ element->prev=tail; //предыдущий элемент списка относительно добавленного, будет последним(хвостом) tail->next=element; //следующий элемент за хвостом это добавляемый элемент списка tail=element; //присваивание элементу статуса хвоста } cout<<"ok"<<endl; } void push_front(int num){ Node *element=new Node; element->value=num; count++; if(!head){ head=element; tail=head; } else{ element->next=head; //следующий элемент за добавляемым элементом является хвост head->prev=element; //перед головой находится добавляемый элемент head=element; //присваивание элементу статуса головы } cout<<"ok"<<endl; } void pop_back(){ if(count!=0){ //если дек не пустой cout<<tail->value<<endl; if(count>1){ //если в деке находится больше одного элемента Node *element=tail; //указываем на то, что будет использоваться хвост tail=tail->prev; //присваиваем статус хвоста предыдущему элементу tail->next=nullptr; //указываем на то, что за элементом пусто delete element; //удаляем бывший хвост count--; //уменьшаем размер дека } else{ //если в деке находится всего один элемент head=tail=0; //присваиваем ему значение ноль count--; //уменьшаем размер дека } } else cout<<"error"<<endl; } void pop_front(){ if(count!=0){ cout<<head->value<<endl; if(head->next){ //если в деке больше одного элемента Node *element=head; //указываем на то, что будем использовать голову head=head->next; //присваиваем статус головы следующему за бывшей головой элементу head->prev=nullptr; //указываем на то, что перед головой пусто delete element; //удаляем бывшую голову count--; //уменьшаем размер дека } else if(head==tail){ //если элемент один в деке head->next=nullptr; //указываем, что за головой пусто head=nullptr; //указываем на то, что голова тоже пуста delete head; //удаляем единственный элемент count=0; //присваиваем ноль размеру дека } } else cout<<"error"<<endl; } void back(){ if(count!=0)cout<<tail->value<<endl; //выводим значение хвоста else cout<<"error"<<endl; } void front(){ if(count!=0)cout<<head->value<<endl; //выводим значение головы else cout<<"error"<<endl; } void size(){ cout<<count<<endl; //выводим размер дека } void clear(){ count=0; //присваиваем размеру дека ноль cout<<"ok"<<endl; while(head) //цикл: пока по адресу головы что-то лежит { tail=head->next; //присваиваем статус хвоста следующему элементу, что лежит за головой delete head; //удаляем первый элемент дека head=tail; //указываем на то, что хвост принимает статус головы } } void exit(){ cout<<"bye"; } }; int main() { deque deq; string str; while(cin>>str){ if(str=="push_front"){ int num; cin>>num; deq.push_front(num); } if(str=="push_back"){ int num; cin>>num; deq.push_back(num); } if(str=="pop_front")deq.pop_front(); if(str=="pop_back")deq.pop_back(); if(str=="clear")deq.clear(); if(str=="size")deq.size(); if(str=="front")deq.front(); if(str=="back")deq.back(); if(str=="exit"){ deq.exit(); break; } } return 0; } |
Описание решения задачи:
Для решения данной задачи использовался двунаправленный линейный список. Каждый узел ДЛС содержит два поля указателей — на следующий и на предыдущий узел. Для этого в задаче была создана структура [latex]Node[/latex]. Указателем на адрес начала списка и конца, соответственно, выступают узлы [latex]head[/latex] и [latex]tail[/latex], изначально инициализированные нулем.
Я выбрала данный метод реализации неограниченного дека, так как основным назначением связного списка и является предоставление механизма для хранения и доступа к произвольному количеству данных, что являлось основным барьером решения данной задачи. В отличии от массива, подсчет размера которого так же будет требовать дополнительных математических расчетов, список не требует дополнительных временных затрат на копирование/переписывание элементов при увеличении размера массива, рассчитанного на менее громоздкие вхождения. Да, прямого доступа к значениям произвольного элемента по индексу у нас нет, но на то и была поставлена задача в реализации именно этого представителя библиотеки контейнеров, ведь в деке допустимо удаление/добавление элементов лишь на концах. Единственным действительно заметным минусом в сравнении с использованием массива, по моему мнению, является увеличение расхода памяти в три раза, из-за хранения помимо основного значения элемента указатели на предыдущий и последующий элементы.
Условие задачи
Код задачи на с++
Засчитанное решение
Эта задача уже публиковалась у нас в трёх вариантах.
Поясните, почему Ваш вариант тоже стоит рассматривать.
Постаралась исправить: под описанием решения задачи я указала все минусы и плюсы такого решения.