[Solved] Pop() function for stack in C

Question

It would help to see how you push items onto the stack. If you’re really calling pop without a push first, well, then it’s not supposed to do anything, is it?

This bit makes me nervous:

Node *aux,*prev;
prev = *stack;
aux = prev->next;
if(aux == NULL)
{
    free(prev);
    return;
}

You set prev to *stack, and if nothing follows prev, you free it. Note that since prev == *stack, you’ve also freed *stack, so that pointer is now invalid. If you try to access that pointer in your caller, you’ll invoke Undefined Behavior.

It looks like you’re making your list tail the top of the stack; I’m going to tell you right now that you will make your life much simpler if you make the list head the top of the stack, such that your pushes and pops look like the following:

bool push( Node **l, int val )
{
  Node *p = calloc( 1, sizeof *p );
  if ( p )
  {
    p->v = val;
    p->next = *l;   // set p to point to the current head of the list
    *l = p;         // make p the new head of the list
  }
  return p != NULL;  // will return false if the calloc (and by extenion,
}                    // the push operation) fails.  

bool pop( Node **l, int *v )
{
  Node *p = *l;      // p points to head of list
  if ( !p )
    return false;

  *v = p->val;     // get value in current node
  *l = p->next;    // make the next element the new list head
  p->next = NULL;  // sever the old list head
  free( p );       // and deallocate it

  return true;
}

No list traversals, no need to keep track of current and previous nodes. All you care about is the head node. The statement p->next = NULL; isn’t strictly necessary since we immediately free p afterwards. I like it because it makes it obvious that we have removed p from the list, but if you don’t want to spare the cycles, you can omit it.

Edit

I was right to be nervous about that code.

So here’s basically what’s happening – when you have exactly one item in the stack, you free the head of the list, but you don’t update the value of the list pointer (*stack in the original code, *l in the latest edit). The value of the stack variable in main is unchanged, and now it’s invalid – the memory at that address is no longer allocated. So the next time you call push, it sees that *l is not NULL, and attempts to traverse down the (non-existent) list.

At this point the behavior is undefined; literally anything can happen. On my system after the first push, stack has the value 0x501010. I do a pop, which frees that memory, but doesn’t change the value of stack. On the next push, *l is not NULL, so I set (*l)->next to whatever malloc returns, which in my case is…0x501010 again. So *l is 0x501010, and (*l)->next is 0x501010. If I try to push another item, I wind up in an infinite loop (p == p->next).

To fix this, you need to set the list pointer to NULL after you free it:

Node *aux,*prev;
prev = *l;
aux = prev->next;
if(aux == NULL)
{
    free(prev);
    *l = NULL;
    return;
}

Accepted Answer