如何仅通过类在 C++ 中使用链表实现队列

Question

我有一个链接列表 class，像这样实现的（也经过测试）：

template <class T>
class LList {
    LNode<T>* head;
    LNode<T>* tail;
    int size; // proporciona muitas vantagens
    LNode<T>* rCopy(LNode<T>* right);
public:
    LList() : head(nullptr), tail(nullptr), size(0) {}
    LList(const LList& other) :
            head(nullptr), tail(nullptr), size(0) {
        *this = other;
    }
    ~LList() { clear(); }

...
    // O(1)
    void insertAtBack(T newvalue) {
        LNode<T>* tmp = new LNode<T>(newvalue, nullptr);
        tail->next = tmp;
        tail = tmp;
        if (head == nullptr)
            head = tmp;
        this->size++;
    }
...
};

然后，我创建了一个队列class：

template <class T>
class Queue {
private:
    LList<T> lista;
public:
//    Queue() : lista() {} ??? don't know how to do it
    void enqueue(T element);
    T peek();
    void dequeue();
    int size();
    bool isEmpty();
    void sizeLog();
};

template<class T>
void Queue<T>::enqueue(T element) {
    lista.insertAtBack(element);
}

但我不能在 main 上使用它，任何入队尝试都会导致 for 循环崩溃，即 returns 错误代码 -1073741819。函数 isEmpty() 起作用并显示 true.

Queue<int> f;
std::cout << "created" << endl;
std::cout << f.isEmpty() << endl;

for (int i=0; i<10; i++) {
    f.enqueue(i*5);
}

输出：

created
1

Process finished with exit code -1073741819 (0xC0000005)

我尝试为 Queue class 编写构造函数来初始化 LList class，但找不到正确的方法。如果我写一个主函数来只测试 LList class，我不需要初始化，因为它的构造函数已经在进行工作。

Answer 1

最初 tail, head 是 nullptr 所以当插入第一个元素时，您尝试访问 insertAtBack 中的 tail->next 其中 tail 是 nullptr 导致错误（可能是未捕获的异常），如果 tail 是 nullptr，只需为其分配 tmp 值。像这样放置一个 nullptr 检查表达式..


// O(1)
    void insertAtBack(T newvalue) {
        LNode<T>* tmp = new LNode<T>(newvalue, nullptr);

        // if it is nullptr, 
        // it is the first and only element
        // so head = tail = tmp
        if(tail != nullptr) 
            tail->next = tmp;
        tail = tmp;
        if (head == nullptr)
            head = tmp;
        this->size++;
    }

``

如何仅通过类在 C++ 中使用链表实现队列

How to implement a Queue using Linked List in C++ by classes only

c++

queue

singly-linked-list

如何仅通过 类 在 C++ 中使用链表实现队列

How to implement a Queue using Linked List in C++ by classes only

c++

queue

singly-linked-list

如何仅通过类在 C++ 中使用链表实现队列