1

Тема: Класи та об'єкти в С++

У  мене є завдання: Створити клас – стек на основі одновимірного масиву цілих чисел. Визначити конструктор, деструктор, функції для додавання елемента до стеку та вилучення елемента зі стеку, обчислення кількості елементів у стеку, мінімального та максимального елемента.
Ось код:

#include<iostream>

using namespace std;

class STACK
{
private:
    int* stack;
    int count;

public:

    STACK()
    {
        count = 0;
    }

    void add(int item)
    {

        int* point;
        point = stack;
        stack = new int[count + 1];
        count++;
        for (int i = 0;i < count - 1;i++)
            stack[i] = point[i];
        stack[count - 1] = item;
        if (count > 1)
            delete[]point;
    }

    int del()
    {
        if (count == 0)
            return 0;
        count--;
        return stack[count];
    }
    int Head()
    {
        if (count == 0)
            return 0;
        return stack[count - 1];
    }
    
        ~STACK()
    {
        if (count > 0)
            delete[]stack;
    }

    int Count()
    {
        return count;
    }

    void Print()
    {
        int* p;
        p = stack;
        cout << "Stack:" << endl;
        if (count == 0)
            cout << "is empty." << endl;
        for (int i = 0;i < count;i++)
        {
            cout << "Item[" << i << "]=" << *p << endl;
            p++;
        }
        cout << endl;
    }
};

int main()
{
    STACK st;

    st.Print();

    st.add(2);
    st.add(4);
    st.add(15);
    st.add(6);
    st.add(23);
    st.Print();
    
    cout << "Count:" << st.Count()<<"\n" << endl;

    int d;
    d = st.del();
    cout << "Delete item:" << d << endl;
    st.Print();
    
    return 0;

}

Зроблено майже все окрім визначення мінімального та максимального елемента. Де найдоцільніше шукати їх, в main() чи створювати функцію у класі? І як це правильно реалізувати?

2 Востаннє редагувалося ch0r_t (28.02.2021 19:53:11)

Re: Класи та об'єкти в С++

Можна створити(визначити), до прикладу, методи на кшталт int getMin(){} та int getMax(){}, де виконуватиметься пошук елемента порівнюючи кожне значення, скажімо з тимчасовою перемінною int n=stack[0], присвоюючи найменше значення їй що раз як таке зустрілось. Теж з макс., тільки відповідно перевірка має бути на те чи не є воно більшим за те що зараз. Потім, очевидно, в кінці поверніть її значення як результат пошуку.

edit

~STACK(){
     if (count > 0)
         delete[]stack;
         count = 0; // може так краще? Про всяк випадок
}
Подякували: Lena_17, leofun012

3

Re: Класи та об'єкти в С++

Створити клас – стек на основі одновимірного масиву цілих чисел. Визначити:
1. Конструктор, деструктор
2. Функції для додавання елемента до стеку та вилучення елемента зі стеку
3. Обчислення кількості елементів у стеку
5. Мінімального та максимального елемента.

Думаю краще дотримуватись умови задачі. Саме визначити у протоколі класу пункт 5. Але ніхто не заважає Вам зробити це і поза протоколом класу СТЕК. Думаю це буде не зайве і викладач оцінить Вашу роботу.

Проглянувши Ваш код є декілька зауважень, сподіваюсь вони будуть для Вас корисні і Ви прислухаєтесь...  :)
1. Відразу перше, що кидається в очі - це те, що після кожного виклику функії-члена void Stack::add(int item): Виділяється пам'ять, відбувається копіюються даних та знищується не потрібна область. На мою думку робота і з Heap пам'яттю і так сповільнює роботу програми, а тут ще і після кожного виклику функції Ви знову звертаєтесь до неї за новою областю більшою на одиницю.
Моя порада, виділяйте блоками. Ну скажімо хоч б нехай по 4 елементи (це для прикладу, можна і більше). Тоді потрібно лише слідкувати за тим, щоб не було переповнення. *WALL*

Прихований текст
class Stack {
    int *pa = nullptr, len{0};

public:
    /* ... */

    void push(const int& val)
    {
        if (!pa or !(len % 4)) {
            int* p = new (std::nothrow) int[len + 4];

            memset(p, 0, ((len + 4) * sizeof(int)));

            for (int i = 0; i < len; ++i)
                p[i] = pa[i];

            delete[] pa, pa = p;
        }

        for (int i = len; i > 0; --i)
            pa[i] = pa[i - 1];

        pa[0] = val;
        ++len;

        return;
    }

    int pop() { /* ... */  }

    void print() {  /* ... */  }
};

