C++队列程序未按预期运行求助（用于二叉树构建）

核心问题排查 #

1. 类型转换错误导致编译失败 #

在enqueue函数的else分支里，malloc返回值被错误转换为struct QNode（结构体类型），正确应该是struct QNode*（指针类型）。同时变量名和结构体名同名（QNode）极易混淆，建议重命名变量：

// 错误写法
struct QNode* QNode = (struct QNode)malloc(sizeof(struct QNode));
// 正确写法
struct QNode* newQNode = (struct QNode*)malloc(sizeof(struct QNode));

2. 双向链表链接断裂 #

队列基于双向链表实现，但enqueue时只维护了新节点的pre指针，未更新原队尾节点的post指针，导致链表正向链接完全断裂，所有节点的post始终为NULL：

// 必须添加这行，把原队尾的post指向新节点
Queue->last->post = newQNode;

3. 遍历逻辑遗漏最后一个节点 #

遍历循环条件while (nodepointer->post != NULL)会跳过最后一个节点（它的post是NULL），应改为遍历到节点本身不为NULL：

// 错误写法
while (nodepointer->post != NULL) { ... }
// 正确写法
while (nodepointer != NULL) { ... }

4. Dequeue后的遍历逻辑错误 #

第一次遍历后nodepointer指向队列最后一个节点，执行dequeue删除队首后，直接用原指针遍历会和新队首失去关联，必须重新从新的队首开始遍历。

5. 队列size成员未正确维护 #

enqueue的else分支未更新size，dequeue也未减少size，且初始化时直接赋值参数size逻辑错误——应每次入队size++，出队size--。

6. 边界处理缺失 #

当队列只剩最后一个节点时，dequeue后未把Queue->last设为NULL，导致isEmpty判断错误（此时first为NULL但last仍指向已释放的节点）。

7. 节点数据未初始化 #

main中定义的root、root1、root2未初始化data成员，输出地址无意义，应设置具体测试值。

修复后的完整代码 #

#include <iostream>
#include <cstdlib> // 包含malloc/free的头文件

struct Node {
    int data;
    struct Node* lchild;
    struct Node* rchild;
};

struct QNode {
    struct Node* node; // 变量名改为node，避免与结构体名冲突
    struct QNode* pre;
    struct QNode* post;
};

struct Queue {
    struct QNode* first = NULL;
    struct QNode* last = NULL;
    int size = 0; // 初始化size为0
};

void enqueue(struct Queue* queue, struct Node* node) {
    struct QNode* newQNode = (struct QNode*)malloc(sizeof(struct QNode));
    newQNode->node = node;
    newQNode->post = NULL;

    if (queue->first == NULL && queue->last == NULL) {
        std::cout << "Created the first node\n";
        newQNode->pre = NULL;
        queue->first = newQNode;
        queue->last = newQNode;
    } else {
        newQNode->pre = queue->last;
        queue->last->post = newQNode; // 维护原队尾的post指针
        queue->last = newQNode;
    }
    queue->size++; // 入队后size加1
}

void dequeue(struct Queue* queue) {
    if (queue->first == NULL && queue->last == NULL) {
        std::cout << "Cannot dequeue: Queue is empty\n";
        return;
    }

    struct QNode* temp = queue->first;
    queue->first = queue->first->post;

    // 删除最后一个节点时，更新last为NULL
    if (queue->first == NULL) {
        queue->last = NULL;
    } else {
        queue->first->pre = NULL; // 新队首的pre设为NULL
    }

    free(temp);
    queue->size--; // 出队后size减1
}

int isEmpty(struct Queue* queue) {
    return (queue->first == NULL && queue->last == NULL) ? 1 : 0;
}

int main(void) {
    // 初始化Node节点，设置测试数据
    struct Node root = {10, NULL, NULL};
    struct Node root1 = {20, NULL, NULL};
    struct Node root2 = {30, NULL, NULL};

    struct Queue Q;
    enqueue(&Q, &root);
    enqueue(&Q, &root1);
    enqueue(&Q, &root2);

    std::cout << "Initial queue elements (data): ";
    struct QNode* nodepointer = Q.first;
    while (nodepointer != NULL) {
        std::cout << nodepointer->node->data << " "; // 输出节点数据而非地址
        nodepointer = nodepointer->post;
    }
    std::cout << "\n";

    dequeue(&Q);
    std::cout << "After dequeue, queue elements (data): ";
    nodepointer = Q.first; // 重新从队首开始遍历
    while (nodepointer != NULL) {
        std::cout << nodepointer->node->data << " ";
        nodepointer = nodepointer->post;
    }
    std::cout << "\n";

    return 0;
}

额外优化建议 #

• 尽量在C中使用new/delete替代malloc/free，更符合C语法规范，也能自动调用构造函数。
• 将队列封装为类，用成员函数代替全局函数，提升代码封装性和可维护性。
• 增加malloc失败的错误检查，避免空指针访问。

内容的提问来源于stack exchange，提问作者Richard AR