使用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++; 
} 

要讓隊列更有效率最好是基於雙面來實現它名單。