Trouble with pointers and stack implementation

Question

I am trying to create a program that implements a stack in C.

Currently, my stack is showing up empty.

I think this is because I pass the stack but not a pointer to the stack.

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

typedef struct node
{
    int info;
    struct node * ptr;
}node;

//create
//push
//pop
//destroy
//display
void push(int, node * top_node);
void pop(node * top_node);
void destroy(node * top_node);
void display(node * top_node);
int main(int argc, char** argv) 
{
    node * top_node = NULL;

    push(1, top_node);
    push(5, top_node);
    push(55, top_node);
    display(top_node);
    pop(top_node);
    display(top_node);
    pop(top_node);
    display(top_node);
    pop(top_node);
    display(top_node);
    push(1, top_node);
    display(top_node);
    destroy(top_node);
    return (EXIT_SUCCESS);
}

void display(node * top_node)
{
    node * temp = top_node;
    if(top_node == NULL)
    {
        printf("The stack is empty\n");
        return;
    }
    while(temp != NULL)
    {
        printf("%d\n ", temp-> info);
        temp = top_node -> ptr;
    }
}

void push(int data, node * top_node)
{
    if(top_node == NULL)
    {
        top_node = (struct node **) malloc(1*sizeof(struct node));
        top_node ->ptr = NULL;
        top_node -> info = data;         
    }
    else
    {
        node * temp = (struct node *) malloc(1*sizeof(struct node));
        temp -> ptr = top_node;
        temp -> info = data;
        top_node = &temp;
    }  
}

void pop(node * top_node)
{
    node * new_top = top_node;
    if(new_top == NULL)
    {
        printf("\nERROR, the stack is empty");
        return;
    }
    else
    {
        new_top = new_top -> ptr;
        printf("popped value = %d", top_node -> info);
        free(top_node);
        top_node = new_top;
    }
}

void destroy(node * top_node)
{
    node * temp = top_node;
    while(temp != NULL)
    {
        temp = top_node -> ptr;
        free(top_node);
        top_node = temp;
        temp = temp->ptr;   
    }
    free(temp);
}

The output that I am getting is this:

The stack is empty
ERROR, the stack is emptyThe stack is empty
ERROR, the stack is emptyThe stack is empty
ERROR, the stack is emptyThe stack is empty
The stack is empty

RUN SUCCESSFUL (total time: 227ms)

I believe that I should pass a pointer to stack, I tried implementing it but it shot out a bunch of errors.

Any step in the direction without giving me the full answer would be greatly appreciated.

Turn on compiler warnings, and fix them. You have some pointer type mismatches, which is never good. — Tom Karzes, Jun 04 '16 at 03:53
"RUN SUCCESSFUL (total time: 227ms)" - According to your output your code is correct. Strange enough. — too honest for this site, Jun 04 '16 at 03:56
See my answer, for issues in addition to the one identified by other answerers. — Ahmed Akhtar, Jun 04 '16 at 05:30
why did I get downvoted? I am new to this site and so far it doesn't seem very new-user friendly. — thutchi, Jun 05 '16 at 01:03
I think that could be because you could have studied these concepts by reading some tutorials too. Also, you could have looked at some sample code that is easily available on the web. This is just my opinion, the actual downvoters may have had other reasons. Btw I did not down vote you. — Ahmed Akhtar, Jun 05 '16 at 01:09

score 1 · Answer 1 · answered Jun 04 '16 at 03:54

1

Assigning to top_node in push() has no effect because that pointer is declared locally and only exists in the stack frame of the push() function itself. Instead you could pass a pointer to the pointer that is declared in the main() function, like this

void 
push(int data, node **top_node)
{
    if (*top_node == NULL)
    {
        *top_node = malloc(sizeof(**top_node));
        if (*top_node == NULL)
            return; // maybe warn about the error or abort the whole program
        (*top_node)->ptr = NULL;
        (*top_node)->info = data;
    }    
    else
    // append the node       
}

Otherwise, the allocated space is lost forever causing a memory leak, because the pointer that was holding it's adderss is destroyed when the function returns.

answered Jun 04 '16 at 03:54

Iharob Al Asimi

52,653
6
59
97

