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:
1 2 3 4
|
typedef struct stack {
int data;
struct stack *next;
} STACK;
|
This part I completely understand.
1 2 3 4 5 6 7 8 9 10 11 12 13
|
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.
1 2 3 4 5 6 7 8 9 10 11 12 13
|
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.