Unexpected results implementing stacks with linked lists

Question

I am writting this program, and I want to understand why I am getting the wrong printing (which should de 1,2,3,4,5) gives some address instead. My stackIsEmpty() does not even act as it is meant to that is to stop printing values when the stack is empty. Here is my code:

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

//Stacks using Structures and linked list and pointerws.

typedef struct Stack{
    //Type of the elements of the stack. Here integers
    int elem;
    //To of the stack
    struct Stack* previous;
} Stack;

void initialize(Stack *st);
void push(Stack *st, int element);
int pop(Stack *st);
int stackIsEmpty(Stack *st);

int main(){
    int i;
    Stack st;
    Stack *pt_st = &st;
    initialize(pt_st);

    //Test phase...
    for(i=0; i<5; i++)
        push(pt_st, i+1);

    for(i=0; i<5; i++)
        printf("here is one element: %d\n", pop(pt_st));
    //End of test with error!
    return 0;
}

void initialize(Stack *st){
    st = NULL;
}

void push(Stack *st, int element){
    Stack *sta = (Stack*)malloc(sizeof(Stack));
    if (sta != NULL)
    {
        sta->previous = st;
        sta->elem = element;
        st = sta;
        free(sta);
    }
    else
        exit(0);
}

int pop(Stack *st){
    if(!stackIsEmpty(st))
    {
        printf("stack is empty cannot pop\n");
        return 0;
    }
    else
    {
        int number = st->elem;
        Stack* copy = st->previous;
        free(st);
        st = copy;
        return number;
    }
}

int stackIsEmpty(Stack *st){
    if(st == NULL)
        return 0;
    else
        return 1;
}

I think i could put in the address of `sta` into `st`. And I free the allocated space to the variable `sta`. — franckstifler, Jan 18 '16 at 10:34

Viktor Simkó · Answer 1 · 2016-01-18T11:12:56.890

The Stack pointer pt_st You've created is passed by value to the functions, so the functions only modifying a local copy of it.

You can create a pointer to pointer, or make pt_st a global variable.

Your push function also has problems.

I've modified your code, made pt_st global, so it works now:

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

//Stacks using Structures and linked list and pointerws.

typedef struct Stack{
    //Type of the elements of the stack. Here integers
    int elem;
    //To of the stack
    struct Stack* previous;
} Stack;

void initialize();
void push(int element);
int pop();
int stackIsEmpty();

Stack *pt_st; // made pt_st global, so functions can modify it

int main(){
    int i;
    initialize();

    //Test phase...
    for(i=0; i<5; i++)
        push(i+1);

    for(i=0; i<5; i++)
        printf("here is one element: %d\n", pop(pt_st));
    //End of test with error!
    return 0;
}

void initialize(){
    pt_st = NULL; // set it to NULL
}

void push(int element){
    Stack *sta = malloc(sizeof(Stack)); // don't need to cast malloc
    sta->elem = element;

    sta->previous = pt_st; // set sta's previous

    pt_st = sta; // point to the pushed node
}

int pop(){
    if(stackIsEmpty())
    {
        printf("pt_stack is empty cannot pop\n");
        return 0;
    }
    else
    {
        int number = pt_st->elem;
        Stack *temp = pt_st; // create a temp copy of the first node's address
        pt_st = pt_st->previous;
        free(temp);
        return number;
    }
}

int stackIsEmpty(){
    if(pt_st == NULL)
        return 1; // if pt_st is NULL, then the stack is empty
    else
        return 0;
}

score 0 · Answer 2 · edited May 23 '17 at 11:52

I think you need to read something about passing values by copy: What's the difference between passing by reference vs. passing by value?

initialize makes nothing, you pass an address (by value) so anything will be reported in you main. This is almost the same for every function. You also free immediately after having allocated a structure. You must pass the pointer to stack by address, as the top of the stack is modified by your functions :

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

//Stacks using Structures and linked list and pointerws.

typedef struct Stack{
    //Type of the elements of the stack. Here integers
    int elem;
    //To of the stack
    struct Stack* previous;
} Stack;

void initialize(Stack **st);
void push(Stack **st, int element);
int pop(Stack **st);
int stackIsEmpty(Stack *st);

int main(){
    int i;
    Stack *pt_st;
    initialize(pt_st);

    //Test phase...
    for(i=0; i<5; i++)
        push(&pt_st, i+1);

    for(i=0; i<5; i++)
        printf("here is one element: %d\n", pop(&pt_st));
    //End of test with error!
    return 0;
}

void initialize(Stack **st){
    *st = NULL;
}

void push(Stack **st, int element){
    Stack *sta = (Stack*)malloc(sizeof(Stack));
    if (sta != NULL)
    {
        sta->previous = *st;
        sta->elem = element;
        *st = sta; // new top of stack is sta            
    }
    else
        exit(0);
}

int pop(Stack **st){
    if(!stackIsEmpty(*st))
    {
        printf("stack is empty cannot pop\n");
        return 0;
    }
    else
    {
        int number = (*st)->elem;
        Stack* copy = (*st)->previous;
        free(*st);
        *st = copy;
        return number;
    }
}

int stackIsEmpty(Stack *st){
    if(st == NULL)
        return 0;
    else
        return 1;
}

Also try to avoid to exit prematurely in your functions, it is better to return an error code and let the caller take the decision, something like:

//pseudo code
int push(...) {
   if alloc fails return -1
   else { do the trick; return 0;
}

...
if (push(...)==-1) { print "something's wrong"; exit 0; }

It should be slightly different with pop as you need both to return a value on success and an error code on failure:

int pop(Stack **st,int *pop) {
    if (staksIsEmpty(st)) return -1;
    *pop = *(st.elem);
    ...
    return 0;
}

...
int value;
if (pop(&pt_st,&value)==-1) //error

I appriciate that remark, and i am just asking my self if it happens that the value I return is containned in the one the user provided. How should i manage to distiguish the `return integer` from the `return error`? — franckstifler, Jan 18 '16 at 16:39
You're right I've made a mistake, I was talking about push, need an edit for pop... — Jean-Baptiste Yunès, Jan 18 '16 at 18:14

Unexpected results implementing stacks with linked lists

2 Answers2