int main()
{
    Stack st;

    /* Додаємо елементи до стеку */
    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);

    /* Після кожного 4-го виклику функції-члена push(int ithem) буде
        виділятись нова область у купі. Копіювання до нової області
        усіх значень із переповненої області та видалення переповненої
        області пам'яті із купи... */
    st.push(5);
    st.push(6);
    st.push(7);
    st.push(8);

    /* Перевиділення пам'яті. Див коментар вище */
    st.push(9);
    st.push(0);

    st.print();

    return 0;
}

Чи як варіант зробити масив статичним та слідкувати за його переповненням.
Для наглядності розмір масиву рівний 10.

Прихований текст
class Stack {
    int arr[10]{0}, len{0};

public:
   /* ... */

    void push(const int& val)
    {
        assert((len < 10) and "Стек переповнений");

        for (int i = len; i > 0; --i)
            arr[i] = arr[i - 1];

        arr[0] = val;
        ++len;

        return;
    }

    int pop() { /*... */ }

    void print() { /* ... */ }
};

int main()
{
    Stack st;

    st.print();

    /* Додаємо елементи до стеку */
    st.push(2);
    st.push(4);
    st.push(15);
    st.push(6);
    st.push(23);

    st.print();

    return 0;
}

2. Друге зауваження стосується вивільнення пам'яті у деструкторі. Ваш приклад:

~STACK(){
     if (count > 0)
         delete[]stack;
}

А саме умова при котрій Ви збираєтесь видаляти об'єкт із пам'яті. На моє переконання краще перевіряти сам вказівник, чи вказує він на якусь ділянку пам'яті чи рівний nullptr (NULL) і звільнити його. Детально тут. Отже зауважу перевірка для вивільнення може не спрацювати :) оскільки під-час роботи програми ви змінюєте count і будь-що може статись із цією змінною, а так Ви ініціалізували вказівник nullptr в конструкторі, виділили пам'ять int* p = new (std::nothrow) int[size]; в якісь із функції. Чим менше Ви проводите ці операції над вказівником ти біль імовірно, що ця пам'ять виділена та ви можете її знищити:

Stack::Stack() { p = nullptr; }

void Stack::push(int item) { 
   p = new (std::nothrow) int[size];
}

Stack::~Stack() {
    if (pa)
       delete[] pa;
    pa = nullptr;
}

3. Ну і третє стосується того, як ви заносите дані до масиву. Сама ця структура даних Стек говорить як його потрібно ініціалізувати.

Працює за принципом «останнім прийшов — першим пішов» (LIFO, англ. last in, first out)

Подякували: ch0r_t1

4 Востаннє редагувалося koala (01.03.2021 09:03:24)

Re: Класи та об'єкти в С++

lucas-kane написав:

Моя порада, виділяйте блоками.

Звичайна практика - збільшувати розмір масиву в 2 (чи 1.5) рази. Виділення однаковими блоками не змінює складність, кількість викликів new все одно буде O(n). Так, доведеться тримати одну додаткову змінну для розміру резерву.
А от пересувати весь масив при додаванні - це точно надмірно. Особливо - пересувати його після копіювання. Останній доданий елемент цілком може мати індекс count-1.

lucas-kane написав:

вивільнення пам'яті у деструкторі

Оце правильно. До того ж в оригінальному коді присутня ця помилка: count==0 можливий не лише на початку роботи, а й після викидання елементів; тоді виділена пам'ять не буде звільнена. Загальна порада тут - дотримуватися принципу RAII, resourse aquisition is initialization: в конструкторі обов'язково виділяйте пам'ять, у деструкторі обов'язково звільняйте.

lucas-kane написав:

new (std::nothrow) int[size];

Ну це вже трохи надмірно для початківця. Тим більше, що оригінальна програма працюватиме краще: якщо new падає з виключною ситуацією, то подальші команди гарантовано не виконаються. А от

            int* p = new (std::nothrow) int[len + 4];
            memset(p, 0, ((len + 4) * sizeof(int)));

при нестачі пам'яті призведе до UB; і якщо на сучасних x86/x64 тут буде помилка доступу до пам'яті, то що на різній екзотиці - передбачити важко, можна випадково переписати якісь системні дані, що лежать за адресою 0. Аварійне завершення, в цілому, краще за UB.

lucas-kane написав:

Сама ця структура даних Стек говорить як його потрібно ініціалізувати.

Навпаки. Стек - це про принцип роботи структури, а не про її організацію. Не має значення, починається стек з індексу 0, останнього індексу буфера, всередині кільцевого буфера чи аби-де в списку. Значення має, що є лише 2 операції доступу. І з цієї точки зору завдання обчислити мінімум і максимум в стеку виглядає дещо абсурдним: формально його можна виконати, лише знищивши стек.

Подякували: wander, ch0r_t, leofun013