Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ Лабораторна робота №3 з курсу «Програмування. Частина III. Структури даних та алгоритми» на тему: «Структура даних СТЕК» 1. МЕТА РОБОТИ Вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач. 2. ТЕОРЕТИЧНІ ВІДОМОСТІ Стек - динамічна структура даних, що представляє собою впорядкований набір елементів, у якій додавання нових елементів і видалення існуючих відбувається з одного кінця, який називається вершиною стека. Згідно визначення, елементи вилучаються зі стека в порядку, зворотному їхньому додаванню в цю структуру, тобто діє принцип LIFO (Last In, Fist Out – останнім прийшов, першим вийшов). Найбільш наочним прикладом організації стека служить дитяча пірамідка, в якій додавання й зняття кілець здійснюється саме відповідно до визначення стека. Можна уявити також стопку тарілок. Нижня тарілка із цієї стопки буде використана останньою, а верхня тарілка, яка була покладена в стопку останньою, буде використана першою. Подібне відбувається й в стеку. Стеки широко використовуються як для розв’язання прикладних задач, так і в системному програмному забезпеченні, включаючи компілятори і інтерпретатори. Історично склалося так, що дві основні операції для стека - помістити в стек і вилучити зі стека - одержали назву відповідно "заштовхнути" і "виштовхнути". Тому для реалізації стека необхідно створити дві функції: "push" (заштовхнути), що поміщає елемент у вершину стека, і "pop" (виштовхнути), що вилучає з вершини стека один елемент. Необхідно також передбачити певну область у пам'яті, де фактично буде зберігатися стек. Для цього можна використати масив або можна виділити область пам'яті, використовуючи засоби динамічного розподілу пам'яті. 3. ПОРЯДОК ВИКОНАННЯ РОБОТИ 1. При підготовці до лабораторної роботи, необхідно засвоїти теоретичний матеріал по темі і підготуватись до контрольного опитування по розумінню питань даної тематики. 2. Згідно з індивідуальним завданням розробити алгоритм розв’язання задачі. 3. Підготувати програмну реалізацію розробленого алгоритму. Засобами вбудованого тексто-вого редактора інтегрованого середовища набрати текст підготовленої програми. Відкомпілювати, налагодити та виконати програму. 4. Протестувати програму згідно зі складеною системою тестів і, при потребі, підкоректувати текст програми. Проаналізувати отримані результати. 5. Написати контрольне опитування по темі. 6. Оформити звіт по роботі. 4. ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ 4.1. Варіанти завдань Змоделювати стек на базі статичного масиву згідно з завданням. Переписати основні операції роботи зі стеком і перевірити правильність їх застосування. Для цього (якщо в завданні не вказано інший спосіб) задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа додавати в стек, а кожне від'ємне число має вилучати зі стеку один елемент. Виводити на екран динаміку вмісту стеку під час обробки заданої послідовності. Послідовність чисел задати такою, що вона демонструвала роботу основних функцій (push, pop, top, empty), а також можливості виникнення ситуацій вилучення з порожнього стеку або переповнення стеку. 15 варіант 15. Реалізувати стек, у якому вершина стека вказує на останній елемент стеку, а не на перший вільний елемент масиву. На вході задається послідовність цілих чисел. Якщо число X є парним, то воно додається в стек, якщо X є непарним числом, то зі стеку вилучається один елемент. Додаток(код програми) Main.cpp #include"stack.h" int main(void) { int size,temp; stack ST(10); cout<<"Vvedit rozmir poslidovnosti: "; cin>>size; for(int i=0;i<size;i++){ cout<<"\nVvedit element: "; cin>>temp; if(temp>=0) ST.push(temp); else ST.pop(); ST.show(); } if(ST.funcif()) cout<<"\nV poslidovnosti ye elementy > 10\n"; else cout<<"\nV poslidovnosti nema elementiv > 10\n"; return 0; } Stack.h #include<iostream> using namespace std; class stack { public: stack(int _size){ size=_size; data=new int [size]; used=-1; //вказує на вершину стеку } virtual ~stack(){ delete []data; } void push(int item){ used++; if(used>=size){ cout<<"\n!!!stack overflow!!!\n"; used--; } else{ data[used]=item; } } int top(){ return data[used]; } void pop(){ if(used==-1){ EMPTY=true; cout<<"\n!!!stack underflow!!!\n"; } else{ used--; } } void show(){ cout<<"Stack: "; for(int i=0;i<=used;i++){ cout<<" "<<data[i]; } cout<<"\n"; } bool funcif(){ for(int i=0;i<=used;i++) if(data[i]>10) return true; return false; } bool empty(){ if(used==-1) return true; else return false; } bool full(){ if(used==size) return true; else return false; } private: int size,used; int *data; bool FULL,EMPTY; }; Результат виконання програми: /