This is what I was looking for, for my solution. I had this at one point but I could not get it to recognize top_node as a struct when assigning the pointer and the data. I assume that is because I left out the parenthesis. – thutchi Jun 04 '16 at 18:39
@thutchi More precisely, [operator precedence](http://en.cppreference.com/w/c/language/operator_precedence). – Iharob Al Asimi Jun 04 '16 at 18:52
okay thank you. I think I understand what is going on now. First time making a stack, and its been a few years since linked lists. thank you. – thutchi Jun 04 '16 at 21:45
Great work being the first one to identify the primary issue. – Ahmed Akhtar Jun 05 '16 at 04:14

Ahmed Akhtar · Accepted Answer · 2016-06-05T04:10:28.053

Apart from the issue, about the call by value to top_node, identified by both iharob and Cherubim Anand, there are other issues as well:

All functions that have to modify top_node have to get its address passed in using node ** except display because it just reads top_node without having to modify it.
The call to such a modifying function will have to pass in the address of top_node, using & operator like pop(&top_node);, instead of passing its value, as is done for display function like display(top_node);.
The usage of top_node inside such functions will have to use one level of dereferencing using * operator like *top_node except in display, where only the value is being passed.
In the display function the line temp = top_node -> ptr; will always set temp to the second element causing the loop to iterate forever. It should instead be temp = temp->ptr;.
(struct node **) malloc(1*sizeof(struct node)); in push is incorrect and should be changed to (struct node*)malloc(sizeof(struct node));. Any number multiplied by 1 remains unchanged.
The last two statements in destroy function were erroneous and had to be removed to preserve correct functionality.

Here is the modified code:

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

typedef struct node
{
    int info;
    struct node *ptr;
}node;

//create
//push
//pop
//destroy
//display
void push(int, node ** top_node);
void pop(node ** top_node);
void destroy(node ** top_node);
void display(node * top_node);
int main(int argc, char** argv) 
{
    node *top_node = NULL;

    push(1, &top_node);
    push(5, &top_node);
    push(55, &top_node);
    display(top_node);
    pop(&top_node);
    display(top_node);
    pop(&top_node);
    display(top_node);
    pop(&top_node);
    display(top_node);
    push(1, &top_node);
    display(top_node);
    destroy(&top_node);
    return (EXIT_SUCCESS);
}

void display(node * top_node)
{
    node * temp = top_node;
    if(top_node == NULL)
    {
        printf("The stack is empty\n");
        return;
    }
    while(temp != NULL)
    {
        printf("%d\n", temp->info);
        temp = temp->ptr;
    }
}

void push(int data, node ** top_node)
{
    if(top_node == NULL)
    {
        *top_node =  (struct node*)malloc(sizeof(struct node));
        (*top_node)->ptr = NULL;
        (*top_node)-> info = data;
    }
    else
    {
        node * temp = (struct node*)malloc(sizeof(struct node));
        temp -> ptr = *top_node;
        temp -> info = data;
        *top_node = temp;
    }
}

void pop(node ** top_node)
{
    node * new_top = *top_node;
    if(new_top == NULL)
    {
        printf("ERROR, the stack is empty\n");
        return;
    }
    else
    {
        new_top = new_top -> ptr;
        printf("Popped value = %d\n", (*top_node)-> info);
        free(*top_node);
        *top_node = new_top;
    }
}

void destroy(node ** top_node)
{
    node * temp = *top_node;
    while(temp != NULL)
    {
        temp = (*top_node)-> ptr;
        free(*top_node);
        *top_node = temp;
    }
}

Thank you, this falls in line with what everyone else has said. Should one cast `malloc()` ? There seems to be a discrepancy there. I think the `destroy()` function makes sense. If you are always checking temp to be equal to NULL then you are looking at the next object in the stack. Correct? Therefore you are always freeing the item above temp. Is this the wrong way to think about it? — thutchi, Jun 04 '16 at 19:09
@thutchi If you cast `malloc()` you risk a lot. [Read here for more information](http://stackoverflow.com/a/605858/1983495). Also, you can't pass a variable by reference in [tag:c], what you can do is pass a pointer to the memory location the data is stored in, that's very different. You need to dereference the pointer to alter it whereas you don't need to do anything special with a variable that is a reference. Notably, [tag:c++] has pass by reference, so mixing these concepts can become a problem. — Iharob Al Asimi, Jun 04 '16 at 22:39
@iharob that makes sense now. In school we were taught with casting. weird. I do have one more question when @Ahmed Akhtar frees `top_node` in the `destroy()` function he does not `free(temp)` I ran this through a memory leak checker and it works the way he wrote it. So, why don't we have to`free(temp)` — thutchi, Jun 04 '16 at 23:16
@thutchi The destroy function basically stores the next element for a while in `temp` and then `free`s the previous element and then resets `top_node` to the next element previously stored in `temp`.This way all memory gets freed up and there remains no question of freeing up `temp`. — Ahmed Akhtar, Jun 05 '16 at 00:59
@AhmedAkhtar I think I am beginning to understand what is happening. The wording may not be correct but this is what I am thinking: temp still holds the pointers to the address of the data in 'current_node`. therefore, you are freeing the information that temp was pointing to anyways, because both pointers point to the same place. Is that the correct way to look at it? — thutchi, Jun 05 '16 at 01:13
@thutchi After this line `temp = (*top_node)-> ptr;` temp points to the next element in line, which may also be `NULL`, and `top_node` points to the previous element which needs to be deleted before moving `top_node` forward. — Ahmed Akhtar, Jun 05 '16 at 01:19
@AhmedAkhtar Ahh! I understand it now. Thank you for helping me get some cobwebs out of the brain. — thutchi, Jun 05 '16 at 01:22
@thutchi Glad to help. An upvote would help, I too am a university student like you. — Ahmed Akhtar, Jun 05 '16 at 01:39
@iharob Thanks, I have done that. That would be a great help and display of sportsmanship. — Ahmed Akhtar, Jun 05 '16 at 04:11

Trouble with pointers and stack implementation

2 Answers2