c++ - 出队不适用于从双链表继承的队列类

Question

我写了一个双链表类，它有 insertAtStart、insertAtEnd、removeFromStart、removeFromEnd 成员函数。检查下面的代码

class Node {
    public:
        int val;
        Node *next;
        Node *prev;

        Node(int v)
            : val(v),
              next(nullptr),
              prev(nullptr) {}
};

#include<iostream>
using namespace std;

#include "../node.h"

class LinkedList {
    private:
        Node* start;
        Node* end;

    public:
        LinkedList(): start(nullptr), end(nullptr) { }

        void insertAtStart(int val) {
            Node* n = new Node(val);
            if(start == nullptr) {
                start = n;
                end = n;
            } else {
                n->next = start;
                start = n;
            }
        }

        void insertAtEnd(int val) {
            Node* n = new Node(val);
            if(end == nullptr) {
                end = n;
                start = n;
            } else {
                end->next = n;
                n->prev = end;
                end = n;
            }
        }

        void removeFromStart() {
            if(start == nullptr) return;
            if(start == end) {
                start = end = nullptr;
                return;
            }
            start = start->next;
            start->prev = nullptr;
        }

        void removeFromEnd() {
            if(end == nullptr) return;
            if(start == end) {
                start = end = nullptr;
                return;
            }
            end = end->prev;
            end->next = nullptr;
        }

        void printList() {
            Node *ptr = start;
            while(ptr != nullptr) {
                cout << ptr->val << " ";
                ptr = ptr->next;
            }
            cout << endl;
        }
};

我使用下面的主函数测试了上面的代码，它运行良好

#include "double-linked-list.h"

int main() {
    LinkedList l = LinkedList();
    l.insertAtStart(1);
    l.insertAtStart(2);
    l.insertAtStart(3);
    l.insertAtStart(4);
    l.insertAtStart(5);
    l.insertAtEnd(6);
    l.insertAtEnd(7);
    l.insertAtEnd(8);
    l.insertAtEnd(9);
    l.insertAtEnd(10);
    l.printList();
    l.removeFromStart();
    l.printList();
    l.removeFromStart();
    l.printList();
    l.removeFromEnd();
    l.printList();
    l.removeFromEnd();
    l.printList();
    return 0;
}

输出:

Inserting 1 at start
Linked list: 1
Inserting 2 at start
Linked list: 2 1
Inserting 3 at start
Linked list: 3 2 1
Inserting 4 at start
Linked list: 4 3 2 1
Inserting 5 at start
Linked list: 5 4 3 2 1
Inserting 6 at end
Linked list: 5 4 3 2 1 6
Inserting 7 at end
Linked list: 5 4 3 2 1 6 7
Inserting 8 at end
Linked list: 5 4 3 2 1 6 7 8
Inserting 9 at end
Linked list: 5 4 3 2 1 6 7 8 9
Inserting 10 at end
Linked list: 5 4 3 2 1 6 7 8 9 10
Removing from start
Linked list: 4 3 2 1 6 7 8 9 10
Removing from start
Linked list: 3 2 1 6 7 8 9 10
Removing from end
Linked list: 3 2 1 6 7 8 9
Removing from end
Linked list: 3 2 1 6 7 8

我现在，写了一个从上面的链表类派生的队列类

#include "../double-linked-list/double-linked-list.h"

class Queue {
    private:
        LinkedList q;
    public:
        Queue() {}

        void enqueue(int val) {
            q.insertAtStart(val);
        }

        void dequeue() {
            q.removeFromEnd();
        }

        void printQueue() {
            q.printList();
        }
};

和下面的主要功能来测试它

#include "queue.h"

int main() {
    Queue q = Queue();
    q.enqueue(1);
    q.printQueue();
    q.enqueue(2);
    q.printQueue();
    q.enqueue(3);
    q.printQueue();
    q.enqueue(4);
    q.printQueue();
    q.enqueue(5);
    q.printQueue();
    q.dequeue();
    q.printQueue();
    q.dequeue();
    q.printQueue();
}

入队似乎工作得很好，但出队却不行。出队后甚至不打印任何内容。

输出:

Enqueuing 1
1
Enqueuing 2
2 1
Enqueuing 3
3 2 1
Enqueuing 4
4 3 2 1
Enqueuing 5
5 4 3 2 1
Denqueuing

为了调试，我在 LinkedList 的 removeFromEnd 函数中放置了一个 cout 语句。

void LinkedList::removeFromEnd(){
    if(end == nullptr) return;
    if(start == end) {
        start = end = nullptr;
        return;
    }
    end = end->prev;
    cout << "print statement 1";
    end->next = nullptr;
    cout << "print statement 2";
}

现在，当我再次运行队列的主要功能时，打印语句 1 正在控制台中打印，但第二条不是。我不明白为什么。有人可以帮我弄清楚我做错了什么吗？

编辑:

阅读评论后我对以下功能进行了更改

void insertAtStart(int val) {
    Node* n = new Node(val);

    // If start and end are null
    if(start == nullptr && end == nullptr) {
        start = end = n;
    }
    // There is at least 1 node in the list
    else {
        n->next = start;
        start->prev = n;
        // There is only one node in the list
        if(start->next == nullptr) {
            end->prev = n;
        }
        start = n;
    }
}

void insertAtEnd(int val) {
    Node* n = new Node(val);

    // If start and end are null
    if(start == nullptr && end == nullptr) {
        start = end = n;
    }
    // There is at least 1 node in the list
    else {
        n->prev = end;
        end->next = n;
        // There is only one node in the list
        if(end->prev == nullptr) {
            start->next = n;
        }
        end = n;
    }
}

这成功了。如果有兴趣，我将整个链接列表类作为答案发布。

Answer 1

对于初学者来说，程序存在内存泄漏，因为您没有删除分配的节点。

至于你的问题那就是这个函数

    void insertAtStart(int val) {
        Node* n = new Node(val);
        if(start == nullptr) {
            start = n;
            end = n;
        } else {
            n->next = start;
            start = n;
        }
    }

无效。当新节点添加到列表的开头时，它不会刷新数据成员 end->prev(更准确地说是 start->prev)。即 end->prev 总是等于 nullptr。

至少像这样重写函数

    void insertAtStart(int val) {
        Node* n = new Node(val);
        if(start == nullptr) {
            start = n;
            end = n;
        } else {
            n->next = start;
            start->prev = n; // <===
            start = n;
        }
    }