Implementation of Stack using Linked List in C

Question

Menu Driven program in C implementing all the stack operations using linked list 

Answer 1

Linked List Implementation for Stack

Linked List

• Linked List can be defined as collection of objects called nodes that are randomly stored in the memory.
• A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory.
• The last node of the list contains pointer to the null.
• It allocates the memory dynamically. All the nodes of linked list are non-contiguously stored in the memory and linked together with the help of pointers.
• Sizing is no longer a problem since we do not need to define its size at the time of declaration. List grows as per the program's demand and limited to the available memory space.

Adding a node to the stack (Push operation)

• Create a node first and allocate memory to it.
• 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.
• 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)

• 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.
• 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)

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

Program Code

#include <stdio.h> #include <stdlib.h> struct node {     int info;     struct node *ptr; }*top,*top1,*temp; int topelement(); void push(int data); void pop(); void isEmpty(); void display(); void element_count(); void create(); int count = 0; void main() {     int no, ch, e;     printf("\n1.Push");     printf("\n2.Pop");     printf("\n3.Top");     printf("\n4.Empty");     printf("\n5.Exit");     printf("\n6.Dipslay");     printf("\n7.Stack Count\n");     create();     while (1)     { printf("\nEnter choice:"); scanf("%d",&ch); switch (ch) { case 1:     printf("Enter data:");     scanf("%d", &no);     push(no);     break; case 2:     pop();     break; case 3:     if (top == NULL) printf("No elements in stack");     else     { e = topelement(); printf("\nTop element:%d", e);     }     break; case 4:     isEmpty();     break; case 5:     exit(0); case 6:     display();     break; case 7:     element_count();     break; default :     printf("Enter correct choice!");     break; }     } } /* Create empty stack */ void create() {     top = NULL; } /* Count stack elements */ void element_count() {     printf("\nNo. of elements in stack: %d", count); } /* Push data into stack */ void push(int data) {     if (top == NULL)     { top =(struct node *)malloc(1*sizeof(struct node)); top->ptr = NULL; top->info = data;     }     else     { temp =(struct node *)malloc(1*sizeof(struct node)); temp->ptr = top; temp->info = data; top = temp;     }     count++; } /* Display stack elements */ void display() {     top1 = top;     if (top1 == NULL)     { printf("Stack is empty"); return;     }     while (top1 != NULL)     { printf("%d ", top1->info); top1 = top1->ptr;     }  } /* Pop Operation on stack */ void pop() {     top1 = top;     if (top1 == NULL)     { printf("\n Error: Trying to pop from empty stack"); return;     }     else top1 = top1->ptr;     printf("\nPopped value: %d", top->info);     free(top);     top = top1;     count--; } /* Return top element */ int topelement() {     return(top->info); } /* Check if stack is empty or not */ void isEmpty() {     if (top == NULL) printf("\nStack is empty");     else printf("\nStack is not empty & contains %d elements", count); }

Output

---

For more UTU III Sem DSA Lab Experiments Click here

For other University DSA Lab Experiments Click here

---

Answer 2

27/04/2020

Stack Operations using Linked List

To implement a stack using a linked list, we need to set the following things before implementing actual operations.

• Step 1 - Include all the header files which are used in the program. And declare all the user defined functions.
• Step 2 - Define a 'Node' structure with two members data and next.
• Step 3 - Define a Node pointer 'top' and set it to NULL.
• Step 4 - Implement the main method by displaying Menu with list of operations and make suitable function calls in the main method.

push(value) - Inserting an element into the Stack

We can use the following steps to insert a new node into the stack...

• Step 1 - Create a newNode with given value.
• Step 2 - Check whether stack is Empty (top == NULL)
• Step 3 - If it is Empty, then set newNode → next = NULL.
• Step 4 - If it is Not Empty, then set newNode → next = top.
• Step 5 - Finally, set top = newNode.

pop() - Deleting an Element from a Stack

We can use the following steps to delete a node from the stack...

• Step 1 - Check whether stack is Empty (top == NULL).
• Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is not possible!!!" and terminate the function
• Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set it to 'top'.
• Step 4 - Then set 'top = top → next'.
• Step 5 - Finally, delete 'temp'. (free(temp)).

display() - Displaying stack of elements

We can use the following steps to display the elements (nodes) of a stack...

• Step 1 - Check whether stack is Empty (top == NULL).
• Step 2 - If it is Empty, then display 'Stack is Empty!!!' and terminate the function.
• Step 3 - If it is Not Empty, then define a Node pointer 'temp' and initialize with top.
• Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same until temp reaches to the first node in the stack. (temp → next != NULL).
• Step 5 - Finally! Display 'temp → data ---> NULL'.

Implementation of Stack using Linked List | C Programming

#include<stdio.h>
#include<conio.h>

struct Node
{
   int data;
   struct Node *next;
}*top = NULL;

void push(int);
void pop();
void display();

void main()
{
   int choice, value;
   clrscr();
   printf("\n:: Stack using Linked List ::\n");
   while(1){
      printf("\n****** MENU ******\n");
      printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
      printf("Enter your choice: ");
      scanf("%d",&choice);
      switch(choice){
	 case 1: printf("Enter the value to be insert: ");
		 scanf("%d", &value);
		 push(value);
		 break;
	 case 2: pop(); break;
	 case 3: display(); break;
	 case 4: exit(0);
	 default: printf("\nWrong selection!!! Please try again!!!\n");
      }
   }
}
void push(int value)
{
   struct Node *newNode;
   newNode = (struct Node*)malloc(sizeof(struct Node));
   newNode->data = value;
   if(top == NULL)
      newNode->next = NULL;
   else
      newNode->next = top;
   top = newNode;
   printf("\nInsertion is Success!!!\n");
}
void pop()
{
   if(top == NULL)
      printf("\nStack is Empty!!!\n");
   else{
      struct Node *temp = top;
      printf("\nDeleted element: %d", temp->data);
      top = temp->next;
      free(temp);
   }
}
void display()
{
   if(top == NULL)
      printf("\nStack is Empty!!!\n");
   else{
      struct Node *temp = top;
      while(temp->next != NULL){
	 printf("%d--->",temp->data);
	 temp = temp -> next;
      }
      printf("%d--->NULL",temp->data);
   }
}