CS2208 Data Structure Lab - Implemention Of Stack Using Single Linked List using C and CPP

AIM:

Write a C or C++ program to Implement Stack using Single Linked List.
Alogarithm steps:

Step 1: create a list.

i) Create a new empty node top.

ii) Read the stack element and store it in top's data area.

iii) Assign top's link part as NULL (i.e. top->link=NULL).

iv) Assign temp as top (i.e. temp=top).

Step 2: Read next stack operation.

i) If it is Create then go to step1.

ii) If it is Push then it process following steps

a) Check Main memory for node creation.

b) Create a new node top.

c) Read the stack element and store it in top's data area.

d) Assign top's link part as temp (i.e. top->link=temp).

e) Assign temp as top (i.e. temp=top).

iii) If it is pop then it process following steps

a) If top is NULL then display stack is empty.

b) Otherwise assign top as temp (i.e. top=temp, bring the top to top position)

c) Assign temp as temp's link. (i.e. temp=temp->link, bring the temp to top's previous position).

d) Delete top from memory.

iv) If it is traverse then process the following steps

a) Bring the top to stack’s top position(i.e. top=temp)

b) Repeat until top becomes NULL

i) Display the top's data.

ii) Assign top as top's link (top=top->link).



IMPLEMENTATION USING C Program

#include
#include
#include
#include
/* 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();
/* create function create the head node */
void create()
{
printf("\nENTER THE FIRST ELEMENT: ");
top=(struct node *)malloc(sizeof(struct node));
scanf("%d",&top->data);
top->link=NULL;
temp=top;
}

/* display function visit the linked list from top to end */
void display()
{
top=temp;       // bring the top to top position
printf("\n");
while(top!=NULL)
{
printf("%d\n",top->data);
top=top->link;   // Now top points the previous node in the list
}
}
void push()
{
printf("\nENTER THE NEXT ELEMENT: ");
top=(struct node *)malloc(sizeof(struct node));
scanf("%d",&top->data);
top->link=temp;
temp=top;
}

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



IMPLEMENTATION USING C++ program

#include
#include
#include
class stack
{
 int element;
 stack* next;
public:
 stack* push(stack*,int);
 stack* pop(stack*);
 void stack_display(stack*);
}*head,object;
stack* stack::push(stack* head,int key)
{
 stack* temp,*temp1;
 temp1=head;
 temp=new stack;
 temp->element=key;
 temp->next=NULL;
 if(head==NULL)
 head=temp;
 else
 {
 while(head->next!=NULL)
 head=head->next;
 head->next=temp;
 head=temp1;
 }
 return head;
}
stack* stack::pop(stack* head)
{
 stack* temp;
 if(head!=NULL)
 {
 temp=head;
 if(head->next==NULL)
 {
  cout<<"\nthe pooped element from the stack is: "<element<  return NULL;
 }
 while(head->next->next!=NULL)
 head=head->next;
 cout<<"the popped element from the stack is  "<next->element;
 cout< head->next=head->next->next;
 head=temp;
 return head;
 }
 else
 {
  cout<<"\n\n STACK IS EMPTY ";
  return head;
 }
}
void stack::stack_display(stack* head)
{
 if(head!=NULL)
 {
 while(head->next!=NULL)
 {
  cout<element;
  head=head->next;
 }
 cout<element<<" --->TOP";
 cout< }
 /*else
  cout<<"\n\nTHE STACK IS EMPTY\n";*/
}
void choice()
{
  int key,ch;
  head=NULL;
  clrscr();
while(1)
{
 textcolor(15);
 clrscr();
 cout<<"\n\nMAIN MENU\n\n";
 cout<<"\n1.PUSH\n2.POP\n3.EXIT\n\n";
 cout<<"ENTER YOUR CHOICE : ";
 cin>>ch;

 switch(ch)
 {
 case 1:
  cout<<"\n\nENTER THE ELEMENT TO PUSH STACK : ";
  cin>>key;
  head=object.push(head,key);
  object.stack_display(head);
  break;
 case 2:
   head=object.pop(head);
  object.stack_display(head);
  break;
 case 3:
  exit(1);
 default:
  cout<<"\n\nInvalid choice...\n";
  break;
 }
}
}
void main()
{
choice();
}


OUTPUT:

SAMPLE INPUT AND OUTPUT:
  STACK
1.         CREATE
2.         PUSH
3.         POP
4.         EXIT
ENTER YOUR CHOICE : 1
ENTER THE FIRST ELEMENT : 10
10
  STACK
1.         CREATE
2.         PUSH
3.         POP
4.         EXIT
ENTER YOUR CHOICE: 2
ENTER THE NEXT ELEMENT: 30
10
30
STACK
1.         CREATE
2.         PUSH
3.         POP
4.         EXIT
ENTER YOUR CHOICE: 3
DELETED ELEMENT IS 30
STACK
1.         CREATE
2.         PUSH
3.         POP
4.         EXIT
ENTER YOUR CHOICE: 3
DELETED ELEMENT IS 10
STACK
1.         CREATE
2.         PUSH
3.         POP
4.         EXIT
ENTER YOUR CHOICE: 3
STACK IS EMPTY.