МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ « ЛЬВІВСЬКА ПОЛІТЕХНІКА » кафедра ЕОМ / ЗВІТ про виконання лабораторної роботи № 3 «Структура даних СТЕК » з дисципліни: « Програмування. Частина III. Структури даних та алгоритми » Вибір варіанту: № 8 = [7+84 ] % 21 + 1 Мета роботи: Вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач. Постановка задачі: Змоделювати стек на базі статичного масиву згідно з завданням. Написати основні операції для роботи зі стеком (push, pop, top, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в стек, а кожне від'ємне число має вилучати зі стеку один елемент. Виводити на екран динаміку вмісту стеку під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості стеку"(stack underflow) і "переповнення стеку" (stack overflow). Примітка: після реалізації стеку працювати з ним як з абстрактним типом даних, а не як з масивом. Реалізувати стек, у якому до опису стека додано логічну змінну FULL замість функції full(). Переписати основні функції роботи зі стеком з врахуванням цієї змінної. Після обробки заданої вхідної послідовності перевірити, чи стек буде “дзеркальним” (тобто перший елемент буде дорівнювати останньому, другий – передостанньому і т.д.). Алгоритм розв’язання задачі: Для реалізації стеку створимо клас , елементами якого є : масив data розміром CAPACITY для зберігання елементів стеку. Для визначення вершини стеку будемо використовувати змінну used, яка буде вказувати на першу вільну комірку стеку. Для ініціалізації стеку змінній used присвоїмо 0. Створимо наступні функції-методи класу: рush ( ) -> додаватиме елемент до стеку, якщо елемент послідовності буде більший від 0. рop ( ) -> вилучатиме елемент зі стеку, при від’ємному елементі послідовності. top ( ) -> повертатиме значення елемента, який знаходиться у вершині стеку не вилучаючи його. empty ( ) -> перевірятиме, чи стек порожній. Повертатиме значення true якщо це так, і false, якщо у стеку містяться елементи. Show ( ) -> виводить на екран вміст стеку. Змінна FULL матиме значення true, якщо стек повний і false, якщо стек неповний. Для перевірки дзеркальності стеку будемо прирівнювати перший і останній елемент стеку, кожного разу приближаючись до його середини. Динаміка вмісту стеку: Вхідна послідовність: 7,-7,-7,1,4,3,4,3,6,1,10,8 Примітка: вказує на положення used Функ. Stack() Push (7) Pop ( ) Pop ( ) Push (1) Push (4) Push (3)  Динаміка стеку         Опер. Used=0 data [used]=5; used++; used-- stack underflow data [used]=1; used++; data [used]=2; used++; data [used]=3; used++;   Push (4) Push (3) Push (6) Push (1) Push (10) Push (8)       ___10  ___10  data [used]=4; used++; data [used]=3; used++; data [used]=2; used++; data [used]=1; used++; stack overflow stack overflow   Результат виконання програми: / Висновки: на лабораторній роботі я вивчив фундаментальні абстрактні структури даних стек. Набув практичних навичок побудови стека, дослідив динаміку його вмісту та використав стек для розв'язання прикладної задачі. Додатки Stack.h #pragma once class stack { public: stack(void); ~stack(void); bool FULL; int used ; int data [7]; void рush (int x ); void рop (void); int top ( ); bool empty ( ); void show (); }; Stack.cpp #include <iostream> #include "stack.h" using namespace std; stack::stack(void) { used = 0; for (int i=0; i<7; i++) data [i]=0; FULL=false; } stack::~stack(void) { } void stack::рush (int x) { if (used>6) { cerr<<endl<<"!!! stack overflow !!!"<<endl; FULL=true; } else { data [used]=x; used++; FULL=false; } } void stack::рop (void) { if (used==0) cerr<<endl<<"!!! stack underflow !!!"<<endl; else used--; } int stack::top ( ) { return data [used-1]; } bool stack::empty ( ) { if (used==0) return true; else return false; } void stack::show () { cout<<"Вмiст стеку"<<endl<<endl; int i=used-1; while (i>=0) { cout<<data[i]<<endl; i--; } } main.cpp #include <iostream> #include "stack.h" using namespace std; int main () { setlocale (LC_ALL,"Ukrainian"); int posl [12]; cout<<"Введiть послiдовнiсть з 12 чисел"<<endl; for (int i=0;i<12;i++) cin>> posl [i]; cout<<endl<<"Введена послiдовнiсть:"<<endl; for (int i=0;i<12;i++) cout<<" "<< posl [i]; cout<<endl; stack obj ; for (int i=0; i<12;i++) { if (posl [i]>=0) obj.рush(posl [i]); else obj.рop (); obj.show (); } obj.show (); //створюєм стек копії stack copy; int size=0; //визначаємо кількість елементів while (obj.empty()==false) { copy.рush(obj.top()); size++; obj.рop(); } //ділимо стеки навпіл int tmp=size/2; for (int i=0; i<tmp; i++) { obj.рush(copy.top()); copy.рop (); } //якщо стек непарний, то вилучаємо середній елемент if (size%2 != 0) copy.рop (); //підраховуєм кількість однакових вершин стеків int lk=0; for (int i=0; i<tmp; i++) { if (copy.top()==obj.top()) lk++; copy.рop (); obj.рop (); } //якщо ця кількість співпадає з половиною елементів стеку - то він дзеркальний if (lk==tmp) cout<<"Стек дзеркальний"<<endl; else cout<<"Стек не є дзеркальний"<<endl; system ("pause"); return 0; }