МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ / Лабораторна робота № 3 Структура даних СТЕК Львів – 2010 1 Мета роботи: Вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач. 2 Постановка задачі: Реалізувати за допомогою одного масиву з N елементiв два стеки. Стеки повинні рости з кінців масиву назустріч один одному. На вході задається послідовність пар цiлих чисел (X,Y), де X - додатнє ціле число, Y - число 1 або 2. Якщо число X є парним, то воно додається в стек, якщо X є непарним числом, то зі стеку вилучається один елемент. Друге число Y кожної пари (X,Y) вказує на номер стеку, з яким виконується робота. Після обробки всієї заданої вхідної послідовності визначити в якому стеку добуток всіх парних чисел буде найменьшим. 3 Алгоритм роз’вязку задачі: Стек організовуємо у вигляді шаблонного класу. Це дає можливість працювати з усіма стандартними типами даних. Спочатку вводим кількість елементів а потім по черзі задаєм пари Х(число) та Y(номер стеку). Дані вносяться в перший чи другий стек якщо чило додатнє або видаляються якщо відємне. Після обробки всієї заданої вхідної послідовності визначаєм у якому стеку добуток парних чисел найменший. 4 Динаміка вмісту стеку: Задана послідовність: (2,1); (6,2); (12,2); (4,1); (4,2); (2,2); (6,1); (6,2); (3,1); (8,1) n дія – почерговність занесення в стек. Стек 1: Порожній стек Елементи вхідної послідовності    2 4 6 3 8     Data[4]     Data[3]     Data[2]     Data[1]  Used(   Data[0]        Data[4]     Data[3]     Data[2]   Used(   Data[1]   2  Data[0]        Data[4]     Data[3]   Used(   Data[2]   4  Data[1]   2  Data[0]        Data[4]   Used(   Data[3]   6  Data[2]   4  Data[1]   2  Data[0]        Data[4]     Data[3]   Used(   Data[2]   4  Data[1]   2  Data[0]        Data[4]     Data[3]   Used(   Data[2]   4  Data[1]   2  Data[0]      Функції : push(2);1 дія push(4);4 дія push(9); 7 дія pop();9 дія push(8); 10 дія   Стек 2: Порожній стек Елементи вхідної послідовності    6 12 4 2 6     Data[4]     Data[3]     Data[2]     Data[1]  Used(   Data[0]        Data[4]     Data[3]     Data[2]   Used(   Data[1]   6  Data[0]        Data[4]     Data[3]   Used(   Data[2]   12  Data[1]   6  Data[0]        Data[4]   Used(   Data[3]   4  Data[2]   12  Data[1]   6  Data[0]        Data[4]   2  Data[3]   Used( 4  Data[2]   12  Data[1]   6  Data[0]      6  Data[4]   2  Data[3]   Used( 4  Data[2]   12  Data[1]   6  Data[0]      Функції : push(6);2 дія push(12); 3 дія push(4); 5 дія push(2);6 дія push(6); 8 дія   5 Результати виконання програми: / Висновки: На цій лабораторній роботі я ознайомилась з cтруктурою даних стек. Дослідила принципи і методи роботи зі стеком. Додатки: #include <iostream> #include <conio.h> using namespace std; class Stack{ public: Stack(int N){ right=N; n=N; left=0; } void Push_left(int a){ k[left]=a; left++; } void Push_right(int a){ k[right]=a; right--; } int Top_left(){ return k[left-1]; } int Top_right(){ return k[right+1]; } void Pop_left(){ if(this->empty_left()==false) left--; } void Pop_right(){ if(this->empty_right()==false) right++; } bool empty_left(){ if(left==0) return true; else return false; } bool empty_right(){ if(right==n) return true; else return false; } bool full(){ if(left==0 && right==n) return true; else return false; } void Print_left(){ cout<<"Stack #1:\n"; if (this->empty_left()!=1){ for(int i=0;i<left;i++) cout<<k[i]<<" "; cout<<endl; } else cout<<"Stack #1 is empty!\n"; } void Print_right(){ cout<<"Stack #2:\n"; if (this->empty_right()!=1){ for(int i=n;i> right;i--) cout<<k[i]<<" "; cout<<endl; } else cout<<"Stack #2 is empty!\n"; } void Print(){ this->Print_left(); cout<<"\n"; this->Print_right(); } void Func(){ int a=1,b=1; for(;this->empty_left()!=true;){ if(this->Top_left()%2==0) a=a*this->Top_left(); this->Pop_left(); } for(;this->empty_right()!=true;){ if(this->Top_right()%2==0) b=b*this->Top_right(); this->Pop_right(); } if(a>b) cout<<"Answer: 1st Stack!"; if(a<b) cout<<"Answer: 2st Stack!"; if(a==b) cout<<"Steky rivni"; } private: int n; int k[30]; int left; int right; }; int main(){ int a=1,b,c; Stack k(40); cout<<"Vvedit' kilkist' chusel: "; cin>>c; for(int i=0;i<c;i++){ cout<<endl<<i+1<<".X= "; cin>>a; cout<<endl<<i+1<<".Y= "; cin>>b; if(a%2==0){ if(b==1) k.Push_left(a); else k.Push_right(a); } if(a%2==1){ if(b==1) k.Pop_left(); else k.Pop_right(); } system("cls"); //cout<<"\n--------------------------"<<endl; k.Print(); } k.Func(); getchar(); getchar(); return 0; }