ساختمان داده Stack

فرق این Stack با قبلی در این هست که در قبلی برای شبیه سازی از آرایه استفاده شده ولی در این یکی از لیست پیوندی و همان طور که میدونید لیست های پیوندی علی رغم سرعت بالا از حافظه به نحو احسن استفاده می کنند.

#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
#include <process.h>
struct node
{
  char token;
  struct node *next;
};
//***************************************************************************
class stack   //create a stack
{
  struct node *start;
  public:
  stack(){start=NULL;} //this is a constructor

    void push(char token);
    char pop(void);
    int isempty(void);
    void show(void);
}s;
void stack::push(char token)
{
 struct node *temp;
 temp=start;
 if (temp==NULL){
   start=(struct node *)malloc(sizeof(node));
   start->token=token;
   start->next=NULL;
 }
 else{
  while(temp->next)
    temp=temp->next;
  temp->next=(struct node *)malloc(sizeof(node));
  temp->next->token=token;
  temp->next->next=NULL;
 }
}//end of stack::push
char stack::pop(void)
{
 struct node *temp;
 char token;
 temp=start;
 if (temp==NULL){cout<<"\nStack is empty\n";getch();return 0;}
 if (temp->next==NULL){
 token=temp->token;
 free (temp);
 start=NULL;
 return token;
 }
 while(temp->next->next)
    temp=temp->next;
 token=temp->next->token;
 free(temp->next);
 temp->next=NULL;
 return token;
} //end of stack::pop
int stack::isempty(void)
{
  if (start==NULL)
     return 1;//stack is empty
  else
     return 0;//stack is not empty
}//end of stack::isempty
void stack::show(void)
{
 struct node *temp;
 temp=start;
 cout<<"\n=============================================\n";
 if (temp==NULL){cout<<"stack is empty";getch();return;}
 while(temp){
   cout<<temp->token<<"   ";
   temp=temp->next;
 }//loop
 getch();
}//end of stack::show