如何实现 returns "popped" 元素（即 data/value）的 'Pop' 函数？（链表栈）

Question

对于如何实现同时弹出元素和 return 将其作为 return 值的单个函数感到困惑。

到目前为止，我所看到的都是 return 指向新栈头的指针的弹出函数。

这是一个开始，但是...

#define VALUE int

typedef struct node_t {
    VALUE item;
    struct node_t *next;
} node;

.
.
.

// Function
VALUE pop(node *stack_head) {

    // Used to store the node we will delete
    node *deleteNode = stack_head;

    // Error Checking        //  <<====== (btw, is this actually necessary ?)
    if (!deleteNode || !stack_head) {

        if (!stack_head) fprintf(stderr, "\nPop failed. --> ...\n");
        if (!deleteNode) fprintf(stderr, "\nPop Failed. --> ...\n");
        return 0;
    }

    // Storing the value in a variable
    VALUE popped_item = stack_head->item;

    // Updating the head
    stack_head = stack_head->next;    <<====== THERE'S A PROBLEM HERE ! (i think)

    // Freeing/Deleting the 'popped' node
    free(deleteNode);

    // Return 'popped' value
    return popped_item;
}

。 . .

stack_head = stack_head->next;

实际上并没有改变指针stack_head（即堆栈的头部）指向的地址......所以这个值确实是 returned 对于第一个弹出但是随后弹出 return 个错误。

是的，因为它是一个局部变量，但是您如何更改实际指针（指向堆栈头部的指针）以指向新的堆栈头部？

Answer 1

参数 stack_head 是函数 pop 的局部参数，因此当您修改它时，结果在函数外部不可见。

您需要传递要修改的变量的地址，然后在函数中取消引用指针参数以更改它指向的内容。

所以把你的函数改成这样：

VALUE pop(node **stack_head) {

    node *deleteNode = *stack_head;

    if (!*stack_head) {
        fprintf(stderr, "\nPop failed. --> ...\n");
        return 0;
    }

    VALUE popped_item = (*stack_head)->item;

    *stack_head = (*stack_head)->next;

    free(deleteNode);
    return popped_item;
}

并这样称呼它：

node *stack_head = NULL;
// do something to push onto the stack
VALUE v = pop(&stack_head);

Answer 2

好的，这将是一个相当长的摘要，但希望值得。您可以看到我作为结论 here and obtain a modular version of the code here 提供的代码的测试用例。我的建议是您使用这样的结构：

struct {
    size_t top;
    T value[];
}

你可能不应该使用 经典链表 的原因（或者 任何东西 ，真的）在 this video courtesy of Bjarne Stroustrup.问题的基础是你的大部分开销都在 allocation 和 cache misses 中，当你保持 一次分配中的所有内容。

如果我为了方便使用而写这个，也许：

#define stack_of(T) struct { size_t top; T value[]; }

这应该允许您相当明智地声明空堆栈，例如：

int main(void) {
    stack_of(int) *fubar = NULL;
}

这对于其他语言中的模板来说足够熟悉，可以很好地工作，而且也不是对预处理器的可怕滥用。我确定我已经写了一个 push_back 函数 somewhere which we can adapt to this version of push 我已经链接到外部，因为它对于这个答案的结论并不重要（在这里耐心等待；我们会回到那个暂时)...

所以现在我们有 stack_of(T) 和 push(list, value)，我们可以像这样使用它们：

int main(void) {
    stack_of(int) *fubar = NULL;
    push(fubar, 42);
    push(fubar, -1);
}

pop 的最简单解决方案可能类似于：

#define pop(list) (assert(list && list->top), list->value[--list->top]))

...但这确实有一个缺点，我们稍后会讨论。现在我们有一个测试用例：

int main(void) {
    stack_of(int) *fubar = NULL;
    int x;
    push(fubar, 42);
    push(fubar, -1);
    x = pop(fubar); printf("popped: %d\n", x);
    x = pop(fubar); printf("popped: %d\n", x);
    x = pop(fubar); printf("popped: %d\n", x);
}

...正如您将在调试期间看到的那样，assert 在执行期间失败，告诉我们弹出的数量多于推送的数量...可能是一件好事。尽管如此，这实际上并没有减少堆栈的大小。为此，我们实际上还需要更像 push 的东西，只是我们要去掉这些行：

    list->top = y;                  \
    list->value[x] = v;             \

所以有重构的机会。因此我给你带来 operate():

#define operate(list, ...) {                                         \
    size_t x = list ? list->top : 0                                  \
         , y = x + 1;                                                \
    if ((x & y) == 0) {                                              \
        void *temp = realloc(list, sizeof *list                      \
                                 + (x + y) * sizeof list->value[0]); \
        if (!temp)                                                   \
            return EXIT_FAILURE;                                     \
        list = temp;                                                 \
    }                                                                \
    __VA_ARGS__;                                                     \
}

现在我们可以根据 operate 重新定义 push:

#define push(list, v) operate(list, list->value[x] = v; list->top = y)

... 和 pop 看起来有点像以前那样，但是最后调用 operate 导致 list 缩小（从原来的四倍大小，例如，当您从 4) 的列表中弹出 3 个元素时，使其大小不超过其大小的两倍。

#define pop(list) (assert(list && list->top), list->value[--list->top]); \
                  operate(list, )

总而言之，您可以看到我提供的代码的测试用例 here and obtain a modular version of the code here...

如何实现 returns "popped" 元素（即 data/value）的 'Pop' 函数？（链表栈）

How to implement a 'Pop' function that returns the "popped" element (i.e the data/value) ? (linked list stacks)

c

stack

element

function

如何实现 returns "popped" 元素（即 data/value）的 'Pop' 函数？ （链表栈）

How to implement a 'Pop' function that returns the "popped" element (i.e the data/value) ? (linked list stacks)

c

stack

element

function

如何实现 returns "popped" 元素（即 data/value）的 'Pop' 函数？（链表栈）