Міністерство освіти і науки, молоді та спорту України Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 3 на тему: "Структура даних СТЕК" з дисципліни: " Програмування. Частина III. Структури даних та алгоритми " Вибір варіанту: № варіанта = [(день народження) + (місяць народження) + (ASCII–код першої літери прізвища – велика латинська літера) ] % 20 + 1 (10 + 2 + 67 [буква С]) % 20 + 1 = 20 Львів – 2013 Мета роботи: Вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач. Постановка задачі: 20. Реалізувати стек, у якому до опису стека додано функцію change_top, яка заміняє елемент, що знаходиться у вершині стека, заданим елементом. Кожний раз, коли після операції вилучення у вершині стека опиняється непарне число, то треба замінити його наступним парним числом. Після обробки всієї заданої вхідної послідовності перевірити, чи всі числа у стеку будуть більшими за 10, чи ні. Алгоритм розв’язання задачі: Стек організовуємо у вигляді шаблонного класу. Це дає можливість працювати з усіма стандартними типами даних. Спочатку по черзі вносимо 15 елементів. Дані вносяться чи не вносяться в стек. Перевіряючи чи вершина стеку парна при вилученні, якщо ні замінюємо наступним парним числом, заносячи дані в основний стек. Перевіряємо чи всі числа в стеку більші десяти по черзі вилучаючи їх зі стеку і заносячи в додатковий стек. Перевіривши всі елементи заносимо їх назад в основний стек і виводимо повідомлення. Динаміка вмісту стеку: used->    67   45   34   56   43   23   24   34   4   Код програми: Stack.h template<class item> class stack{ private: //Вказівник на вершину стеку int used; //Масив елементів стеку item *items; //Capacity - ємність стеку int Capacity; public: //Конструктор з заданою ємністю stack(int n) { Capacity = n; items = new item[Capacity]; used = 0; } //Конструктор заповняє стек масивом stack(item a[],int arrsize) { int i; Capacity = arrsize; items = new item[Capacity]; used = 0; for (i = 0; i < arrsize; i++) push(a[i]); } //Деструктор ~stack() { delete[] items; } //Методи стеку //Заміна вершини void change_top(item it) { if (empty()!=1) items[used-1] = it; } //Очищення стеку void clear() { used=0; } //Перевірка чи стек порожній bool empty() { if (used==0) return true; else return false; } //Розмір стеку int size() { return used; } //Вершина стеку item top() { if(empty()!=1) return items[used - 1]; } //Занесення до стеку void push(item it) { if(size() < Capacity) { items[used] = it; used++; } } //Вилучення зі стеку void pop() { if(empty()!=1) used--; } //Вивести вміст стеку void print() { cout << "stack:"; if(empty()!=1) { for(int i = 0; i < size(); i++) { cout << items[i] << " "; } cout << " " << "size:" << size() << endl; } else cout << " empty" << endl; } }; Main.cpp #include "Stack.h" #include <iostream> #include <stdio.h> #define N 20 // Ємність стеку #define C 5 // Кількість єлементів стеку using namespace std; void main(void) { bool flg=1; int a,i; stack<int> stc(N); stack<int> tmp(N); // Заповнюємо перший стек for(i = 0; i < C; i++) { cout << "a="; cin >> a; if (a < 0) { stc.pop(); if(stc.top() % 2 == 1) stc.change_top(stc.top()+1); } else stc.push(a); stc.print(); } a=stc.size(); for(i=0; i < a; i++) { // Підраховуємо чи всі елементи стеку більші десяти // вилучаємо елементи заносячи їх в додатковий стек flg = flg && (stc.top() > 10); tmp.push(stc.top()); stc.pop(); stc.print(); } for(i = 0; i < a; i++) { stc.push(tmp.top()); tmp.pop(); stc.print(); } if (flg)cout << "Numbers > 10: Yes"; else cout << "Numbers > 10: No"; getchar();getchar(); } Результат виконання програми: / Рис1. Ескіз вікна з результатом виконання програми Висновок: На цій лабораторній роботі я ознайомився з cтруктурою даних стек. Дослідив принципи і методи роботи зі стеком.