У роботі розглядаються
- Структури даних
- Стек
- Алгоритми
- Мова програмування C++
- Динамічна пам'ять
- Шаблони класів
Звіт про виконання лабораторної роботи № 4 з дисципліни «Програмування. Частина III. Структури даних та алгоритми» на тему «Стек»
Оригінальна назва роботи
Стек
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Комп’ютерні науки
Кафедра:
Кафедра програмного забезпечення
Інформація про роботу
Рік:
2020
Тип роботи:
Лабораторна робота
Предмет:
Програмування Частина III Структури даних та алгоритми
Група:
КН-31
Коротко про документ
Про що ця робота
Цей звіт присвячено вивченню абстрактної структури даних стек та набуттю практичних навичок її побудови. У роботі наведено реалізацію стека на C++ та виконання індивідуального завдання з послідовного зберігання стеків.
Зміст і розділи
- Мета роботи
- Завдання 1
- Результат
- Код
- Індивідуальне завдання
- Висновок
Для кого:Студенти технічних спеціальностей вищих навчальних закладів
Викладачі:Викладач кафедри
Ключові поняття
стекструктури данихалгоритмшаблон класустатичний масивpushpopC++пам'ятьабстрактний тип даних
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Звіт
про виконання лабораторної роботи № 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;
}
Висновок: Вивчив фундаментальну абстрактну структуру даних стек. Набув практичних навичок побудови стека, дослідив динаміку його вмісту та використання стеків для розв'язання прикладних задач.
Допоможи студентському архіву
Ми допомогли тобі — допоможи наступному студенту
Оголошення від адміністратора
Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!