[FIXED] Why do I have to return a pointer when i'm working with dynamic data type? (i.e stack, list, queue, dynamic array)

Issue

When using pop and push function, I have to return a pointer otherwise the variable stack doesn't change. Does anyone know why?

#include <stdio.h>
#include <stdlib.h>

//Defining stack element
typedef struct element
{
    int num;              //Content of the element
    struct element *next; //Pointer to the next element
}element;

element *push(element *s, int x); //Insert x elements in the stack
void print(element *s);           //Prints the stack's elements
element *pop(element *s);         //Removes the stack's top element

int main()
{
    element *stack = NULL; //Pointer to the stack's top element
    int x;

    printf("Insert the number of elements: ");
    scanf("%d", &x);

    stack = push(stack, x);
    print(stack);

    stack = pop(stack);
    print(stack);

    return 0;
}

element *push(element *s, int x)
{
    element *newElement;

    for(; x > 0; x--)
    {
        newElement = (element*)malloc(sizeof(element));

        printf("Number: ");
        scanf("%d", &newElement->num);

        newElement->next = s;
        s = newElement;
    }

    return s;
}

void print(element *s)
{
    element *through = s;

    printf("Your stack:\n");

    while(through != NULL)
    {
        printf("%d\t", through->num);
        through = through->next;
    }
    printf("\n");
}

element *pop(element *s)
{
    element *elementDeleted = s;
    s = elementDeleted->next;

    printf("Element deleted: %d\n", elementDeleted->num);

    free(elementDeleted);
    elementDeleted = NULL;

    return s;
}

I simply expected to modify the pointer stack in the functions, so I expected the functions to be void. But actually if I don't return the pointer the stack variable keeps its starting value (in this case NULL).

Solution

You need to usse a double pointer in your function arguments:

// Add a new value to the top of the stack
void push(element **s, const int x);
// Print the stack
void print(const element *s);
// Try removing the top element of the stack and returning it
int pop(element **s);

You then call push and pop with a reference to the stack pointer:

push(&stack, x);
pop(&stack);

Then, if you want to modify the pointer to the stack, you dereference s once: *s = newElement, but if you want to get the value of the top element, you dereference it twice: const int num = (*s)->num;.

The reason for needing to do this is that when you pass a pointer to the stack to a function, that function receives a copy of the pointer. This new pointer refers to the same stack, so modifying the values in the stack will work, but modifying the pointer itself will do nothing outside the function.

If instead you use a pointer to the pointer to your stack, then you allow that second pointer to be modified, because only the top-level pointer is a copy.

Answered By - Billy Brown

Answer Checked By - Marie Seifert (PHPFixing Admin)