CODEWITHSUNDEEP
csegmentation-faultstack
user3277837
user3277837

Reputation:

C Programming Stack

I am currently working on stacks right now. I am supposed to use the following structures and function prototypes: 

typedef struct node_{
    char data;
    struct node_ *next;
}node;

typedef struct stack_{
    unsigned int size;
    node* stack;
}stack;

stack* create_stack();
void   push(stack* s, char val);

Here is my actual code for create_stack() and push():

stack* create_stack()
{
    stack *stack;
    stack = malloc(sizeof(stack));
    stack->size = 0;
    stack->stack = NULL;
    return stack;
}

void push(stack* s, char val)
{
    stack *newStack;
    newStack = create_stack();
    newStack->stack->data = val;
    newStack->stack = s->stack;
    s = newStack;
}

I am getting a segmentation fault when I try to store char val into newStack->stack->data. How does this not work? What do I need to do to make this stack on top???

Upvotes: 1

Views: 181

Answers (3)

SirDarius
SirDarius

Reputation: 42889

The push function is wrong.

void push(stack* s, char val)
{
    stack *newStack;
    newStack = create_stack(); /* new stack created, why not work on the existing one ? */
    newStack->stack->data = val; /* you're writing to a NULL pointer */
    newStack->stack = s->stack;
    s = newStack; /* this will not be visible from outside the function */
}

First of all, you are trying to recreate a new stack for each call of this function, which is certainly not what is intended.

If you try to modify the value of s, it will not be visible from outside the function, and you will still have your original stack.

Then, you are accessing the stack->data member even though stack has no space allocated to it yet (because you set it to NULL). You actually set it right after, which is why it crashes, most probably.

You probably want to do something like this:

void push(stack* s, char val)
{
    node * n;

    /* go to the end of the "stack" */
    n = s->stack;
    while (n != NULL) {
        n = n->next;
    }

    /* allocate memory for a new node */
    n = malloc(sizeof(node));

    /* initialize node */
    n->data = val;
    n->next = NULL;

    /* increment stack size */
    s->size++;
}

And as mentionned before, this is merely a singly-linked list which is not the best fit for a stack, because as it exists now, you have to follow the node pointers to reach the last element, which makes push and pop operations O(N).

A faster implementation would look like this:

void push(stack* s, char val)
{
    node * first_node, * new_node;
    first_node = s->stack;

    /* allocate memory for a new node */
    new_node = malloc(sizeof(node));

    /* initialize node */
    new_node->data = val;
    new_node->next = first_node;

    /* increment stack size */
    s->stack = new_node;
    s->size++;
}

The top of the stack is always the first node, and the performance is O(1).

Upvotes: 2

mah
mah

Reputation: 39807

Follow your code....

stack *newStack = create_stack();   // in push()
    newStack = malloc(sizeof(stack)); // in create_stack()
    newStack->stack = NULL; // in create_stack()
newStack->stack->data = val; // in push()... this is where you crash.

Upvotes: 1

TypeIA
TypeIA

Reputation: 17248

Because newStack->stack is a NULL pointer. Your create_stack() function sets it to NULL, and you then dereference it. You have to allocate a struct node somewhere.

This code also has some readability issues which might be contributing to the problem. You are naming variables the same names as their types, which is very confusing. Consider using some other naming pattern like stack_t for types and stack for variable names.

Upvotes: 0

Related Questions