Задача. Простой дек
Условие задачи
Реализуйте структуру данных «дек«. Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
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_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 |
| 2. | push_front 5 pop_front size push_back 3 push_front 10 back pop_back size clear front exit |
ok 5 0 ok ok 3 3 1 ok -1 bye |
| 3. | push_front 1 push_back 12 back front size pop_front size exit |
ok ok 12 1 2 1 1 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 |
#include <iostream> #include <string> using namespace std; #define SIZE 10000 struct deque { int storage[SIZE]; int _size = 0, start = 0, end = 0; void push_front(int n) { if (_size == SIZE) { cout << "Full\n"; } else if (_size == 0) { storage[start] = n; _size++; } else { if (start == 0) { start = SIZE - 1; storage[start] = n; _size++; } else { start--; storage[start] = n; _size++; } } } void push_back(int n) { if (_size == SIZE) { cout << "Full\n"; } else if (_size == 0) { storage[end] = n; _size++; } else { if (end == SIZE-1) { end = 0; storage[end] = n; _size++; } else { end++; storage[end] = n; _size++; } } } int pop_front() { int b; if (_size != 0 && (start == end)) { b = storage[start]; _size--; return b; } else if (_size == 0) { return -1; } else { b = storage[start]; if (start == SIZE - 1) { start = 0; _size--; } else { start++; _size--; } return b; } } int pop_back() { int b; if (_size != 0 && (start == end)) { b = storage[end]; _size--; return b; } else if (_size == 0) { return -1; } else { b = storage[end]; if (end == 0) { end = SIZE - 1; _size--; } else { end--; _size--; } return b; } } int front() { if (_size == 0) return -1; else return storage[start]; } int back() { if (_size == 0) return -1; else return storage[end]; } int size() { return _size; } void clear() { _size = 0; start = end = 0; } }; int main() { deque d; string s; int n; while (cin >> s) { if (s == "push_front") { cin >> n; d.push_front(n); cout << "ok\n"; } else if (s == "push_back") { cin >> n; d.push_back(n); cout << "ok\n"; } else if (s == "pop_front") { cout << d.pop_front() << endl; } else if (s == "pop_back") { cout << d.pop_back() << endl; } else if (s == "front") { cout << d.front() << endl; } else if (s == "back") { cout << d.back() << endl; } else if (s == "size") { cout << d.size() << endl; } else if (s == "clear") { d.clear(); cout << "ok\n"; } else if (s == "exit") { cout << "bye\n"; return 0; } } return 0; } |
Алгоритм решения
Реализуем двустороннюю очередь с помощью массива. Ввиду особенности структуры дека, необходимым является указание области, активной во время выполнения операций
push_front,
push_back,
pop_front,
pop_back,
front и
back. Это либо начало дека(переменная
start), либо его конец(переменная
end).
1. Перед выполнением операций
push_front и
push_back обязательной является проверка дека на заполненность и соответственно на пустоту. Таким образом, если размер дека равен максимально допустимому количеству элементов в структуре данных, программа выводит
Full — ни одна из двух вышеупомянутых команд не выполняется. Аналогично, если размер дека равен нулю, увеличиваем его на единицу. Иначе: команды успешно выполняются с проверкой условий, представленных в коде программы. Программа выводит «ok».
2. Далее переходим к командам
pop_front и
pop_back. Здесь, как и в случае предыдущих операций, в первую очередь проверяем дек на пустоту. Если двусторонняя очередь не содержит элементов, то программа выводит -1. Важной также является проверка на равенство начала и конца дека, в этом случае нужно уменьшить размер структуры на единицу. Если дек содержит хотя бы один элемент, команды успешно выполняются и выводятся значения извлекаемых элементов.
3. Аналогично, перед выполнением команд
front и
back проверяем, содержит ли дек хотя бы один элемент. Если нет, выводится -1. Иначе: выводятся значения первого и последнего элемента соответственно.
4. Используем команду
size, чтобы получить размер дека. Программа выводит количество элементов в деке.
5. Далее, с помощью команды
clear удаляем из дека все элементы: присваиваем переменной
_size(размер дека) и переменным
start и
end значение ноль. Программа выводит «ok».
6. Команда
exit выводит «bye» — программа завершает работу.
Реализация вывода на экран всех требуемых значений происходит в теле функции
main() с помощью строки
s.
Для запроса на выполнение следует перейти по ссылке.
Ссылка на засчитанное решение на e-olymp.com.
Зачтено.
Вот только, ни комментариев в коде, ни пояснений к решению.
Игорь Евгеньевич, добавила алгоритм решения. Проверьте, пожалуйста.