C++ class Очередь с приоритетом, реализация метода push

Question

Я реализовала class Priority_queue, реализовала методы, но возникли проблемы с методом push. Он должен добавлять элемент по приоритету, то есть отсортировано, от наибольшего к наименьшему.

void push(const T& value) {
    _size++;
    if (_top == nullptr) {
        _top = new Element<T>(value);
    }
    else {
        Element<T>* tmp = new Element<T>(value);
        if (_top->GetData() < tmp->GetData()) {
            tmp->SetData(value);
            tmp->SetNext(_top);
            _top = tmp;
        }
        else {
            Element<T>* tmp2 = _top->GetNext();
            while (tmp2 != nullptr) {
                if (tmp2->GetData() < tmp->GetData()) {
                    tmp2= new Element<T>(value,tmp2);
                }
                tmp2 = tmp2->GetNext();
            }
        }
    }
}

Он правильно добавляет элементы только если число, которое я хочу добавить больше моего _top. Как его можно реализовать более правильно?

Answer 1

void push(const T& value) {
    
    // увеличить размер очереди
    _size++;

    // создать новый элемент
    Element<T>* newElement = new Element<T>(value);

    if (_top == nullptr) {
        _top = newElement
    }
    else {
        // если последний элемент меньше нового - добавить новый кусок
        if (_top->GetData() < newElement->GetData()) {
            newElement->SetData(value);     // зачем это нужно, если в конструкторе уже задано значение
            newElement->SetNext(_top);
            _top = newElement;
        }
        else {
            // найти элемент меньше нового
            Element<T>* last = _top;
            Element<T>* prev = nullptr;

            while ((last != nullptr) && (last->GetData() >= newElement->GetData())) {
                prev = last;

                // перейти к следующему элементу
                last = last->GetNext();
            }

            if (last != nullptr) {
                newElement->SetNext(last->GetNext());
                last->SetNext(newElement);
            }
            else {
                prev->SetNext(newElement);
        }
    }
}

вот такой вариант вроде как должен сработать

в случае, когда значение нового элемента меньше топового вы зачем то в цикле начинаете создавать эти элементы, хотя элемент вроде как нужно создать только 1 раз и дальше уже решать вопрос куда вставить указатель

БЛОГ НА HUSL

C++ class Очередь с приоритетом, реализация метода push

Ответы (1 шт):