1

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???

Improve this question
12
  • Obviously, newStack->stack is NULL, but you are dereferencing it with ->data. Commented Mar 17, 2014 at 15:32
  • 1
    You surely do not want to create a new stack on each push, won't you? Commented Mar 17, 2014 at 15:33
  • are you trying to allocate on heap or stack? It looks like the heap Commented Mar 17, 2014 at 15:33
  • @GIJoe allocating on the stack and creation of a stack are quite different things Commented Mar 17, 2014 at 15:34
  • 1
    @vlad_tepesch a stack is a concept, not a specific implementation. A singly linked list makes for a fine stack if the elements are pushed and popped at the head. Besides, this sounds like an assignment where the OP is required to use this structure, so recommending an array isn't going to help. Commented Mar 17, 2014 at 16:08

3 Answers 3

Reset to default
2

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).

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

2 Comments

You might consider that s could come in NULL. Also you might consider that while pushing to the end can work, performance is O(n) while you could get O(1) by pushing to the head if you're willing to change the signature to stack *push(stack *s, char val); and return the new head pointer.
@mah Agreed. Although, only the head node in the stack needs to be changed here, not the stack s itself. I admit the original naming is a little bit confusing :)
1

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.
Improve this answer

Comments

0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.