Dynamic stack in C [pop crash]

Question

Im making a program to convert a decimal int to binary using a dynamic stack. It crashes on the last pop. ex. num: 4 output: 10crash

#include <stdio.h>

struct stack {
    struct stack *prev;
    int val;
    struct stack *next;
};
struct stack *first,*cur,*tmp;
struct stack *GETNODE(){
    struct stack *pt = (struct stack *)malloc(sizeof(struct stack));
};
int counter=1;
void push(int val){
    tmp=GETNODE();
    tmp->prev=NULL;
    tmp->val=val;
    tmp->next=NULL;
    if(first==NULL){
        first=tmp;
        cur=first;
    }else{
        tmp->prev=cur;
        cur->next=tmp;
        cur=tmp;
    }
    counter++;
};

int pop(){
    int val=tmp->val;
    cur=tmp->prev;
    free(tmp);
    tmp=cur;
    tmp->next=NULL;
    counter--;
    return(val);
};


main(){
    int num = 4;
    while(num!=0){
        push(num%2);
        num/=2;
    }
    while(counter!=1){
        printf("%d ",pop());
    }
}

[Don't cast the result of `malloc()`.](http://stackoverflow.com/questions/605845) — Jonathon Reinhart, Feb 07 '15 at 18:17
MSVC Compiler warning C4716: `'GETNODE' : must return a value.` — Weather Vane, Feb 07 '15 at 18:20
@JonathonReinhart this is how the teacher told us to do it, plus it does not seem to be the problem — user1824034, Feb 07 '15 at 18:21
If your teacher really thinks casts are a substitute for correct declarations, you need a new teacher. Tell them that. — Alex Celeste, Feb 07 '15 at 19:15
Also `main()` hasn't been a valid declaration for a while. `int main(void)` is correct. Also, checking the return value of `malloc` is not optional. — Jonathon Reinhart, Feb 08 '15 at 04:02

score 1 · Accepted Answer · answered Feb 07 '15 at 18:34

1

The problem is in your pop function. If you think about how it operates, in the final pass you will free(tmp), which is currently pointing to the very first item. After you free it, you then assign:

tmp->next=NULL;

You are trying to dereference an invalid pointer at this point.

answered Feb 07 '15 at 18:34

David Hoelzer

15,862
4
48
67

whops, thank you! i would never notice that – user1824034 Feb 07 '15 at 18:43
You *would* notice it if you stepped through your code with a debugger. – Jonathon Reinhart Feb 08 '15 at 04:03

Weather Vane · Answer 2 · 2015-02-07T18:44:31.043

I made a lot of changes to your code. Mainly, it was far too complicated - only a singly linked list was needed, and you don't need a counter - just track the list pointer. Your GETNODE() function did not return a value, causing undefined behaviour in the calling function. I simplified that too, there is no need for a separate function to allocate memory because malloc() already does that.

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

struct stack {
    struct stack *prev;
    int val;
};

struct stack *first = NULL;

void push(int val){
    struct stack *pt = malloc(sizeof(struct stack));
    if (pt == NULL){
        printf ("Bad call to malloc()\n");
        exit (1);
    }
    pt->prev=first;
    pt->val=val;
    first = pt;
}

int pop(){
    int val;
    struct stack *pt = first;
    if (first == NULL)
        return -1;
    val=first->val;
    first = first->prev;
    free(pt);
    return(val);
}

void dec2bin(int num){
    printf("%-5d", num);
    while(num!=0){
        push(num%2);
        num/=2;
    }
    while(first){
        printf("%d",pop());
    }
    printf("\n");
}

int main(void){
    dec2bin (4);
    dec2bin (129);
    dec2bin (160);
    return 0;
}

Program output:

4    100
129  10000001
160  10100000

Parham Alvani · Answer 3 · 2015-02-07T19:12:50.417

I change some part of your code and your code working now.

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

struct stack {
     struct stack *prev;
     int val;
     struct stack *next;
};

struct stack *first, *cur, *tmp;
int counter = 0;

struct stack *GETNODE()
{
     return malloc(sizeof(struct stack));
}


void push(int val)
{
    tmp = GETNODE();
    tmp->prev = NULL;
    tmp->val = val;
    tmp->next = NULL;

    if (first == NULL) {
         first = tmp;
         cur = first;
    } else {
         tmp->prev = cur;
         cur->next = tmp;
         cur = tmp;
    }
    counter++;
}

int pop(void)
{
     int val = cur->val;

     tmp = cur;
     cur = cur->prev;
     free(tmp);
     counter--;

     return val;
 }


int main(int argc, char *argv[])
{
    int num;

    scanf("%d", &num);

    while (num != 0) {
        push(num % 2);
        num /= 2;
    }
    while (counter != 0)
    printf("%d ", pop());
    printf("\n");
}

Dynamic stack in C [pop crash]

3 Answers3