МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ
Лабораторна робота № 3 Структура даних СТЕК 1 Мета роботи: Вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач. 2 Постановка задачі: Реалізувати стек, у якому до опису стека додано функцію change_top, яка заміняє елемент, що знаходиться у вершині стека, заданим елементом. Кожний раз, коли після операції вилучення у вершині стека опиняється непарне число, то треба замінити його наступним парним числом. Після обробки всієї заданої вхідної послідовності перевірити, чи всі числа у стеку будуть більшими за 10, чи ні. 3 Алгоритм роз’вязку задачі: Стек організовуємо у вигляді шаблонного класу. Це дає можливість працювати з усіма стандартними типами даних. Спочатку по черзі вносимо 15 елементів. Дані вносяться чи не вносяться в стек. Перевіряючи чи вершина стеку парна при вилученні, якщо ні замінюємо наступним парним числом, заносячи дані в основний стек. Перевіряємо чи всі числа в стеку більші десяти по черзі вилучаючи їх зі стеку і заносячи в додатковий стек. Перевіривши всі елементи заносимо їх назад в основний стек і виводимо повідомлення. 4 Динаміка вмісту стеку: 5 Результати виконання програми:
Висновки: На цій лабораторній роботі я ознайомився з cтруктурою даних стек. Дослідив принципи і методи роботи зі стеком. Додатки: //----------------------------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 << "Chysla > 10: TAK"; else cout << "Chysla > 10: HI"; getchar();getchar(); } //----------------------------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] << " " << "size:" << size()<<endl; else cout << " empty" << endl; } };