Міністерство освіти і науки України Національний університет „Львівська політехніка” Звіт з лабораторної роботи № 5 з дисципліни: “Структури даних та алгоритми» На тему: “ Структура даних ЧЕРГА” Варіант 4 1. МЕТА РОБОТИ Вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач. 2. ЗАВДАННЯ 2.1 Постановка задачі Змоделюйте чергу (або дек) згідно з завданням. Перепишіть основні операції для роботи з чергою (деком), і продемонструйте їх застосування для операцій додавання і вилучення елементів в чергу (дек). Для цього задайте послідовність з N цілих чисел. Всі додатні числа послідовно заносяться в чергу (дек), кожне від’ємне число вилучає з черги (деку) один елемент. 4. Змоделюйте чергу, в якій реалізований такий механізм вилучення елемента з черги: початок черги завжди знаходиться в першому елементі масиву; при вилученні одного елемента з черги, всі решта елементів пересуваються на одну позицію ближче до початку масиву. 2.2 Алгоритм розв’язання задачі 2.2.1 Створюю новий проект C++ в середовищі розробки Visual Studio 2017 2.2.2 Моделюю стек на базі статичного масиву згідно з завданням, переписуючи основні операції роботи зі стеком: void pop(); void push(const Item& entry); void imp_pop(); // видаляє елемент та зміщує всі інші на позицію вниз // КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ bool empty() const { return (count == 0); } Item front() const; // перший елемент Item rear() const; // останній елемент void printQueue(); // вивід черги Item peek(int n) const; // доступ по індексу int getfirst() { return first; } // індекс першого елемента int getlast() { return last; } // індекс останнього елемента size_type size() const { return count; } // кількість елементів2.2.3 Виконую індивідуальне завдання згідно з варіантом; 2.2.4 Закінчую створення програми та перевіряю правильність її виконання. 2.3 Результати виконання програми / Рис 2.3 Результат виконання програми ВИСНОВКИ Під час виконання лабораторної роботи я набув практичних навичок побудови черги, дослідив динаміку його вмісту та використання черг для розв'язання прикладних задач. ДОДАТКИ Файл nQueue.h #pragma once #ifndef MAIN_SAVITCH_STACK1_H #define MAIN_SAVITCH_STACK1_H #include <cstdlib> // Надає тип size_t. #include<iomanip> namespace main_savitch_7A { template <class Item> class nQueue { public: // ОПЕРАТОРИ ПЕРЕІМЕНОВАННЯ ТИПІВ ТА КОНСТАНТНІ ЧЛЕНИ typedef size_t size_type; typedef Item value_type; static const size_type CAPACITY = 30; // КОНСТРУКТОР nQueue(); // МОДИФІКУЮЧІ ФУНКЦІЇ-ЧЛЕНИ void pop(); void push(const Item& entry); void imp_pop(); // видаляє елемент та зміщує всі інші на позицію вниз // КОНСТАНТНІ ФУНКЦІЇ-ЧЛЕНИ bool empty() const { return (count == 0); } Item front() const; // перший елемент Item rear() const; // останній елемент void printQueue(); // вивід черги Item peek(int n) const; // доступ по індексу int getfirst() { return first; } // індекс першого елемента int getlast() { return last; } // індекс останнього елемента size_type size() const { return count; } // кількість елементів private: Item data[CAPACITY]; size_type first; size_type last; size_type count; // ДОПОМІЖНІ ФУНКЦІЇ-ЧЛЕНИ size_type next_index(size_type i) const { return (i + 1) % CAPACITY; } }; } #endif Файл nQueue.cpp #include "stdafx.h" #include "nQueue.h" #include <cassert> namespace main_savitch_7A { template <class Item> const typename nQueue<Item>::size_type nQueue<Item>::CAPACITY; template <class Item> nQueue<Item>::nQueue() { count = 0; first = 0; last = CAPACITY-1; } template <class Item> Item nQueue<Item>::front() const { assert(!empty()); return data[first]; } template <class Item> Item nQueue<Item>::rear() const { assert(!empty()); return data[last]; } template <class Item> void nQueue<Item>::pop() { first = next_index(first); count--; } template <class Item> void nQueue<Item>::imp_pop() { for (int i = 0; i < count; i++) { data[i] = data[i + 1]; } data[last] = NULL; last--; count--; } template <class Item> void nQueue<Item>::push(const Item& entry) { assert(size() < CAPACITY); last = next_index(last); data[last] = entry; count++; } template<typename T> void nQueue<T>::printQueue() { cout << "Current Queue:"; for (int i = this->getlast(); i >= this->getfirst(); i--) { cout << data[i] << "("<<i<<")"<<" "; } cout << endl; } template <class Item> Item nQueue<Item>::peek(int n) const { assert(!empty()); return data[n]; } } Файл lab5.cpp #include "stdafx.h" #include "nQueue.cpp" #include <iostream> using namespace std; using namespace main_savitch_7A; int main() { nQueue<int>MyQueue; int amount; cout << "Enter the number of items in the queue:"; cin >> amount; int index = 0; while (index<amount-1) { cout << "Add an element if the value is positive and delete if negative:"; int nEoQ; cin >> nEoQ; if (nEoQ >= 0) { MyQueue.push(nEoQ); MyQueue.printQueue(); index = MyQueue.getlast(); } else { MyQueue.imp_pop(); MyQueue.printQueue(); } } return 0; }