МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” / Кафедра ЕОМ Звіт З лабораторної роботи №3 Структура даних СТЕК Львів – 2012 1. Мета роботи Вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач. 2.Постановка задачі Змоделювати стек на базі статичного масиву згідно з завданням. Написати основні операції для роботи зі стеком (push, pop, top, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) різних цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в стек, а кожне від'ємне число має вилучати зі стеку один елемент. Виводити на екран динаміку вмісту стека під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості стеку" (stack underflow) та "переповнення стеку" (stack overflow). Зауваження: працювати зі стеком як з абстрактним типом даних (АТД), а не як з масивом. 4. Реалізувати стек, у якому покажчик вершини стеку вказує на останній елемент стеку, а не на перший вільний елемент масиву. Задати послідовність, що складається з цифр 0 і 1. Кожна цифра 1 додається в стек, а кожна цифра 0 вилучає зі стеку один елемент. Після обробки всієї заданої вхідної послідовності перевірити, чи буде в стеку парн кількість елементів, чи ні . 3. Динаміка вмісту стеку Схематичне зображення динаміки вмісту стеку відповідно до заданої послідовності. Також демонструє штучний виклик помилок при виконанні програми. Розмір масиву під стек 4 елементів. 3.1. Послідовність чисел:3 3 7 5 4 -5 -1 - 1 2 -5 -4 -2 1 3.2. Схематичне зображення стеку після обробки кожного числа з вхідної послідовності поржній стек 3 3 7 5 4   




 Фунуції: push(3); push(3); push(7); push(5); push(4);stack underflow   поржній стек -5 -1 -1 2 -5   




 Фунуції: pop(); pop(); pop(); push(2); pop();   поржній стек -4 -2 1   


 Фунуції: pop(); pop();stack overflow push(1)   4.Алгоритм розв’язання задачі Для представлення стеку я створив клас, котрий є описаний у файлі mstack.h. Описав усі потрібні функції,. Для представлення динаміки стеку я написав окрему функцію show_dynamics(). Вона виводить динаміку стеку у зручному для читання вигдялі. Розмір масиву під стек я взяв на 10 елементів. 1. Спочатку створюємо стек та його копію для виводу динаміки основного стеку. 2. Вводимо з клавіатури послідовність з чисел для запису їх у стек. 3. Якщо число рівне «1», то записуємо його у стек, а якщо «0» то витягуємо зі стеку одне значення. 4. Після обробки всієї заданої вхідної послідовності визначаємо парність елементів що залишились в стеку. 5. Завершуємо роботу програми. 5. Результати виконання програми Задаю послідовність: 1 0 1 1 1 0 0 1 1 1 / / / / / / / / / / / Висновок : На даній лабораторній роботі я навчився працювати зі стеком, написав програму-приклад для вирішення задачі, що відповідала моєму варіанту. Додатки Код програми: // "stack.h" #include <iostream> #include <conio.h> #ifndef _STACK_H_ #define _STACK_H_ template <class T> class Stack { public: static const int CAPACITY = 4; private: T data[CAPACITY]; int used; public: Stack(); ~Stack() { }; bool empty() const; bool full() const; bool push(const T & k); bool pop(); T top() const; }; template <class T> Stack<T>::Stack() { used = -1; } template <class T> bool Stack<T>::empty() const { return used == -1; } template <class T> bool Stack<T>::full() const { return used == Stack<T>::CAPACITY - 1; } template <class T> bool Stack<T>::push(const T & k) { if (this->full()) return false; data[++used] = k; return true; } template <class T> bool Stack<T>::pop() { if (this->empty()) return false; --used; return true; } template <class T> T Stack<T>::top() const { return data[used]; } #endif //main.cpp #include "stack.h" #include <iostream> #include <conio.h> using namespace std; typedef int TP; const int size = 10; TP item[size]; void ViewStack(Stack<TP> s); bool is_even(Stack<TP> s); void ViewArr(); int counter=1; int main(void) { int i = 0; Stack<TP> st; TP v; while (i != size) { system("cls"); cout << "Enter sequence with " << size << " elements (1 or 0):\n " ; if (!(cin >> item[i])) return 0; i++; } system("cls"); for (i = 0; i < size; ++i) { switch (item[i]) { case 0: { if (st.empty()) { ViewStack(st); cout << "Error! Stack underflow\n"; getch(); } else { v = st.top(); st.pop(); ViewStack(st); cout << "Element " << v << " popped from the stack.\n"; getch(); counter-- ; } break; } case 1: { if (st.full()) { ViewStack(st); cout << "Error! (stack overflow) \n"; getch(); } else { st.push(item[i]); ViewStack(st); cout << "Element " << st.top() << " push to stack.\n"; getch(); counter++ ; } break; } default: { break; } } } cout << "\n"; if (is_even(st)) { ViewStack(st); cout << "\nIn stack even number of elements.\n"; getch(); } else { ViewStack(st); cout << "\nIn stack odd number of elements.\n"; getch(); } return 0; } void ViewStack(Stack<TP> s) { system("cls"); ViewArr(); while (!s.empty()) { cout <<"\n" " |__"; cout << s.top() << "__|" << endl ; s.pop(); } cout << endl; } bool is_even(Stack<TP> s) { int n = 0; while (!s.empty()) { ++n; s.pop(); } return n % 2 == 0; } void ViewArr() { for (int i = 0; i < size; ++i) cout << item[i] << " "; cout << "\n"; if (counter%2==0 && counter!=0) { cout<<"\n"<<"Couter of elements is PARNE"; } else if (counter%2!=0 && counter!=0) { cout<<"\n"<<"Counter of elements is NeParne"; }else{ cout<<"\n"<<"Counter of elements in stack equal 0"; } }