Реализация своего pop() для стека C++

Question

Реализация своего pop() для стека C++

Рейтинг: 0Ответов: 1Опубликовано: 10.03.2023

// Online C++ Compiler - Build, Compile and Run your C++ programs online in your favorite browser


#include <iostream>
#include <cstdlib>

namespace s21 {
    template <class T>
    class stack {
        public:
            using value_type = T;
            using reference = T&;
            using const_reference = const T&;
            using size_type = std::size_t;
        
        public:
            stack();
            ~stack();
            void push(const_reference value);
            const_reference top();
            void pop();

        private:
            T *array_;
            size_t size_;
            size_t capacity_;
    };
}



namespace s21 {
    template <class T> 
    stack<T>::stack() : array_(nullptr), size_(0), capacity_(0) {}

    template <class T> 
    stack<T>::~stack() {
        if (size_ != 1) {
            array_ -= size_ - 1;
           // delete [] array_;
        }
    }

    template <class T>
    void stack<T>::push(const_reference value) {
        if (size_ == 0) {
            capacity_ = 10;
            array_ = new T[capacity_];
        } else {
            array_++;
        }
        if (size_ == capacity_) {
            capacity_ += 10;
            T *tmp = new T[capacity_];
            std::copy(array_, array_ + 10, tmp);
            delete [] array_;
            array_ = tmp;
        } 
        size_++;
        *array_ = value;
    }

    template <class T>
    typename stack<T>::const_reference stack<T>::top() {
        if (size_ == 0) {
            throw(std::out_of_range("Stack is empty"));
        }
        return *array_;
    }

    template <class T>
    void stack<T>::pop() {
        T *temp = array_;
        array_--;
        delete temp;
        size_--;
    }
}

int main() {
    s21::stack <int> steck_;
    steck_.push(1);
    steck_.push(2);
    steck_.push(3);
    steck_.push(4);
    steck_.pop();
    std::cout << steck_.top();
    return 0;
}

Не могу нормально удалить элемент с вершины стека. Получаю, что освобождаю память, которая не была выделена. Хотя делаю все 1 в 1 (вроде) по таким же вопросам из интернета.

c# стек

Источник: Stack Overflow на русском

Answer 1

▲ 0

У вас ошибка в логике, приводящая к утечкам памяти. В push() вы проверяете size, хотя надо проверять только capacity_.

template <class T>
void stack<T>::push(const_reference value) 
{
    if (size_ == 0) 
    {
       capacity_ = 10;
       array_ = new T[capacity_];
    }

Смотрите, вначале у вас 0 элементов, при первом push() выделили память и у вас стало capacity_ == 10; size_ == 1;. Потом сделали pop() и стало capacity_ == 10; size_ == 0;. И при следующем push() вы перевыделяете память, не удалив старую.
Здесь нет ни одной функции без ошибок.
Выделение памяти под массив и удаление/добавление элементов - это два разных процесса. T *array_; - нужно изменять либо при первоначальном выделении памяти, либо когда памяти для хранения элементов уже не хватает. Во всех остальных случаях при добавлении элемента вы делаете ++size_;, при удалении элемента - --size_; (не забывая проверить границы).

template <class T>
void stack<T>::push(const_reference value) 
{
    if (size_ == capacity_) 
    {
        capacity_ += 10;
        T *tmp = new T[capacity_];
        std::copy(array_, array_ + 10, tmp);
        delete[] array_;
        array_ = tmp;
    } 
    array_[size_] = value;
    ++size_;
}

template <class T>
typename stack<T>::const_reference stack<T>::top() 
{
   if (size_ == 0) 
       throw(std::out_of_range("Stack is empty"));
   return array_[size_ - 1];
}

template <class T>
void stack<T>::pop() 
{
   if (size_ == 0) 
       throw(std::out_of_range("Stack is empty"));
   --size_;
}

Реализация своего pop() для стека C++

Ответы