使用C++中的链接列表实现队列实现

Question

我想基于链接列表在C++中实现队列容器。我使用相同的结构来实现堆栈，它工作正常。

但现在我havet与方法“排队”的麻烦。我不明白究竟是什么问题，但我知道指针是我的弱点。

#include <iostream> 

template <class N> 
class node { 
public: 
    N data; 
    node* next; 
}; 

template <class Q> 
class my_queue { 
protected: 
    node<Q>* m_head; 
    unsigned int m_size; 

public: 
    my_queue() { 
    m_head = NULL; 
    m_size = 0; 
    } 

    void enqueue(Q value) { 

    node<Q>* newel = new node<Q>; // creating the new element 
    node<Q>* last = m_head; // find the last element in the queue 

    while(last != NULL) { 
     last = last->next; 
    } 

    newel->data = value; 
    newel->next = last->next; 
    last->next = newel; 

    m_size++; 
    } 

    void print() { 
    node<Q>* element = m_head; // element == each element in the list 
    while(element != NULL) { 
     std::cout << element->data << std::endl; 
     element = element->next; 
    } 
    } 

}; 

如果我编译这个用：

main() { 
    my_queue<int> q; 
    q.enqueue(1); 
    q.enqueue(2); 
    q.enqueue(3); 
    q.enqueue(4); 
    q.enqueue(5); 
    q.print(); 

    return 0; 
} 

我没有错误，但是当我运行它，我得到“段错误”。

Answer 1

这个循环的功能

while(last != NULL) { 
    last = last->next; 
} 

指针last后，将永远等于NULL。所以功能未定义的行为由于这些语句

newel->next = last->next; 
last->next = newel; 

该功能可以改写如下方式

void enqueue(const Q &value) 
{ 
    node<Q> *newel = new node<Q> { value, nullptr }; 

    if (m_head == nullptr) 
    { 
     m_head = newel; 
    } 
    else 
    { 
     node<Q> *last = m_head; // find the last element in the queue 

     while (last->next != nullptr) last = last->next; 

     last->next = newel; 
    } 

    m_size++; 
} 

要让队列更有效率最好是基于双面来实现它名单。