Міністерство освіти і науки, молоді та спорту України Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт про виконання лабораторної роботи № 4 на тему: "Структура даних ЧЕРГА" з дисципліни:" Програмування. Частина III. Структури даних та алгоритми " Вибір варіанту: № варіанта = [(день народження) + (ASCII–код першої літери прізвища – велика латинська літера) + (ASCII–код другої літери прізвища – мала латинська літера)] % 30 + 1 (11 + 86 +112) % 30 + 1 = 29 Львів – 2013 Мета роботи: Вивчення фундаментальної абстрактної структури даних - черги. Набуття практичних навичок побудови черги, дослідження динаміки її вмісту та використання черг для розв'язання прикладних задач. Постановка задачі: Змоделювати чергу або дек на базі статичного масиву згідно з завданням. Переписати основні операції для роботи з чергою (push, pop, front, empty, full) або деком (push_left, push_right, pop_left, pop_right, front_left, front_right, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в чергу (дек), кожне від’ємне число має вилучати з черги (деку) один елемент (при роботі з деком, парні числа працюють з правим кінцем деку, а непарні – з лівим). Виводити на екран динаміку вмісту черги (деку) під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості черги"(queue underflow) і "переповнення черги" (queue overflow) або "втрати значимості деку"(deq underflow) і "переповнення деку" (deq overflow). Примітка: після реалізації черги або деку працювати з ними як з абстрактними типами даних, а не як з масивами. 29. Змоделювати чергу, в якій реалізований такий механізм додавання нового елемента: якщо досягнутий кінець масиву, то всі елементи черги пересуваються на початок масиву. Після обробки всієї заданої вхідної послідовності знайти три найбільших елемента черги. Динаміка вмісту черги:  B E  0)       - порожня черга      B E   B E   B E  1) 1       2)        3)  3         B E   B E   B E  4)  3 4     5)   4     6)   4  6       B E      7)   4 6 7      Код програми: #include<iostream> using namespace std; template<class T> class deque{ private: int size; int front, back; T *data; public: deque(int size) :front(0), back(-1){ this->size = size; data = new T[size]; } void push_back(const T& element){ if (back + (-front) == size){ cout << "deque is full" << endl; exit(1); } else{ back++; data[back] = element; } } void push_front(const T& element){ if (back + (-front) == size){ cout << "deque is full" << endl; exit(1); } else{ front--; data[front] = element; } } T& pop_front(){ T temp; if (back + (-front) == 0){ cout << "deque is empty" << endl; exit(1); } else{ temp = data[front]; front++; } return temp; } T& pop_back(){ T temp; if (back + (-front) == 0){ cout << "deque is empty" << endl; exit(1); } else{ temp = data[back]; back--; } return temp; } void print(){ for (int i = front; i <= back; i++){ cout << data[i] << " "; } } void commute_left(const T& element){ data[front] = element; } void commute_right(const T& element){ data[back] = element; } int length(){ return (-front) + back; } T& getFront(){ return data[front]; } T& getRear(){ return data[back]; } bool isSpecular(){ int iter = 0; if ((-front + back - 1) % 2 == 0){ for (int i = back - 1, j = front; i >= front, j < back; i--, j++){ if (data[j] == data[i]) iter++; } if (iter - 1 == (-front + back - 1)) return true; else return false; } else{ return false;; } } }; void main(){ setlocale(LC_ALL, "Ukrainian"); deque<int> dec(10); int a; cout << "заносiть деякi числа в чергу" << endl; for (int i = 0; i < 10; i++){ cin >> a; if (a >= 0){ if (i % 2 == 0) dec.push_back(a); if (i % 2 != 0) dec.push_front(a); if (dec.getFront() > 50) dec.getFront() -= 10; if (dec.getRear() > 50) dec.getRear() -= 10; } if (a < 0){ if (a % 2 == 0){ dec.pop_back(); } if (a % 2 != 0){ dec.pop_front(); } } dec.print(); } cout << "введiть числа якi хочете замiнити на початку i в кiнцi черги" << endl; cin >> a; dec.commute_left(a); cin >> a; dec.commute_right(a); dec.print(); if (dec.isSpecular() == 0) cout << "чи дзеркальна черга: НI"<<endl; if (dec.isSpecular() == 1) cout << "чи дзеркальна черга: ТАК"<< endl; } Результат виконання програми: / Рис1. результат виконання програми Висновок: Виконавши дану лабораторну роботу, я вивчив фундаментальну абстрактну структуру даних – чергу, отримав практичні навики побудови черги, дослідив динаміку її вмісту та використання черги для розв'язання прикладних задач.