One disadvantage of using an array to implement a stack is the wasted space-most of the time most of the array is unused. A more elegant and economical implementation of a stack uses a linked list, which is a data structure that links together individual data objects as if they were ``links'' in a ``chain'' of data.
//stack using linked list
#include<stdio.h>
#include<iostream.h>
#include<conio.h>
template<class T>
class stack;//forward declaration, bcoa wea re usig stack class in node class
template<class T>
class node
{
T data; //data field contains int value
node<T> *link;//link field contain address of a node(next node)
friend class stack<T>;//we can access data and linke from the next class stack
};
template<class T>
class stack
{
private:
node<T> *top;//top is a reference(pointer) to a node(topmost node)
public:
stack();
~stack();
int isempty();
void push(T x);
T pop() ;
T topmost();
void display();
};
template <class T>
stack<T>::stack()
{
top=NULL; //top points to first
}
template<class T>
int stack<T>::isempty()
{
return(top==NULL);//return true when stack is empty and false otherwise
}
template<class T>
void stack<T>:: display()
{
node<T> *p;;//p is a pointer of type node
if(isempty())
cout<<"Stack is empty\n";
else
{
cout<<"stack is as follows\n";
//disp each node of stack until stack is exasted
for(p=top;p!=NULL;p=p->link)
{
//display data and linke fields of each node
cout<<p->data<<"\t"<<p->link<<endl;
}
}
}//end display()
template<class T>
void stack<T>::push(T x)
{
node<T> *p;
p=new node<T>;//create a node, p is pointer to it
p->data=x;//store x in new node data field
p->link=top;//attach new node p and top most node
top=p;//change top pointer to new node
}
template<class T>
T stack<T>:: pop()
{
T x;
node<T> *p;
if(isempty())//if stack is empty, deletion is not possble
return(-1);
p=top;//p points to top most node
top=top->link;//move top to next ode so that top most node is logically delted
x=p->data;//copy top nost node data to x
delete p;//delate top most node physically
return(x);//data of the deleted node
}
template<class T>
int stack<T>::topmost()
{
if(isempty())//if stack is empty return-1
return(-1);
else
return(top->data);//data of the top most node
}
template<class T>
stack<T>:: ~stack()
{
node <T> *p;
while(!isempty())//execute loop until stack is empty
{
p=top;
top=top->link;
delete p;
//pop();//instead of the 2 statements
}
}
void menu()
{
cout<<"1.insertion\n";
cout<<"2.deletion\n";
cout<<"3.display\n";
cout<<"4.topmost value of the stack\n";
cout<<"5.exit\n";
}
void main()
{
stack <int>a;
int ch,x;
menu();
cout<<"enter ur choice\n";
cin>>ch;
while(ch<5)
{
switch(ch)
{
case 1:{
cout<<"enter value to be inserted\n";
cin>>x;
if(x==-1)
cout<<"invalid\n";
else
a.push(x);
break;
}
case 2: {
x=a.pop();//delete top most node frm the stack
if(x==-1)
cout<<"stack is empty, del. is not possble\n";
else
cout<<"deleted value is "<<x<<endl;
break;
}
case 3: {
a.display();//display stack in the reverse order
break;
}
case 4:{
x=a.topmost();
if(x==-1)
cout<<"stack is emtpy\n";
else
cout<<"top most value is "<<x<<endl;
break;
}
}//switch
menu();
cout<<"enter ur choice\n";
cin>>ch;
}
cout<<"enter your choice\n";
}
/*
E:\rajendra\java\ds>javac Linked.java
E:\rajendra\java\ds>java Linked
1.insertion
2. deletion
3.display
4.topmost value of the stack
5.exit
1
enter value to be inserted
10
1.insertion
2. deletion
3.display
4.topmost value of the stack
5.exit
enter ur choice
1
enter value to be inserted
20
1.insertion
2. deletion
3.display
4.topmost value of the stack
5.exit
enter ur choice
1
enter value to be inserted
30
1.insertion
2. deletion
3.display
4.topmost value of the stack
5.exit
enter ur choice
1
enter value to be inserted
40
1.insertion
2. deletion
3.display
4.topmost value of the stack
5.exit
enter ur choice
3
stack is as follows
40 node@1b90b39
30 node@18fe7c3
20 node@b8df17
10 NULL
1.insertion
2. deletion
3.display
4.topmost value of the stack
5.exit
enter ur choice
5
enter your choice
E:\rajendra\java\ds>
*/
//stack using linked list
#include<stdio.h>
#include<iostream.h>
#include<conio.h>
template<class T>
class stack;//forward declaration, bcoa wea re usig stack class in node class
template<class T>
class node
{
T data; //data field contains int value
node<T> *link;//link field contain address of a node(next node)
friend class stack<T>;//we can access data and linke from the next class stack
};
template<class T>
class stack
{
private:
node<T> *top;//top is a reference(pointer) to a node(topmost node)
public:
stack();
~stack();
int isempty();
void push(T x);
T pop() ;
T topmost();
void display();
};
template <class T>
stack<T>::stack()
{
top=NULL; //top points to first
}
template<class T>
int stack<T>::isempty()
{
return(top==NULL);//return true when stack is empty and false otherwise
}
template<class T>
void stack<T>:: display()
{
node<T> *p;;//p is a pointer of type node
if(isempty())
cout<<"Stack is empty\n";
else
{
cout<<"stack is as follows\n";
//disp each node of stack until stack is exasted
for(p=top;p!=NULL;p=p->link)
{
//display data and linke fields of each node
cout<<p->data<<"\t"<<p->link<<endl;
}
}
}//end display()
template<class T>
void stack<T>::push(T x)
{
node<T> *p;
p=new node<T>;//create a node, p is pointer to it
p->data=x;//store x in new node data field
p->link=top;//attach new node p and top most node
top=p;//change top pointer to new node
}
template<class T>
T stack<T>:: pop()
{
T x;
node<T> *p;
if(isempty())//if stack is empty, deletion is not possble
return(-1);
p=top;//p points to top most node
top=top->link;//move top to next ode so that top most node is logically delted
x=p->data;//copy top nost node data to x
delete p;//delate top most node physically
return(x);//data of the deleted node
}
template<class T>
int stack<T>::topmost()
{
if(isempty())//if stack is empty return-1
return(-1);
else
return(top->data);//data of the top most node
}
template<class T>
stack<T>:: ~stack()
{
node <T> *p;
while(!isempty())//execute loop until stack is empty
{
p=top;
top=top->link;
delete p;
//pop();//instead of the 2 statements
}
}
void menu()
{
cout<<"1.insertion\n";
cout<<"2.deletion\n";
cout<<"3.display\n";
cout<<"4.topmost value of the stack\n";
cout<<"5.exit\n";
}
void main()
{
stack <int>a;
int ch,x;
menu();
cout<<"enter ur choice\n";
cin>>ch;
while(ch<5)
{
switch(ch)
{
case 1:{
cout<<"enter value to be inserted\n";
cin>>x;
if(x==-1)
cout<<"invalid\n";
else
a.push(x);
break;
}
case 2: {
x=a.pop();//delete top most node frm the stack
if(x==-1)
cout<<"stack is empty, del. is not possble\n";
else
cout<<"deleted value is "<<x<<endl;
break;
}
case 3: {
a.display();//display stack in the reverse order
break;
}
case 4:{
x=a.topmost();
if(x==-1)
cout<<"stack is emtpy\n";
else
cout<<"top most value is "<<x<<endl;
break;
}
}//switch
menu();
cout<<"enter ur choice\n";
cin>>ch;
}
cout<<"enter your choice\n";
}
/*
E:\rajendra\java\ds>javac Linked.java
E:\rajendra\java\ds>java Linked
1.insertion
2. deletion
3.display
4.topmost value of the stack
5.exit
1
enter value to be inserted
10
1.insertion
2. deletion
3.display
4.topmost value of the stack
5.exit
enter ur choice
1
enter value to be inserted
20
1.insertion
2. deletion
3.display
4.topmost value of the stack
5.exit
enter ur choice
1
enter value to be inserted
30
1.insertion
2. deletion
3.display
4.topmost value of the stack
5.exit
enter ur choice
1
enter value to be inserted
40
1.insertion
2. deletion
3.display
4.topmost value of the stack
5.exit
enter ur choice
3
stack is as follows
40 node@1b90b39
30 node@18fe7c3
20 node@b8df17
10 NULL
1.insertion
2. deletion
3.display
4.topmost value of the stack
5.exit
enter ur choice
5
enter your choice
E:\rajendra\java\ds>
*/
