Міністерство освіти і науки, молоді та спорту України Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 4 на тему: "Структура даних ЧЕРГА" з дисципліни: " Програмування. Частина III. Структури даних та алгоритми " Вибір варіанту: № варіанта = [(день народження) + (ASCII–код першої літери прізвища – велика латинська літера) + (ASCII–код другої літери прізвища – мала латинська літера)] % 30 + 1 (7 + 67 [буква С] + 104[буква h]) % 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<stdio.h> #include<conio.h> #include<math.h> #define n 5 class Queue { private: int qu[n]; public: int k,l; Queue() { k=-1; for(int i=0;i<n;i++) qu[i]=0; l=0; } ~Queue() { }; Queue(Queue &Queue){}; void push(int a) { int q=0; if (k<n-1) { k++; qu[k]=a; } else { printf("\n!!! Queue overflow\n"); for(int i=0;i<n;i++) { qu[i]=qu[i+l]; } k=k-l+1; l=0; qu[k]=a; } } void pop() { if (l<=k) { qu[l]=0; l++; } else printf("\n!!! Queue underflow\n"); } int front() { return qu[l]; } bool empty() { return (k<l); } bool full() { return ((k>l)); } void print() { for(int i=0;i<n;i++) printf("%d ",qu[i]); printf("\n"); for(int i=0;i<l;i++) { printf(" "); } printf("b "); if(k!=l) { for(int i=l+1;i<k;i++) { printf(" "); } printf("e\n"); } else printf("\n"); } }; void main() { Queue q1; int k; int z; int p=0; printf("Enter size of the array: \t"); scanf("%d", &k); int g[20]={0}; printf("Enter the array elements: \n"); for (int i=0;i<k;i++) { scanf("%d",&g[i]); printf("------\n"); } for (int i=0;i<k;i++) { if (g[i]>0) q1.push(g[i]); else if (g[i]<0) q1.pop(); q1.print(); p=p+1; } int a[10]={0},j=0, max=0; while (!(q1.empty())) { z=q1.front(); a[j]=z; j++; q1.pop(); } for(int i=0;i<j-1;i++) if (a[max]<a[i]) max=i; printf("%d",a[max]); a[max]=0; for(int i=0;i<j-1;i++) if (a[max]<a[i]) max=i; printf(" %d",a[max]); a[max]=0; for(int i=0;i<j-1;i++) if (a[max]<a[i]) max=i; printf(" %d\n",a[max]); getch(); } Результат виконання програми: / Рис1. Ескіз вікна з результатом виконання програми Висновок: Виконавши дану лабораторну роботу, я вивчив фундаментальну абстрактну структуру даних – чергу, отримав практичні навики побудови черги, дослідив динаміку її вмісту та використання черги для розв'язання прикладних задач.