Don't understand implementation of linked lists for stacks

[mothergoose729]

I am having a hard time understanding the C implementation of a linked list for a stack. From what I understand, a linked list is a data type where the fist member is the data, and the second is a pointer to the next element of the stack.

The Wikipedia implementation is as follows:

typedef struct stack {
    int data;
    struct stack *next;
} STACK;

This part I completely understand.

void push(STACK **head, int value)
{
    STACK *node = malloc(sizeof(STACK));  /* create a new node */
 
    if (node == NULL){
        fputs("Error: no space available for node\n", stderr);
        abort();
    } else {                                      /* initialize node */
        node->data = value;
        node->next = empty(*head) ? NULL : *head; /* insert new head if any */
        *head = node;
    }
}

I don't really get what the STACK **header item being passed is. Also, I am not sure exactly what is happening at the else statement. I know what should be happening, is the function should be creating a new element of STACK type, settings the new STACK pointer to null, and setting the STACK pointer of the item below it to point to the new item on the stack. The syntax is not something I am used to though, so I am not following the operations.

int pop(STACK **head)
{
    if (empty(*head)) {                          /* stack is empty */
       fputs("Error: stack underflow\n", stderr);
       abort();
    } else {                                     //pop a node 
        STACK *top = *head;
        int value = top->data;
        *head = top->next;
        free(top);
        return value;
    }
}

Likewise, I don't really understand what the STACK **head pointer is. I am not sure what the if(empty(*head)) is checking. I don't really understand what this function is doing at all. I know what should be happening is the element below the popped element should have its next pointer set to a null state, and the item popped should be returned and the STACK data item deleted.

Any help with better understanding this code, and linked lists in general, would be much appreciated.

[IceThatJaw]

**head is a double pointer. The most common use of them is to pass a pointer by reference, that is by it's address.

I never delved to deep into how to implement Stacks as linked lists so I can't help u with the rest.


EDIT - empty and free look to be part of the STACK class. You will need the full source code to really understand what is going on.

[deathmoon]

wow, instead of passing pointers it is simpler to pass the position you want to put and let the stack implementation put it for you. Carrano's Data Abstraction and Problem Solving with C++ explained this.

[Peter87]

STACK **head is a pointer to a pointer to the top of the stack.

STACK *stackTop = NULL;
push(&stackTop, 5);
// stackTop will now point to the top element of the stack having value 5 

I think you have misunderstood in what direction the pointers should point. The next pointer points to the (old) element below.

node->next = empty(*head) ? NULL : *head;
is using the ternary operator. http://www.cplusplus.com/articles/1AUq5Di1/
It could have been written like this instead

if (empty(*head))
{
	node->next = NULL;
}
else
{
	node->next = *head;
}

empty(*head) checks if the stack is empty. Probably by checking if head == NULL. empty is probably a function or a macro defined somewhere.

*head = node;
The new top of the stack is the new node so this line changes the head (top) pointer to point to the new node.


It is an error to call pop on an empty stack so that is why they check if the stack is empty in pop.

// Make a copy of the top pointer. 
STACK *top = *head;
// Make a copy of the top node's data.
int value = top->data;
// Make the one below the top node to the new top of the stack.
*head = top->next;
// Free the old top node. This is why we had to make a copy of the top node 
// because *head no longer points to the old top.
free(top);
// Return the value of the "popped" top node. This is why we had to make a copy 
// of the data because the node containing the data no longer exists.
return value;