c - 弹出我在 C 中制作的堆栈

Question

我正在用 C 语言编写堆栈结构和 push/pop 方法作为一项教育练习(不是家庭作业，我只是想做点什么，尽管我希望我的家庭作业这么好)，但我陷入了进退两难的境地。

当我从栈中弹出一个节点时，我应该返回栈上的值还是堆上的值？

如果我返回堆上的值，如果使用堆栈的程序没有释放()内存，那么就会出现内存泄漏，但如果我使用堆栈，则可能会出现范围问题和用户(可能只有我)我的堆栈实现将不得不处理额外的工作。

到目前为止，我一直在使用堆来处理与堆栈结构及其方法有关的所有事情，当我试图将弹出的数据放在堆栈上时，当我试图在测试程序中使用它时，数据已损坏.

(最好不要在这里设计堆栈实现，以便堆栈的用户可以更改元素大小，从而将许多不同类型推送到堆栈和不同大小的字符串，因为它将数据作为空指针处理).

我的堆栈实现看起来像这样(我是 C 的新手，所以这可能有点困惑):

#include "cstack.h"

struct node{
    struct node* child;
    struct node* parent;
    void* data;
    int has_child;
    unsigned long int elemsize;
};

struct cstack{
    struct node* root_node;
    struct node* last_node;
    unsigned long int elemsize;
    void (*push)(cstack*);              /*function pointers here incase it suits someones workflow, not that anyone will use my stack implementation*/
    void* (*pop)(cstack*, void* data);
};

void push(cstack* stack, void* data){
    struct node* currnode;
    int isroot = 0;

    if(stack->root_node == NULL){
        stack->last_node = (struct node*)malloc(sizeof(struct node));
        stack->root_node = stack->last_node;
        stack->root_node->has_child = 0;
        stack->root_node->parent = NULL;
        stack->root_node->elemsize = stack->elemsize;
        isroot = 1;
    }

    currnode = stack->last_node;

     /*If they have added a node themselves, which is fine, it will cause undefined behaviour so let's make sure
       the node has no children, but if they have hacked it let's hope they set the correct flags >->*/

    while(currnode->has_child){
        currnode = currnode->child;
    }

    if(!isroot){
        currnode->has_child = 1;
        currnode->child = (struct node*)malloc(sizeof(struct node));

        currnode->child->data = malloc(stack->elemsize);
        currnode->child->parent = currnode;
        currnode->child->elemsize = stack->elemsize;

        memcpy(currnode->child->data, data, stack->elemsize);

        stack->last_node = currnode->child;                            /*update the last node position of the stack*/
    }else{
        currnode->data = malloc(stack->elemsize);
        memcpy(currnode->data, data, stack->elemsize);
    }
}

void* pop(cstack* stack){
    void* rtrn;
    if(stack->root_node != NULL){
        struct node* currnode = stack->last_node;

        while(currnode->has_child){
            currnode = currnode->child;
        }

        /*This is where the variable to return get's set
          when I was using the stack my code was
          rtrn = &(*currnode->data)*/

        rtrn = malloc(currnode->elemsize);
        memcpy(rtrn, currnode->data, currnode->elemsize);

        if(currnode->parent != NULL){
            stack->last_node = currnode->parent;/*we're popping the top node so the last node in the stack should be the parent node of the current last node*/
            currnode = currnode->parent;        /*elevate to parent node*/
            currnode->has_child = 0;
            free(currnode->child->data);
            currnode->child->data = NULL;
            free(currnode->child);
            currnode->child = NULL;
        }else{                                  /*it's the root node*/
            free(currnode->data);
            currnode->data = NULL;
            free(currnode);
            stack->root_node = NULL;
            stack->last_node = NULL;
        }
    }else{
        rtrn = (void*)NULL;                    /*this cast is redundant because NULL should be a void pointer anyway, but if it isn't then we need to make sure it is*/
    }
    return rtrn;
}

void change_elem_size(cstack* stack, unsigned long int elemsize){
    stack->elemsize = elemsize;
}

cstack* new_stack(unsigned long int elemsize){
    cstack* rstack;
    rstack = (cstack*)malloc(sizeof(cstack));
    rstack->root_node = (struct node*)malloc(sizeof(struct node));

    rstack->elemsize = elemsize;
    rstack->pop = pop;
    rstack->push = push;
    rstack->last_node = rstack->root_node;

    rstack->root_node->parent = NULL;
    rstack->root_node->has_child = 0;
    rstack->root_node->child = NULL;

    return rstack;
}

我的另一个想法是让他们传递一个指向预分配变量的指针，这样他们就会知道它在堆栈上，并在必要时增加它的大小。

我希望你能帮助我，我不确定我是否应该直接使用堆，希望我/人们有足够的常识来释放()数据。

Answer 1

我强烈建议遵循 Least Surprise 原则。在这种情况下，它应该与对象及其内存进入堆栈的方式对称。重要的问题是:谁在什么时候拥有该对象？谁首先创建了对象的内存？我还会考虑堆栈的预期性能方面。通常，从堆栈顶部插入(推送)和移除(弹出)对象的时间预计为 O(1)。您的潜在选择如何与此相符？

更一般地思考，如果我必须为一个对象获取内存，然后将该对象“插入”到某个数据结构中，那么该结构将负责该对象的所有权。如果我要弹出该项目，那只是从数据结构中删除该项目，它不再是所有者，所有权返回给调用者。

相反，如果我一开始没有参与对象的内存分配，而 DST 为我做了这件事，我希望我以后不必参与销毁/取消分配.

您显然可以偏离这一点，但对于每一个偏离，您都需要/想要提供文档，以便您的结构的用户知道会发生什么，特别是因为这些偏离可能会偏离他们遇到的大多数其他情况。

另一个考虑因素是，如果您想返回除指向原始对象的指针之外的任何其他内容，您还需要花费时间复制/重建该对象。这当然在复制过程和性能影响方面提出了自己的问题。当真正复杂的对象开始进出您的数据结构时会发生什么。