Міністерство освіти і науки, молоді та спорту України Національний університет “Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 3 на тему: " Структура даних СТЕК" з дисципліни: " Програмування. Частина III. Структури даних та алгоритми " № варіанта = [2+ 82] % 21 + 1=1 1. МЕТА РОБОТИ Вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач. ПОСТАНОВКА ЗАДАЧІ Змоделювати стек на базі статичного масиву згідно з завданням. Написати основні операції для роботи зі стеком (push, pop, top, empty, full) і продемонструвати правильність їх виконання. Для цього (якщо в завданні не вказано інший спосіб) в програмі на вході задати послідовність з К (К>10) різних цілих чисел (числа вводити з клавіатури). Всі додатні числа послідовно заносити в стек, а кожне від'ємне число має вилучати зі стеку один елемент. Виводити на екран динаміку вмісту стека під час обробки заданої послідовності. Вхідну послідовність чисел задати такою, щоб вона демонструвала роботу основних операцій та генерувала виникнення ситуацій "втрати значимості стеку" (stack underflow) та "переповнення стеку" (stack overflow). Зауваження: працювати зі стеком як з абстрактним типом даних (АТД), а не як з масивом. 1. Реалізувати за допомогою одного масиву з N елементiв два стеки. Стеки повинні рости з кінців масиву назустріч один одному. На вході задати пари цiлих чисел (i,j), де i-це число 1 або 2, j – любе число. Перше число і кожної пари (i,j) вказує на номер стеку (1 або 2), з яким виконувати роботу. Якщо друге число j кожної пари (i,j) є додатнім (j>0), то воно додається в і – тий стек, якщо j<0, то з і-го стеку вилучається один елемент, j=0 – ігнорується. Після обробки всієї заданої вхідної послідовності переписати всі парні числа обох стеків в перший стек, а всі непарні – в другий. 3. Динаміка вмісту стеку (або масиву) 3.1. Задаємо вхідну послідовність 10 цілих чисел: (1, 2),(1, -6), (1, -7), (1, 4), (2, 13), (2, 16),(2,9),(1,7)(2, 4),(2, 17). 3.2. Схематичне зображення масиву після обробки кожного числа з вхідної послідовності
Порожній стек
push(2);
pop( );
pop( ); Втрата значимості стеку!
push (4);
push (13);
push (16);
push (9);
push (7);
push (4);
push (13); Переповнення стеку! 3.3. Зміна вмісту стеку згідно умови індивідуального завдання
4. Алгоритм розв’язання задачі ШАБЛОННИЙ ПАРАМЕТР, ОПЕРАТОРИ ПЕРЕІМЕНОВАННЯ ТИПІВ ТА КОНСТАНТНІ ЧЛЕНИ класу Stack<T> Шаблонний параметр T предтставляє собою тип елементів, що зберігаються у стеку. Він може бути довільним вбудованим типом в мові С++ а також структурою, класом (в якому визначений конструктор по замовчуванню),конструктор копіювання і оператор присвоєння. Stack<T>:: CAPACITY предтаставляє максимальну кількість елементів довільного стеку (як тільки ця кількість буде досягнута, додавання елементів у стек припиняється). КОНСТРУКТОР ШАБЛОННОГО КЛАСУ Stack<Т> Stack() Післяумова: стек ініціалізується порожнім МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ шаблонного класу stack<Item>: void push(const int i, const T & k) Передумова: стек не є повним. Післяумова: в стек занесена нова копія елемента. void pop(const int i ) Передумова: стек не є порожнім. Післяумова: вилучена вершина стека. КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ шаблонного класу Stack<T>: T top(const int i) const Передумова: стек не є порожнім. Післяумова: повертається вершина стека, однак стек при цьому не змінюється. bool empty(int i ) const Післяумова: повертає значення true, якщо стек порожній, і значення false, якщо це не так. 5. Результати виконання програми / Висновки. На цій лабораторній роботі я вивчив фундаментальну абстрактну структуру даних стек, набув практичних навичок побудови стека, дослідив динаміку його вмісту та використання стеків для розв'язання прикладних задач.