A stack is a linear data structure that follows the principle of Last In First Out (LIFO). It is a collection of items of the same type. This means the last element inserted inside the stack is removed first. Stack supports various operations like push, pop, peek, empty and size. It can be implemented using array and linked list. Benefit of implementing stack using linked list in C over arrays is that, it allows to grow the stack as per the requirements,i.e, memory can be allocated dynamically.

A stack is represented using nodes of a linked list. Each node consists of two parts: data and next(storing address of next node). The data part of each node contains the assigned value and the next points to the node containing the next item in the stack. The top refers to the topmost node in the stack. Both the push() and pop() operations are carried out at the front/top of the linked list and hence takes O(1) time.

A stack can also be implemented using arrays. But arrays are of limited size and size of stack has to be predetermined whereas in a linked list implementation nodes can be added according to the user's requirements.

Basic Operations on Stack

There are some basic operations that allow us to perform different actions on a stack.

• Push: Add an element to the top of a stack
• Pop: Remove an element from the top of a stack
• IsEmpty: Check if the stack is empty
• IsFull: Check if the stack is full
• Peek: Get the value of the top element without removing it

Algorithm

In linked list implementation of stack, the nodes are maintained non-contiguously in the memory. Each node contains a pointer to its immediate successor node in the stack. Stack is said to be overflown if the space left in the memory heap is not enough to create a node.

The top most node in the stack always contains null in its address field. Lets discuss the way in which, each operation is performed in linked list implementation of stack.

The operations on Stack using Linked List

⚈ Adding a node to the stack (Push operation) :

Adding a node to the stack is referred to as push operation. Pushing an element to a stack in linked list implementation is different from that of an array implementation. In order to push an element onto the stack, the following steps are involved.

1. Create a node first and allocate memory to it.
2. If the list is empty then the item is to be pushed as the start node of the list. This includes assigning value to the data part of the node and assign null to the address part of the node.
3. If there are some nodes in the list already, then we have to add the new element in the beginning of the list (to not violate the property of the stack). For this purpose, assign the address of the starting element to the address field of the new node and make the new node, the starting node of the list.

⚈ Deleting a node from the stack (POP operation) :

Deleting a node from the top of stack is referred to as pop operation. Deleting a node from the linked list implementation of stack is different from that in the array implementation. In order to pop an element from the stack, we need to follow the following steps :

1. Check for the underflow condition : The underflow condition occurs when we try to pop from an already empty stack. The stack will be empty if the head pointer of the list points to null.
2. Adjust the head pointer accordingly : In stack, the elements are popped only from one end, therefore, the value stored in the head pointer must be deleted and the node must be freed. The next node of the head node now becomes the head node.

⚈ Display the nodes (Traversing) :

Displaying all the nodes of a stack needs traversing all the nodes of the linked list organized in the form of stack. For this purpose, we need to follow the following steps :

1. Copy the head pointer into a temporary pointer.
2. Move the temporary pointer through all the nodes of the list and print the value field attached to every node.

Program using C

//STACK USING LINKED LIST #include<stdio.h> #include<stdlib.h> void push(int); int pop ();\ void display(); struct node { int info; struct node *next; }*tos = NULL; int main() { int ch, item; while(1) { printf("\n\n1.Push\n2.Pop\n3.Display\n4.Exit\n\nEnter your choice: "); scanf("%d",&ch); switch(ch) { case 1: printf("\nEnter the item: "); scanf("%d",&item); push(item); break; case 2: item=pop(); if(item!=1) printf("\nThe Popped data item is: %d",item) ; break; case 3: display(); break; case 4: exit(0); default: printf("Invalid Choice."); } } } void push(int item) { struct node *nw; nw=(struct node*) malloc(sizeof(struct node)); nw->info = item; nw->next = tos; tos = nw; } int pop () { int item; struct node *ptr; if(tos == NULL) { printf("\nUnderflow"); return(-1); } else { ptr= tos; item=tos -> info; tos = tos -> next; free(ptr); return(item); } } void display() { struct node *curr; if(tos == NULL) printf("\nStack is Empty"); else { printf("\nThe Stack is : "); curr = tos; while(curr != NULL) { printf("%d<-",curr->info); curr = curr->next; } } }