C - Linked list implementation of Stack, having trouble with pop() function?

Question

My push function works fine, but when I pop the last integer entered into my stack, first the last integer changes to zero then if I pop it again it changes to some garbage integer (this is what is showing when running it in the console). I'm guessing it has to do something in pop() where I am not freeing the node correctly..

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

typedef struct node{
    int data;
    struct node* next;
}Node;


Node* push(Node* root, int value){

    Node* temp = malloc(sizeof(Node));
    temp->data = value;
    temp->next = NULL;

    if(root == NULL){
        root = temp;
    }
    else{
        temp->next = root;
        root = temp;
    }
    return root;
}


int pop(Node* root){

    if(root == NULL){
        printf("nothing to pop, stack is already empty.\n");
        return -1;
    }

    Node* temp = root;
    root = root->next;
    int returnValue = temp->data;
    free(temp);

    return returnValue;
}

int peek(Node* root){

    if(root == NULL){
        printf("Stack is currently empty.\n");
        return -1;
    }
    return root->data;
}

int isEmpty(Node* root){

    if(root == NULL){
        return 1;
    }
    return 0;
}

void display(Node* root){
    printf("\n");
    printf("List: ");
    while(root != NULL){
        printf("%d ", root->data);
        root = root->next;
    }
    printf("\n\n");
}


int main(){

    Node* root = NULL;

    int data, choice;
    printf("\n\nMenu: (1)Push   (2)Pop   (3)Exit\n\n");

    while(1){
        printf("Enter choice: ");
        scanf("%d", &choice);
        printf("\n");

        if(choice == 1){
            printf("Enter data to push: ");
            scanf("%d", &data);
            root = push(root, data);
            display(root);
        }

        if(choice == 2){
            pop(root);
            display(root);
        }

        if(choice == 3){
            break;
        }
    }

    return 0;
}

Don't know where I'm going wrong!

ARAB KUMAR · Accepted Answer · 2020-06-22 00:14:53Z

1

Your code is totally correct, only problem is that whenever you are making a pop() request ,the values are getting changed only for the local root variable of pop() function. this won't change your actual root Node and that's why it is showing undesirable output No big deal, it can be resolved in two ways:

You make your root variable/structure global so that every function can access it directly. also you don't need to pass your it in every function
fetch the updated value of the local root of the pop() function and assign it to your actual root variable. just like you did in your push operation.

I hope this was helpful.

answered Jun 22, 2020 at 0:14

ARAB KUMAR

961 silver badge8 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

cantcode4mylife Over a year ago

So if I decide to go with the latter solution, I cannot return the data I just popped because my function would have to have return type Node* , and return the root at the functions conclusion right?

ARAB KUMAR Over a year ago

yup, but if the returnvalue is necessary then you can go with other approaches also. It totally depends on what is the requirement.

mlibby · Accepted Answer · 2020-06-22 00:21:56Z

1

Just to review. A pointer like Node* root in main contains the address of the actual data.

The problem here is that you are passing a pointer to pop the address of the root node. Then in pop you try to assign to root, but inside the pop function, root is just a copy of the address of the actual data. When the function is done this copy of the address of the data is tossed away (not getting back to your root in main). And you have freed the structure that root in main is pointing to.

What you actually need to do here is pass in a pointer to a pointer to pop so that you can modify the original pointer in the scope of main.

It looks like this in main:

if(choice == 2)
    pop(&root); //& calls the function with the address of the root pointer
    display(root);
}

Then modify your pop function like this:

int pop(Node** root){ //function expects a pointer to a pointer
    if((Node*)*root == NULL){
        printf("nothing to pop, stack is already empty.\n");
        return -1;
    }

    Node* temp = *root;
    *root = temp->next;
    int returnValue = temp->data;
    free(temp);

    return returnValue;
}

edited Jun 22, 2020 at 0:21

answered Jun 22, 2020 at 0:15

mlibby

6,7941 gold badge35 silver badges42 bronze badges

1 Comment

cantcode4mylife Over a year ago

This was very helpful, I definitely see where I went wrong now, appreciate your help!

Collectives™ on Stack Overflow

C - Linked list implementation of Stack, having trouble with pop() function?

2 Answers 2

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related