Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Стек
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2020
Тип роботи:
Лабораторна робота
Предмет:
Програмування Частина III Структури даних та алгоритми
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Звіт
про виконання лабораторної роботи № 4
з дисципліни:
«Програмування. Частина III. Структури даних та алгоритми »
на тему:
«Стек»
Львів-2020
Мета роботи: Вивчення фундаментальної абстрактної структури даних стек. Набуття практичних навичок побудови стека, дослідження динаміки його вмісту та використання стеків для розв'язання прикладних задач.
Завдання 1.
Змоделювати стек на базі статичного масиву згідно з завданням. Переписати основні операції роботи зі стеком і продемонструвати їх застосування при додаванні та вилученні елементів зі стеку. Для реалізації цього (якщо в завданні не вказано інший спосіб) задати послідовність з К цілих чисел (числа вводити з клавіатури). Всі парні числа додавати в стек, а кожне непарне число має вилучати зі стеку один елемент. Виводити на екран динаміку вмісту стеку під час обробки заданої послідовності.
Примітка: не працювати зі стеком як з масивом, а тільки як з абстрактним типом даних.
Результат:
/
Результат виконання програми
Код:
// Stack.h
#pragma once
#include <cassert>
#include <iostream>
template <typename ValueType>
class Stack
{
private:
size_t select = 0;
size_t MAX_SIZE = 1;
ValueType* data;
public:
template <typename ValueType>
Stack();
Stack(const size_t maxSIZE);
~Stack();
ValueType top() const;
size_t size() const;
void push(const ValueType& el);
void pop();
bool empty() const;
void print() const;
};
template <typename ValueType>
Stack<ValueType>::Stack(const size_t maxSIZE) : MAX_SIZE(maxSIZE)
{
data = new ValueType[MAX_SIZE];
select = 0;
}
template <typename ValueType>
Stack<ValueType>::~Stack() { delete[] this->data; }
template <typename ValueType>
bool Stack<ValueType>::empty() const
{
return (this->select == 0);
}
template <typename ValueType>
void Stack<ValueType>::pop()
{
--this->select;
}
template <typename ValueType>
ValueType Stack<ValueType>::top() const
{
assert(!empty());
return this->data[select-1];
}
template <typename ValueType>
size_t Stack<ValueType>::size() const
{
return this->select;
}
template <typename ValueType>
void Stack<ValueType>::push(const ValueType& el)
{
if (Stack<ValueType>::size() > MAX_SIZE)
{
MAX_SIZE *= (MAX_SIZE/2)/2;
ValueType* newStack = new ValueType[MAX_SIZE];
for (int i = 0; i < select; ++i)
newStack[i] = data[i];
delete[] data;
data = new ValueType[MAX_SIZE];
data = newStack;
delete[] newStack;
push(el);
}
else this->data[select++] = el;
}
template <typename ValueType>
void Stack<ValueType>::print() const
{
std::cout << "[ ";
for (int i = 0; i < select; ++i)
std::cout << data[i] << " ";
std::cout << "]\n";
}
// main.cpp
#include <iostream>
#include "Stack.h"
int main()
{
Stack<int> stack(5);
while (true)
{
int val = 0;
std::cout << "Enter value: ";
std::cin >> val;
if (val % 2 == 0)
stack.push(val);
else
{
if (!stack.empty())
stack.pop();
}
std::cout << " stack: = ";
if(!stack.empty())
stack.print();
std::cout << " empty: " << std::boolalpha << stack.empty() << std::endl;
std::cout << " top: " << stack.top() << std::endl;
std::cout << " size: " << stack.size() << std::endl;
}
return 0;
}
Індивідуальне завдання:
Варіант 8, З, Завдання № 7.
Написати програму для послiдовного зберiгання двох стекiв в масивi з N елементiв (стеки розміщуються один за одним: перша половина масиву – перший стек, друга половина масиву – другий стек). На вході задаються пари цiлих чисел (i,j), 1 i 2. Число j пари (i,j) з j>0 додається в i -ий стек; число j пари (i,j), з j<=0, не використовується, але з і-го стеку вилучається один елемент.
/
Результат виконання програми
Код:
// Stack.h
#pragma once
#include <cassert>
#include <iostream>
template <typename ValueType>
class Stack
{
private:
size_t select = 0;
size_t MAX_SIZE = 1;
ValueType* data;
public:
template <typename ValueType>
Stack();
Stack(const size_t maxSIZE);
~Stack();
ValueType top() const;
size_t size() const;
void push(const ValueType& el);
void pop();
bool empty() const;
void print() const;
};
template <typename ValueType>
Stack<ValueType>::Stack(const size_t maxSIZE) : MAX_SIZE(maxSIZE)
{
data = new ValueType[MAX_SIZE];
select = 0;
}
template <typename ValueType>
Stack<ValueType>::~Stack() { delete[] this->data; }
template <typename ValueType>
bool Stack<ValueType>::empty() const
{
return (this->select == 0);
}
template <typename ValueType>
void Stack<ValueType>::pop()
{
--this->select;
}
template <typename ValueType>
ValueType Stack<ValueType>::top() const
{
assert(!empty());
return this->data[select-1];
}
template <typename ValueType>
size_t Stack<ValueType>::size() const
{
return this->select;
}
template <typename ValueType>
void Stack<ValueType>::push(const ValueType& el)
{
if (Stack<ValueType>::size() > MAX_SIZE)
{
MAX_SIZE *= (MAX_SIZE/2)/2;
ValueType* newStack = new ValueType[MAX_SIZE];
for (int i = 0; i < select; ++i)
newStack[i] = data[i];
delete[] data;
data = new ValueType[MAX_SIZE];
data = newStack;
delete[] newStack;
push(el);
}
else this->data[select++] = el;
}
template <typename ValueType>
void Stack<ValueType>::print() const
{
std::cout << "[ ";
for (int i = 0; i < select; ++i)
std::cout << data[i] << " ";
std::cout << "]\n";
}
// main.cpp
#include <iostream>
#include "Stack.h"
int main()
{
size_t N;
std::cout << "Enter N: ";
std::cin >> N;
int *arr = new int[N];
Stack<int> stackArray[2] = { Stack<int>(N / 2), Stack<int>(N / 2) };
while (true)
{
std::cout << "Enter i,j: ";
int i, j;
std::cin >> i >> j;
if (i < 1 || i > 2)
{
std::cout << " [INFO] i can be only 1 or 2\n";
continue;
}
if (j > 0)
{
stackArray[i - 1].push(j);
if (i == 1)
arr[stackArray[0].size() - 1] = j;
else if (i == 2)
arr[(N / 2) + stackArray[1].size() - 1] = j;
std::cout << " push: from stackArray[" << i - 1 << "]" << std::endl;
}
else if (j <= 0)
{
if (!stackArray[i - 1].empty())
{
stackArray[i - 1].pop();
if (i == 1)
arr[stackArray[0].size()] = -1;
else if (i == 2)
arr[(N / 2) + stackArray[1].size()] = -1;
std::cout << " pop: from stackArray[" << i - 1 << "]" << std::endl;
}
}
std::cout << "Array: ";
for (int i = 0; i < N; ++i)
std::cout << arr[i] << " ";
std::cout << " \nstackArray[" << i - 1 << "]" << std::endl;
if (!stackArray[i - 1].empty())
{
std::cout << " stack: ";
stackArray[i - 1].print();
std::cout << " \ttop: \t\t\t" << stackArray[i - 1].top() << std::endl;
}
std::cout << " \tsize: \t\t\t" << stackArray[i - 1].size() << std::endl;
std::cout << " \tempty: \t\t\t" << std::boolalpha << stackArray[i - 1].empty() << std::endl;
}
return 0;
}
Висновок: Вивчив фундаментальну абстрактну структуру даних стек. Набув практичних навичок побудови стека, дослідив динаміку його вмісту та використання стеків для розв'язання прикладних задач.
14.04.2021 18:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора