C++ Program to Stack ADT Implementation Using Linked List

Stack ADT- Linked list Implementation

AIM:

• To Write a C++ Program to Stack ADT implementation using linked list.

Algorithm :
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).

Program:
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
//using namespace std;
class node
{
public:
class node *next;
int data;
};
class stack : public node
{
node *head;
int tos;
public:
stack()
{
tos=-1;
}
void push(int x)
{
if (tos < 0 )
{
head =new node;
head->next=NULL;
head->data=x;
tos ++;
}
else
{
node *temp,*temp1;
temp=head;
if(tos >= 4)
{
cout <<"stack over flow";
return;
}
tos++;
while(temp->next != NULL)
temp=temp->next;
temp1=new node;
temp->next=temp1;
temp1->next=NULL;
temp1->data=x;
}
}
void display()
{
node *temp;
temp=head;
if (tos < 0)
{
cout <<" stack under flow";
return;
}
while(temp != NULL)
{
cout <<temp->data<< " ";
temp=temp->next;
}
}
void pop()
{
node *temp;
temp=head;
if( tos < 0 )
{
cout <<"stack under flow";
return;
}
tos--;
while(temp->next->next!=NULL)
{
temp=temp->next;
}
temp->next=NULL;
}
};
main()
{
Clrscr();
stack s1;
int ch;
while(1)
{
cout <<"\n1.PUSH\n2.POP\n3.DISPLAY\n4.EXIT\n Enter ur choice:";
cin >> ch;
switch(ch)
{
case 1: cout <<"\n enter a element";
cin >> ch;
s1.push(ch);
break;
case 2: s1.pop();break;
case 3: s1.display();
break;
case 4: exit(0);
}
}
return (0);
}

Output:
1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:1
enter a element23
1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:1
enter a element67
1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:3
23 67
1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:2
1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:3
23
1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:2
1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:2
stack under flow
1.PUSH 2.POP 3.DISPLAY 4.EXIT
enter ru choice:4

Result:

• Thus, the stack ADT- linked list implementation program has been written and executed successfully.