Enqueue/Dequeue 在 C++ 中使用指针？

Question

为了我的 class，我现在开始使用 C++，我们在 Scheme 中介绍了入队和出队。然而，我们现在用 C++ 来做，我们需要使用指针，我很难理解这一点。我了解指针是什么，何时使用它们等。但是，我正在努力弄清楚如何将它们实施到本实验室中。我目前有这个代码：

#include <stdlib.h>
#include <iostream>
#include <assert.h>
using namespace std;

struct node {
    int item;
    node* next;
};

typedef node* nodePtr;   

typedef nodePtr* queue;  

queue makeQueue() {
    queue q = new nodePtr[2];
    q[0] = NULL;         
    q[1] = NULL;
    return q;
}

nodePtr start(queue q) {
    return q[0];
}

nodePtr tail(queue q) {
    return q[1];
}

void setStart(queue q, nodePtr newNode) {
    q[0] = newNode;
}

void setTail(queue q, nodePtr newNode) {
    q[1] = newNode;
}

bool emptyQueue(queue q) {
    return q[0] == NULL;
}

int head(queue q) {
    if (emptyQueue(q)) {
        cout << "Attempt to take head of an empty queue.\n";
        exit(1);
    }
    return start(q)->item;
}

void enqueue(queue q, int newItem) {
    // Answer goes here.
}

void dequeue(queue q) {
    // Answer goes here.
}

对于这段代码，我明白我需要做什么：Enqueue 会将 newItem 推入队列的 cdr（或尾部），而 Dequeue 将删除队列开头的节点，并相应地更新适当的位置.但是就是指针让我很迷惑，不知如何是好。

我将如何深入研究使用指针编写入队和出队？我将茫然地假设入队和出队不应该是一行一行的代码。

非常感谢！

Answer 1

在处理基于指针的动态结构（如堆栈、链表和 queues 时），都是关于重新排列指针。正如评论中所建议的那样，将指针表示为纸上指向节点的箭头将有助于可视化在 en-/dequeuing.

时需要如何重新分配指针

我还想指出，您不应该像您那样混合使用 C 和 C++ header。 C++ 库包含与 C 语言库相同的定义，它们以相同的 header 文件结构组织。每个 header 文件的名称与 C 语言版本相同，但带有 "c" 前缀且没有扩展名。例如，C 语言 header 文件 <stdlib.h> 的 C++ 等价物是 <cstdlib>，类似地，<assert.h> 是 <cassert>。此外，在 C++ 中，NULL 指针是 nullptr；在使用 int 和指针参数重载函数时，混合使用 NULL 和 nullptr 可能会导致问题。

现在解决手头的问题。每个 node 都有一个成员 next，它是指向 queue 中下一个 node 的箭头。看起来，q[0] 和 q[1] 分别是第一个和最后一个元素的箭头。

如果您只想queue 有效负载数据中的新元素（不是完整的 node），那么您将必须动态创建 node object 第一的。然后它的 next 指针必须指向 q[0]->next 指向的内容，而 q[0]->next 必须重新分配以指向您刚刚创建的新节点：

之前：

q[0]->next ---> somenode

之后：

q[0]->next -.    -XXX->    somenode
            |                  ^
            |                  |
            '-> newnode->next -'

或者在 C++ 中（没有验证）：

void enqueue(queue q, int newItem) {
    nodePtr newnode = new node;
    newnode->item = newItem;
    newnode->next = q[0]->next;
    q[0]->next = newnode;
}

相应地出队，看看你需要如何重新排列指针。不要忘记 delete 删除节点并提供删除 makeQueue 创建的 queue 的功能。

Enqueue/Dequeue 在 C++ 中使用指针？

Enqueue/Dequeue in C++ Using Pointers?

c++

stack

pointers

enqueue