реализация очереди с вектором c ++

Question

Нам было поручено реализовать класс, который использует вектор для хранения очереди.Я придумал следующее, но на самом деле это не работает.Может кто-нибудь сказать мне, что пошло не так?

Значения чисел правильно вставлены в vec, и первый pop () работает.Но если я проверю head-> getElement (), он выдаст странное число.Последующие вызовы pop () также не выполняются.

#include <iostream>
#include <vector>
using namespace std;

template<class T>
class node{
    T element;
    node* next;
public:
    node(): next(nullptr){};
    T getElement() {return element;}
    void setElement(T newElement) {element=newElement;}
    node* getNext() {return next;}
    void setNext(node* newNext) {next = newNext;}
};

template<class T>
class queue{
    vector<node<T>> vec;
    node<T>* head;
    int size;
public:
    queue(): head(nullptr){}
    void push(node<T> newNode);
    node<T> pop();
    int getSize() {return unsigned(vec.size());}
    vector<T> getVec()const {return vec;}
    node<T>* getHead() {return head;}
    void setHead(node<T>* newHead) {head = newHead;}
    vector<node<T>> getVec() {return vec;}
};

int main() {
    queue<int> v;

    for (int i=0;i<5;i++){
        node<int>* newNode = new node<int>;
        newNode->setElement(i);
        v.push(*newNode);
    }
    cout<<"The elements in the vector are initially:\n";
    for (int i=0; i<v.getSize();i++)
        cout<<v.getVec()[i].getElement()<<" ";
    cout<<"\nAfter popping, the popped element is "<<v.pop().getElement()<<endl;
}

template<class T>
node<T> queue<T>:: pop(){
    node<T>* tmp = new node<T>;
    tmp->setNext(head->getNext());
    head=head->getNext();
    return *tmp;
}

template<class T>
void queue<T>:: push(node<T> newNode){
    if (head==nullptr){
        node<T>* newPtr = new node<T>;
        newPtr = &newNode;
        newPtr->setNext(head);
        head=newPtr;
    }
    else{
        node<T>* newPtr = new node<T>;
        newPtr->setElement(newNode.getElement());
        node<T>* end = head;
        while (end->getNext() != nullptr)
            end->setNext(end->getNext());
        end->setNext(newPtr);
    }
    vec.push_back(newNode);
}

Answer 1

Есть много проблем с вашим кодом. Во-первых, давайте исправим поп. Вы создаете новый узел tmp, устанавливаете следующий и возвращаете то же самое без установки элемента. Чтобы это исправить, вам просто нужно установить его на голову и переместить голову на следующую.

template<class T>
node<T> queue<T>:: pop(){
node<T>* tmp = head;// = new node<T>;
//tmp->setNext(head->getNext());
head=head->getNext();
return *tmp;
}

После этого вы получите свой элемент с поп. Но вы получите неправильный элемент. Поскольку очередь основана на FIFO, вы должны получить «0» при первом появлении, но в вашем случае вы не получите 0. Потому что ваша функция push также неверна. В push, когда вы нажимаете первый элемент, вы берете адрес переданного объекта узла, который передается по значению, это приводит к неопределенному поведению, поскольку переданный объект узла будет уничтожен после завершения функции. Кроме того, в остальной части вашего толчка вы устанавливаете следующий конец на свой собственный следующий и, следовательно, он будет идти в бесконечном цикле. Ниже исправлена ​​реализация.

template<class T>
void queue<T>:: push(node<T> newNode){
if (head==nullptr){
    node<T>* newPtr = new node<T>;
    newPtr->setElement(newNode.getElement());
    //newPtr = &newNode;
    //newPtr->setNext(head);
    head=newPtr;
}
else{
    node<T>* newPtr = new node<T>;
    newPtr->setElement(newNode.getElement());
    node<T>* end = head;
    while (end->getNext() != nullptr)
        end = end->getNext();
    end->setNext(newPtr);
}
vec.push_back(newNode);
}

Наконец, в вашем коде много утечек памяти. Вы создаете новый узел гораздо большее количество раз, чем необходимо, а также не удаляете их. Теперь вы можете видеть, что в случае push вам нужно просто пропустить элемент T, и этого будет достаточно. Вам не нужно пропускать новый узел каждый раз. Кроме того, попробуйте использовать умные указатели, поскольку многие вещи будут управляться самостоятельно.