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

Question

Confused as to how to implement a single function that would at the same time pop the element and return it as return value.

So far all I've seen are pop functions that return a pointer to the new head of the stack.

---

Here's a start, but...

#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;

Doesn't actually change the address that the pointer stack_head (i.e the head of the stack) points to... and so the value is indeed returned for the first pop but subsequent pops return errors.

Yes because it is a local variable but then how would you change the actual pointer (the one that points to the head of the stack) to point to the new head of the stack?

Answer 1

The parameter stack_head is local to the function pop, so when you modify it the result is not visible outside of the function.

You need to pass the address of the variable you want to modify, then in the function you dereference the pointer parameter to change what it points to.

So change your function to this:

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;
}

And call it like this:

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

Answer 2

Okay, this will be a pretty long digest, but hopefully worth it. You can see a testcase of the code I've presented as my conclusion here and obtain a modular version of the code here. My suggestion would be that you use a structure like this:

struct {
    size_t top;
    T value[];
}

The reason you probably shouldn't use classical linked lists for this (or anything, really) is covered by this video courtesy of Bjarne Stroustrup. The basis of the problem is that the majority of your overhead is in allocation and cache misses which don't occur so much when you keep everything in one allocation.

If I were to write this for convenient use, perhaps:

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

This should allow you to declare empty stacks fairly sensibly, like:

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

This is familiar enough to templates in other languages to work fairly well, and also not a hideous abuse of the preprocessor. I'm sure I've written a push_back function somewhere which we can adapt to this version of push which I've linked to externally as it's not important for the conclusion of this answer (bear with me here; we'll come back to that momentarily)...

So now we have stack_of(T) and push(list, value) which we can use like:

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

---

The simplest solution for pop might be something like:

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

... but this does suffer a drawback we'll discuss later. For now we have as a testcase:

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);
}

... and as you'll see during debug the assert fails during execution telling us we've popped more than we've pushed... probably a good thing to have. Still, this doesn't actually reduce the size of the stack. To do that we actually need something more like push again, except we get rid of these lines:

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

So there's an opportunity for refactoring. Thus I bring you 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__;                                                     \
}

Now we can redefine push in terms of operate:

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

... and pop looks kind of like it did before, but with an invocation of operate on the end to cause list to shrink (from quadruple its size, for example when you've popped 3 elements off of a list of 4) to no larger than double its size.

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

---

Summing it all up, you can see a testcase of the code I've presented here and obtain a modular version of the code here...