Міністерство освіти і науки України Національний університет “Львівська політехніка” Звіт про виконання лабораторної роботи №5 з дисципліни: «Програмування. Частина III. Структури даних та алгоритми » на тему: «Структура даних "ЧЕРГА"» Львів-2020 Мета роботи Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач. Завдання Змоделюйте чергу (або дек) згідно з завданням. Перепишіть основні операції для роботи з чергою (деком), і продемонструйте їх застосування для операцій додавання і вилучення елементів в чергу (дек). Для цього задайте послідовність з N цілих чисел. Всі додатні числа послідовно заносяться в чергу (дек), кожне від’ємне число вилучає з черги (деку) один елемент (при роботі з деком, парні числа працюють з одним кінцем деку, а непарні – з іншим). Показувати всі зміни, що будуть відбуватись у черзі (деку). 5 завдання Змоделюйте структуру даних ДЕК з обмеженим входом (тобто вилучати з дека можна з обох кінців, а додавати тільки з одного). Код програми: #include<iostream> using namespace std; template <typename T> class DEK { private: T mas[20]; int leght; bool emptyness; public: DEK() { // конструктор leght = 0; emptyness = true; } int size() { // повертає розмір return leght; }; bool empty() { // Повертає true, якщо DEK порожній, і false у противному випадку return emptyness; }; void push_right(T value) { // функція додавання елементу if (leght != 20) { mas[leght] = value; leght++; emptyness = false; for (int i = 0; i < leght; i++) { cout << "|" << mas[i] << "| "; } cout << endl; } else { cout << "DEK is full" << endl; } }; void pop_right() { //функція видалення справа if (leght == 0) { cout << "DEK is empty" << endl; return; } else { leght--; if (leght == 0) { emptyness = true; cout << "DEK is empty" << endl; return; } } for (int i = 0; i < leght; i++) { cout << "|" << mas[i] << "| "; } cout << endl; }; void pop_left() { // функція видалення зліва if (leght == 0) { cout << "DEK is empty" << endl; return; } else { for (int i = 1; i != leght; i++) { mas[i-1] = mas[i]; } leght--; if (leght == 0) { cout << "DEK is empty" << endl; return; } } for (int i = 0; i < leght; i++) { cout << "|" << mas[i] << "| "; } cout << endl; }; T back() { // повертає значення вершини if (leght > 0) { return mas[leght - 1]; } cout << "DEK is empty" << endl; return -1; }; }; int main(void) { DEK <int> dek; int array[7]; for (int i = 0; i < 7; i++) { // задаємо послідовність з 7 чисел cin >> array[i]; } cout << "Your numbers: "; for (int i = 0; i < 7; i++) { cout << array[i] << " "; } cout << endl; for (int i = 0; i < 7; i++) { if (array[i] < 0) { if (array[i] % 2 == 0) { dek.pop_right(); } if (array[i] % 2 != 0) { dek.pop_left(); } } if (array[i] > 0) { if (array[i] % 2 == 0) { dek.push_right(array[i]); } } } if (dek.back() != -1) { cout << "Back of DEK: " << dek.back() << endl; } else { cout << "DEK is empty"; } cout << "DEK is empty:" << dek.empty() << endl; cout << "Size of DEK: " << dek.size() << endl; }; / Висновок Вивчив поняття черги та ДЕКу, його властивості і навчився реалізувати їх програмно.