stack using Linked List in c++

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>

Stacks using Linked list in java

*/