When implementing stack using an array we make an array behave like a stack in the same way here we need to make a linked list behave like a stack to implement stack using a linked list. We do this by following a property of stack which is, an element can only be inserted and deleted from one end called the top end of the stack.
In the image above there is a linked list containing 4 elements imagine it as a stack. The first node is the top position. Since in a stack elements can only be inserted and deleted from the top end so in linked list implementation of stack we should only allow nodes to be added at the beginning of the linked list and also deletion should be allowed at the beginning of the linked list only.
Nodes store data which can be integer value, float etc. and allowing nodes to be inserted and deleted from one end of the linked list ie; the top end will make a linked list behave like a stack. This is called implementing stackc using a linked list.
What functions do we need in our program?
We need a function to insert nodes at the beginning of the linked list
A function to delete nodes at the beginning of the list
and a display function to display the elements.
If you know linked list or you understood the previous tutorial on linked lists then you very must know how to make those functions listed above.
The only difference is that instead of naming the pointer variable start which holds the address of the first node, here we named it as top as it sounds more appropriate in the case of stack.
Structure of the nodes
struct node
{
int info;
struct node *link;
}*top=NULL;
Pointer top is of type struct node and it is assigned the value of NULL. Remember here we have declared and initialized top in global section of the program so its not local to any function all the functions will have access to the top variable and its value will be updated without returning the value of top in the functions.
void push(int num)
{
struct node *temp;
temp = (struct node *)malloc(sizeof(struct node));
if (temp==NULL)
{
printf("stack overflown");
return;
}
temp->info = num;
temp->link = top;
top = temp;
}
You should know that in case of a linked list memory is dynamically allocated during run time with the help of malloc() function but if there is no memory left to be allocated or the system runs out of memory then malloc function returns NULL value and it is assigned to temp so if temp is equal to null it means there is no memory left and stack is full.
If it is not full then malloc() returns the address of the allocated memory location and assigns it to temp.
 temp->info = num;
temp->link = top;
top = temp;
temp is the newly created node and num is the number entered by the user which is going to get stored in the node which the help of the statement temp->info = num
 Top holds the address of the first node or NULL in case of an empty list.
 temp->link = top; it assigns link part of the newly created node the value of top. In case of an empty list null is assigned and in case of a non-empty list the address of the first node is assigned to the link part of the new node making the node the first node in the list and the previously the node which was the first node now becomes the second node in the list.
top = temp; pointer variable temp has the address of the new node which is assigned to top because top should always store the address of the first node.
Deletion from the top or from the beginning of the list.
int pop()
{
struct node *temp;
int num;
if (top==NULL)
{
printf("underflown");
return;
}
temp=top;
num = top->info;
top = top->link;
free(temp);
return num;
}
If top is equal to null then list is empty and its an underflow condition for a stack.
temp=top; assigning temp the value of top which is the address of the node to be deleted ie; the first node.
num = top->info; assigning num top->info which is the data or number stored in the info part of the first node to be returned later because the function pop() is of type int not void.
top = top->link; top should store the address of the first node, when the first node is deleted the second node in the list should become the first node and top->link which means the link part of the first node contains the address of the second node which is assigned to top.
free(temp); temp has the address of the first node which is to be deleted and free function completely deletes it by freeing that memory location or address. Dynamically allocated memory has to be freed using free function.
Display function:
void display()
{
struct node *p;
if (top==NULL)
{
printf("underflown");
return;
}
printf("n Stack is: n");
p=top;
while (p!=NULL)
{
printf("%dn",p->info);
p=p->link;
}
}
