- Write a program in C to implement a stack data structure using singly linked list.

We have to **implement a Stack data structure using linked list**. Linked list implementation of stack data structure must support basic **stack operations** like push, pop, peek and isEmpty.

Given a singly linked list whose node structure is as follows:

struct node { int data; struct node *next; }

- We will maintain only one node pointer "top", which always points to the head node of linked list. This will ensure that we will add or remove node from one end of linked list.
- We will start with an empty linked list, where top pointer is set to NULL.
**Push Operation**: We will dynamically allocate memory for a struct node variable(let's say temp). Then we will attach new node in front of linked list by setting temp- >next = top. Finally set top pointer to temp.(top = temp;)**Pop Operation**: Remove head node(pointed by top pointer) of the linked list. Store the top pointer in a temp variable. Now, move top pointer to next node(top = top->next;). Deallocate memory of temp node using free.**Peek Operation**: Returns the value of head node of linked list without removing it.(return top->data;)**Is Empty Check**: Check if top pointer is NULL or not. If top pointer is null then**stack**is empty otherwise non-empty.

**Advantage of Implementing a Stack as Linked List**

Dynamic size of stack. We can increase or decrease size of stack at runtime. Unlike array implementation of

**stack**, there is no limit of maximum element in stack.

## C program to Implement a Stack using Singly Linked List

/* * C Program to Implement a Stack using Linked List */ #include <stdio.h> #include <stdlib.h> struct node { int data; struct node *next; }*top; /* Initialize an empty stack */ void initialize() { top = NULL; } /* Checks if Stack is empty or not */ int isEmpty() { if (top == NULL) return 1; else return 0; } /* Returns the top element of Stack */ int peek() { return top->data; } /* Count stack elements */ int getStackSize(struct node *head){ /* Input Validation */ if (head == NULL) { printf("Error : Invalid stack pointer !!!\n"); return; } int length = 0; while(head != NULL){ head = head->next; length++; } return length; } /* Push an Element in Stack */ void push(int num) { struct node *temp; temp =(struct node *)malloc(1*sizeof(struct node)); temp->data = num; if (top == NULL) { top = temp; top->next = NULL; } else { temp->next = top; top = temp; } } /* Pop Operation: Removes Top Element of the Stack */ void pop() { struct node *temp; if (isEmpty(top)) { printf("\nStack is Empty\n"); return; } else { temp = top; top = top->next; printf("Removed Element : %d\n", temp->data); free(temp); } } /* Prints the linked list representation of a stack */ void printStack(struct node *nodePtr) { while (nodePtr != NULL) { printf("%d", nodePtr->data); nodePtr = nodePtr->next; if(nodePtr != NULL) printf("-->"); } printf("\n"); } void main() { /* Initialize Stack */ initialize(); /* Push Elements in stack */ push(1); push(2); push(3); push(4); /* Prints Size of Stack */ printf("Stack Size : %d\n", getStackSize(top)); /* Printing top element of Stack */ printf("\nTop Element : %d\n", peek()); /* Printing Stack */ printf("Stack as linked List\n"); printStack(top); /* Removing elements from stack */ pop(); pop(); pop(); pop(); pop(); printStack(top); return; }Output

Stack Size : 4 Top Element : 4 Stack as linked List 4-->3-->2-->1 Removed Element : 4 Removed Element : 3 Removed Element : 2 Removed Element : 1 Stack is Empty