弹出我用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

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

从更一般的角度来看，我通常会认为，如果我必须为一个对象获取内存，然后将该对象‘插入’到某个数据结构中，那么该结构将负责该对象的所有权。如果我弹出项，这将简单地将项从数据结构中删除，它不再是所有者，所有权返回到调用者。

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

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

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

Answer 2

我喜欢我的pop函数返回被移除的元素而不释放它，因为它让将要使用它的人有更多的自由。

但这是一个选择的问题，你可以做一个具有void原型的pop函数，你也可以释放里面的元素。