C++ 使用动态内存创建队列

Question

我正在尝试使用标准库为我的部分代码创建队列。对于抽象概念，我的 Queue 将具有 Front、Back 指针，它们指向 Queue 中的 Front 和 Back 元素。因此，当我推送某些内容时，Back ptr 将指向已推送的新值。当我弹出一些东西时，前面的 ptr 将指向下一个前面的值。

例如：首先我们声明它是空的，Front Back都指向nullptr，

[] - Front = nullptr, Back = nullptr

推送(5)

[5] - Front = 5, Back = 5

推送(7)

[7 , 5] - Front = 5, Back = 7

推送(4)

[4, 7, 5] - Front = 5, Back = 4

弹出（）

[4, 7] - Front = 7, Back = 4

弹出（）

[4] - Front = 4, Back = 4

弹出（）

[] - Front = nullptr, Back = nullptr

class Queue
{
private:
    struct node
    {
        int value;
        node* next;

        node(int value, node* next = nullptr)
        {
            this->value = value;
            this->next = next;
        }
    };

    node* front, * back;

public:
    //Constructor
    Queue()
    {
        front = nullptr;
        back = nullptr;
    }

    //Class methods:
    void push(int num);
    int pop();
    bool isEmpty();
};

方法定义：

void Queue::push(int num)
{
    back = new node(num, back);
}

int Queue::pop()
{
    int num = front->value;
    node * temp = front;
    front = front->next;
    delete temp;
    return num;
}

bool Queue::isEmpty()
{
    if (front == nullptr)
    {
        return true;
    }
    else
    {
        return false;
    }
}

现在我从 pop() 中收到运行时错误，并且 pop() 没有删除前面的值。

Answer 1

我重写你的代码：

#include <iostream>
using namespace std;

class Queue
{
private:
    struct node
    {
        int value;
        node* next;

        node(int value, node* next = nullptr)
        {
            this->value = value;
            this->next = next;
        }
    };

    node* front, * back;

public:
    //Constructor
    Queue()
    {
        front = nullptr;
        back = nullptr;
    }

    //Class methods:
    void push(int num);
    int pop();
    bool isEmpty() { return (front == nullptr); }

    void print();
};

void Queue::print()
{
    node* tmp = this->front;
    cout << "[ ";
    while(tmp != nullptr) {
        cout << tmp->value << " ";
        tmp = tmp->next;
    }
    cout << "]";
}

void Queue::push(int num)
{
    node* tmp = new node(num, nullptr);
    if(!isEmpty()) { // if not empty
        back->next = tmp;
        back = tmp;
        return;
    }

    // if list is empty
    front = tmp;
    back = tmp;
}

int Queue::pop()
{
    if (isEmpty()) return 0;
    int num = front->value;
    if (front->next == nullptr) { // if list have only one element
        delete front;
        front = nullptr;
        back = nullptr;
        return num;
    }
    node * temp = front;
    front = front->next;
    delete temp;
    return num;
}

int main() {

    Queue q;
    q.push(5);
    q.push(2);
    q.push(2);
    q.push(5);

    q.print();

    q.pop();
    q.print();

    q.pop();
    q.print();

    q.push(5);
    q.print();

    q.pop();
    q.print();

    q.pop();
    q.print();

    q.pop();
    q.print();

    q.pop();
    q.print();

    q.push(5);
    q.print();

    return 0;
}

为了测试，我添加了一个 print() 方法，使 isEmpty() 更清晰，并添加了一些条件来检查特殊情况。

如果列表为空并且调用了 pop()，则无需执行任何操作。

如果列表为空并且 push() 被调用 back 并且 front 需要指向同一个对象。

如果list只有一个元素，pop()调用list需要清空，front和back需要nullptr

Answer 2

我注意到新节点总是有 next == nullptr 并且它们总是附加到列表的末尾。那么为什么不在构造函数中这样做呢？使用 Node ** 是一个众所周知的技巧，可以避免空列表和 non-empty 列表具有单独的代码路径。

我将成员变量的初始化更改为使用带有花括号的现代内联初始化 Node* next{nullptr};。在 Queue 的情况下，您甚至不再需要构造函数。

随着对 Node **back 的更改，push 和 pop 方法可以稍微简化。

#include <iostream>

class Queue
{
private:
    struct Node
    {
        int value;
        Node* next{nullptr};

        // prev is the end of the list this Node should be attached to
        // specifically the address of the Node*, not the Node
        Node(Node **prev, int value_) : value(value_) {
            *prev = this;
         }
    };

    Node *front{nullptr};
    // back is the end of the list to attach new Nodes
    // specifically the address of the Node*, not the Node
    // this allows it to be eigther &front or &node.next
    Node **back{&front};

public:
    //Class methods:
    void push(int num);
    int pop();
    bool isEmpty() { return (front == nullptr); }

    void print();
};

void Queue::print()
{
    Node* tmp = this->front;
    std::cout << "[ ";
    while(tmp != nullptr) {
        std::cout << tmp->value << " ";
        tmp = tmp->next;
    }
    std::cout << "]";
}

void Queue::push(int num)
{
    // Nodes automatically attach to the back
    new Node(back, num);
    // just needs back to be advanced
    back = &((*back)->next);
}

int Queue::pop()
{
    if (isEmpty()) return 0;
    int num = front->value;
    Node * temp = front;
    // advance front
    front = front->next;
    delete temp;
    if (front == nullptr) {
        // empty list now so back has become invalid
        // reset it to point at front
        back = &front;
    }
    return num;
}

int main() {

    Queue q;
    q.push(5);
    q.push(2);
    q.push(2);
    q.push(5);

    q.print();

    q.pop();
    q.print();

    q.pop();
    q.print();

    q.push(5);
    q.print();

    q.pop();
    q.print();

    q.pop();
    q.print();

    q.pop();
    q.print();

    q.pop();
    q.print();

    q.push(5);
    q.print();

    return 0;
}

C++ 使用动态内存创建队列

C++ creating Queue using Dynamic Memory

c++

queue

inheritance

struct

dynamic-memory-allocation