Аисд лаб 2. аисд лаб. 2. Очередь
 Скачать 15.66 Kb.
|
|
ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ Федеральное государственное бюджетное образовательное учреждение высшего образования «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ им. проф. М. А. БОНЧ-БРУЕВИЧА» Кафедра программирования и вычислительной техники Дисциплина «Алгоритмы и структуры данных» Лабораторная работа №2 по теме «Очередь» Выполнил студент ак. группы ИКПИ-63 Котельников Г.А. Санкт-Петербург, 2018 Постановка задачи: Используя очередь, создать простейшую базу данных, содержащую сведения о студентах. Обьясненение задачи: Очередь - это последовательный список с переменной длиной, включение элементов в который происходит с одной стороны, а исключение элементов-с другой стороны списка. Это позволяет реализовать принцип FIFO (первый пришел-первый ушел). Принцип FIFO хорошо вписывается в реальные процессы, что позволяет широко использовать структуру типа "очередь" при машинном моделировании указанных процессов. Основными операциями с очередью являются: включение элемента и исключение элемента. При выполнении первой операции модифицируется указатель на первый свободный слот после последнего занятого слота в хвосте очереди(Р2). При выполнении второй операции модифицируется указатель первого занятого слота в голове очереди(Р1). Указатели Р1 и Р2 изменяются в пределах, которые определяются при описании очереди. Для обычной очереди всегда выполняется соотношение Р2>=Р1. Однако в ней, когда Р2 достигает максимальное значение, фиксируется переполнение очереди даже в том случае, если со стороны головы имеются свободные слоты. Поэтому на практике чаще используют кольцевую очередь, которая образуется замыканием простой очереди. Процедура замыкания заключается в том, что при достижении верхнего предела очереди указатель Р1 или Р2 переключаются на самый первый слот (если при этом первый слот занят, то эта операция является для указателя Р2 недоступной, так как в этом случае очередь является "переполненной"). Кольцевая очередь в отличии от обычной позволяет использовать пространство, отведенное в памяти под очередь, более эффективно, то есть полностью под занятые слоты. В заключении отметим, что очередь, как и стек относится к типу полустатических структур. Решение задачи реализована на языке C++. Был написан отдельный модуль очереди, реализующий все её операции. Программный код: main.cpp #include #include #include using namespace std; struct Student { std::string firstName; std::string secondName; std::string faculty; short int course; short int debtsCount; }; int main() { std::cout << "Laboratory work #2\nStudents database using queue" << std::endl; std::queue while (true) { std::cout << "1) Add student" << std::endl; std::cout << "2) Kill student" << std::endl; std::cout << "3) Get the student's information" << std::endl; int k; std::cin >> k; switch (k) { case 1 : { Student one; std::cout << "First name: "; std::cin >> one.firstName; std::cout << "Second name: "; std::cin >> one.secondName; std::cout << "Faculty: "; std::cin >> one.faculty; std::cout << "Course: "; std::cin >> one.course; std::cout << "Debts count: "; std::cin >> one.debtsCount; data.push(one); break; } case 2: { data.pop(); break; } case 3: { if (data.size() <= 0) { std::cout << "The queue is empty" << endl; break; } std::cout << "First name: " << data.front().firstName << std::endl; std::cout << "Second name: " << data.front().secondName << std::endl; std::cout << "Faculty: " << data.front().faculty << std::endl; std::cout << "Course: " << data.front().course << std::endl; std::cout << "Debts count: " << data.front().debtsCount << std::endl; break; } default: return 0; } } } queue.h #ifndef KEYBOARDTESTIKKK_QUEUE_H #define KEYBOARDTESTIKKK_QUEUE_H template class Queue { public: explicit Queue(int size) : _size(size) { _first = new T[size]; _last = _first; } bool empty() { return _first == _last; } bool full() { return _last >= _first + _size; } void push(T element) { if (full()) throw "Queue is fulfilled"; if (!empty()) _last++; *(_last) = element; } void pop() { if (empty()) throw "Queue is empty"; _last--; } T get() { return *(_first); } int size() { return _size; } void clear() { while (!empty()) this->pop(); } protected: T* _first; T* _last; int _size; }; #endif //KEYBOARDTESTIKKK_QUEUE_H |