Write a C Program to Implement a Stack using Linked List (Pointer)

by

Aim:

Write a C Program to Implement a Stack Using Linked List (Pointer).

Theory:

Linked List Implementation:

  • We go for a linked list implementation of a stack rather than an array implementation because of the run-time memory allocation feature of linked lists.
  • In this implementation, we make a head pointer and make it point to the first created node in the stack.
  • Whenever a new node is pushed into the stack we make the head pointer point to the new node and the new node to point to the already existing node that was pointed by the head pointer.
  • The popping of an element from the stack.
  • The element that was inserted last would be popped out first.
  • So, the head pointer is now made to point to the First Node, which was pointed by the Second Node and the Second Node is freed.

Algorithm:

  1. Create a structure with an element (Element) and a pointer (Next) that points to the next node in the list.
  2. Create a head pointer using the malloc function and assign the resultant pointer variable to the head pointer S.
  3. In the Push operation, create a new node, called TmpCell using the malloc function, assign the new element X to TmpCell->Element, make TmpCell point to the node that was previously pointed to by the head pointer and make the head pointer point to TmpCell by the statements: TmpCell->Next=S->Next and S->Next=TmpCell.
  4. In the Pop operation, store the node pointed to by the head pointer in a pointer called FirstCell by the statement FirstCell=S->Next. Then make the head pointer point to the node next to FirstCell by the statement S->Next=S->Next->Next. Then free FirstCell.
  5. In the Top operation, return the element pointed to by the head pointers next node by the statement S->Next-> Element.

Program:

#include<stdio.h>
#include<stdlib.h>
/* Node decleration */
struct node
{
int data;
struct node *link; //to maintain the link other nodes
};
struct node *top,*temp;
void create();
void push();
void pop();
void display();
void main()
{
int ch;
//clrscr();
while(1)
{
printf("\n\n 1.CREATE \n 2.PUSH \n 3.POP \n 4.EXIT \n");
printf("\n ENTER YOUR CHOICE : ");
scanf("%d",&ch);

switch(ch)
{
case 1:
create();
display();
break;
case 2:
push();
display();
break;
case 3:
pop();
display();
break;
case 4:
exit(0);
}
}
}
/* create function create the head node */
void create()
{
printf("\nENTER THE FIRST ELEMENT: ");
temp=(struct node *)malloc(sizeof(struct node));
scanf("%d",&temp->data);
temp->link=NULL;
top=temp;
}
void push()
{
printf("\nENTER THE NEXT ELEMENT: ");
temp=(struct node *)malloc(sizeof(struct node));
scanf("%d",&temp->data);

temp->link=top;
top=temp;
}

void pop()
{
if(top==NULL)
{
printf("\nSTACK IS EMPTY\n");
}
else
{
temp=top;
printf("\nDELETED ELEMENT IS %d\n",top->data);
top=top->link;
free(temp);
}

}
/* display function visit the linked list from top to end */
void display()
{
temp=top; // bring the top to top position
printf("\n");
while(temp!=NULL)
{
printf("%d\n",temp->data);
temp=temp->link; // Now temp points the previous node in the list
}
}

Execution:

Input:
1 23 2 12 2 14 3 12

Output:

 1.CREATE 
 2.PUSH 
 3.POP 
 4.EXIT 

 ENTER YOUR CHOICE : 
ENTER THE FIRST ELEMENT: 
23


 1.CREATE 
 2.PUSH 
 3.POP 
 4.EXIT 

 ENTER YOUR CHOICE : 
ENTER THE NEXT ELEMENT: 
12
23


 1.CREATE 
 2.PUSH 
 3.POP 
 4.EXIT 

 ENTER YOUR CHOICE : 
ENTER THE NEXT ELEMENT: 
14
12
23


 1.CREATE 
 2.PUSH 
 3.POP 
 4.EXIT 

 ENTER YOUR CHOICE : 
DELETED ELEMENT IS 14

12
23


 1.CREATE 
 2.PUSH 
 3.POP 
 4.EXIT 

 ENTER YOUR CHOICE : 

 1.CREATE 
 2.PUSH 
 3.POP 
 4.EXIT 

 ENTER YOUR CHOICE :

Result:

Thus, Implement stack using linked list (pointer) was executed successfully.

Leave a Comment