МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ Структура даних СТЕК до лабораторної роботи № 1 з дисципліни " Програмування. Частина III. Структури даних та алгоритми " Вибір варіанта індивідуального завдання № варіанта = [( 10 ) + ( 09) + (ASCII–код 71 ] % 20 + 1 Варіант 11 1. Мета роботи: вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач. 2. Постановка задачі Змоделювати стек на базі статичного масиву згідно з завданням. Переписати основні операції для роботи зі стеком і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в стек, а кожне від'ємне число має вилучати зі стеку один елемент. Виводити на екран динаміку вмісту стеку під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій (push, pop, top), а також генерувала виникнення ситуацій "втрати значимості стеку"(stack underflow) і, при потребі, "переповнення стеку" (stack overflow). Завдання №11 Реалізувати стек із “проштовхуванням”: вершина стека завжди знаходиться в першій комірці масиву; при “заштовхуванні” в стек наступного елемента, він розміщується у вершину стека, а всі решта елементів просуваються на одну позицію далі; при вилученні зі стека одного елемента всі решта елементів пересуваються назад. 3. Алгоритм виконання: - зчитується вхідна цифра; -здійснюється перевірка, чи ця цифра додатня, чи від’ємна: якщо додатня, то додається в стек, а якщо від’ємна, то з вершини стеку вилучається один елемент; - після зчитування і опрацювання останнього числа вміст стеку виводиться на екран. 4. Динаміка зміни вмісту стеку: 78, 97, 30, - 62, 72, 26, 20, - 65, 23, 57, 21                      78            97 78                     30 97 78          97 78                     72 97 78          26 72 97 78                   20 26 72 97 78        26 72 97 78                   23 26 72 97 78        57 23 26 72 97 78                 21 57 23 26 72 97 78      5. Результати виконання програми:
Висновок: На даній лабораторні я вивчив фундаментально абстрактну структуру даних стек. Набув практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач. Додаток #include "stack.h" #include <iostream> #include <cstring> #include <cstdlib> #include <ctime> using namespace std; int main() { int arr[30]; srand(time(0)); stack a("a"); for (int i = 0; i < 30; i++) { arr[i] = rand() % 100; } arr[15] = 0; std::cout << "Input sequence: "; for (int i = 0; i < 30; i++) { std::cout << arr[i] << " "; } std::cout << std::endl; for (int i = 0; i < 30; i++) { a.push(arr[i]); } return 0; } #include <cassert> #include <iostream> #include "stack.h" void stack::push(const int& entry) { assert(size() < CAPACITY); if (entry != 0) { data[used] = entry; ++used; } else { used = 0; } print(); } void stack::pop( ) { if (!empty()) { --used; print(); } } int stack::top( ) const { assert(!empty( )); return data[used-1]; } void stack::print() { std::cout << sname << ": "; for (int i = 0; i < used; i++) { std::cout << data[i] << " "; } std::cout << std::endl; } #include <cstdlib> // Надає тип size_t. #include <cstring> class stack { public: // ОПЕРАТОРИ ПЕРЕТВОРЕННЯ ТИПІВ ТА КОНСТАНТНІ ЧЛЕНИ static const int CAPACITY = 30; char sname[20]; // КОНСТРУКТОР stack(char* name) { used = 0; strcpy(sname,name);} // МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ void push(const int& entry); void pop( ); void print (); void wipe_out (); // КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ bool empty( ) const { return (used == 0); } int size( ) const { return used; } int top( ) const; private: int data[CAPACITY]; // Частково заповнений масив. int used; };