#include<iostream>
#include<cstdlib>

#include<iostream>
#include<cstdlib>
#define LEN sizeof(struct Node)
using namespace std;

//我发现,插入操作时,总是先把New与已有节点连接 

using namespace std;
int *Array=NULL; 
int Count=0;

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Position;

#include<iostream>
#include<cstdlib>
#define LEN sizeof(struct Node)
using namespace std;

void Initial(int Size); //初始化栈
void Push(int Element); //入栈 
int GetStackLenth(void);//获取栈的个数 
void GetTopOfStack(void);//栈顶元素 
void Pop(void);          //出栈 
void Traverse(void);     //遍历 
void Destory(void);      //释放栈的内存 

struct Node         //节点 
{
int Element ;
struct Node *Next;
};

typedef struct Node *PtrToNode;
typedef PtrToNode Position;

int main()   ///测试 
{
int a[8]={15,65,13,81,26,34,88,55};
int Choose;
Initial(100);   //栈的初始化:开辟 
for(int i=0;i<8;i++)
   Push(a[i]);  //数组的数依次入栈 
Traverse();   //栈的遍历:从栈顶到栈尾依次输出 
cout <<endl <<“请输入你的选择:n1.出栈 2.结束”
<<endl ;
while(1)
{
cin >>Choose ;
switch(Choose)
{
case 1:
Pop();                          break;
case 2:
                               break;
default :
cout <<“输入选项有误!” <<endl ; break ;
}
if(Choose==2) break;
}
Traverse();   //发生变化后重新遍历,比对以前的栈
Destory();    //用完就释放内存 
return 0;
}

int IsEmpty(Position Top);  //检验空栈 
void GetStackTop(Position Top); //获取栈顶元素 
Position Create(void);  //创建一个栈 
void Traverse(Position Top); //遍历 
void Push(Position Top);  //出栈 
void Pop(Position Top);   //入栈 

struct Node
{
int Element;
struct Node *Last;
struct Node *Next;
};

void Initial(int Size)
{
Array=(int *)malloc(sizeof(int)*Size);  //Size是栈的容纳个数 
if(Array==NULL)
   cout <<“空间不足! ” <<endl ; 
}

int main()  //测试 
{
Position Top=Create();
Traverse(Top);
Push(Top);
return 0;
}

Position Create(void);           //创建双向循环链表 
void Traverse(Position Head);    //正序遍历/n反序遍历 
void Insert(Position Head);      //插入一个元素 
void Delete(Position Head);      //删除一个元素 
int GetListLenth(Position Head); //用于插入 

void Push(int Element)  //入栈 
{
Array[Count++]=Element; 
}

int IsEmpty(Position Top) 
{
return Top->Next==NULL;  
}

int main()  //测试 
{
Position Head;
Head=Create();
Traverse(Head);
Insert(Head);
Delete(Head);
return 0;
}

int GetStackLenth(void)  //获得栈的个数 
{
return Count ;
}

Position Create(void)
{
int i,a[8]={15,16,21,9,54,66,24,59}; //创建一个8个元素的栈 
Position Top=NULL;
Top=(struct Node *)malloc(LEN);
Top->Next=NULL;
Top->Element=0;
for(i=0;i<8;i++)
{

Position Create(void)  //创建 
{
int a[6]={11,41,18,49,35,66},i;
Position Head=NULL;
    Position New=NULL,Tail=NULL;
    Head=(struct Node *)malloc(LEN);
    if(Head==NULL)
        cout <<“空间不足!” <<endl ;
    Head->Next=Head;
    Head->Last=Head;
    Head->Element=0;
    Tail=Head;
    for(i=0;i<6;i++)
    {
    New=(struct Node *)malloc(LEN);
    if(New==NULL)
       cout <<“空间不足!” <<endl ;
    New->Element=a[i];     //赋值 
    New->Last=Tail;        //先把New与已有的节点连接 
    New->Next=Head;
    Tail->Next=New;        //把原来的尾节点与New连接 
    Head->Last=New;        //把Head的Last与New连接 
    Tail=New;              //现在,New是新的Tail,在末尾插入完毕 
   
}
return Head;
}

void GetTopOfStack(void) //获得栈顶元素 
{
if(GetStackLenth()==0)
   cout <<“空栈 ” <<endl ;
else 
   cout <<“栈顶元素为 ” <<Array[Count-1] ; 
}

Position New=(struct Node *)malloc(LEN);
   if(New==NULL)
       cout <<“空间不足” <<endl ;
   New->Element=a[i];  //赋值 
   New->Next=Top;      //New与原先的栈顶连接 
   Top=New;            //New成为新的栈顶 
}
return Top;  
}

void Traverse(Position Head)
 //遍历,这里的Head_L用来遍历,而不一直是头指针 
{
Position Head_L=Head->Next;  //从这开始,正序遍历总是指向Next 
while(Head_L!=Head)
{
cout <<Head_L->Element <<‘ ‘ ;
Head_L=Head_L->Next;
}
cout <<“正序遍历完毕” <<endl ;
Head_L=Head->Last;          //从这开始,反序遍历总是指向Last 
while(Head_L!=Head)
{
cout <<Head_L->Element <<‘ ‘ ;
Head_L=Head_L->Last;
}
cout <<“反序遍历完毕” <<endl ; 
}

void Pop(void)  //出栈 
{
if(GetStackLenth()==0)
   cout <<“空栈!无法进行出栈操作 ” <<endl ;
else
   Array[Count–]=0 ;
}

void Traverse(Position Top)
{
if(IsEmpty(Top))
   cout <<“空栈!” <<endl ;
else 
{
GetStackTop(Top);
   while(Top->Next!=NULL)  //栈底连接的是NULL 
       {
       cout << Top->Element <<‘ ‘;
       Top=Top->Next;
       }
   cout <<“遍历完毕” <<endl ;
}
}

void Insert(Position Head)   //插入
{
int X,SubLabel;
Position New=NULL;
Position Head_L=Head->Next;
cout <<“请输入你要插入的元素值:” ;
cin >>X ;
cout <<“请输入你要插到的序号:” ;
cin >>SubLabel ;

void Traverse(void) //遍历 
{
int Lenth=GetStackLenth();
if(Lenth==0)
   cout <<“空栈! ” <<endl ;
else 
   while(Lenth–)
       cout <<Array[Lenth] <<‘ ‘ ;
   cout <<endl <<“遍历完毕 ” ;
GetTopOfStack();
}

void GetStackTop(Position Top)
{
if(IsEmpty(Top))
   cout <<“空栈!” <<endl ;
else
cout <<“栈顶元素是:” <<Top->Element <<endl ;
}

if(SubLabel>0&&SubLabel<=GetListLenth(Head))
{
while(SubLabel-1)   //找到链表要插入的位置 
       {
        Head_L=Head_L->Next;
        SubLabel–;
       }
   New=(struct Node *)malloc(LEN);
   if(New==NULL)
       cout <<“空间不足!” <<endl ;
   New->Element=X;    //赋值 
   New->Last=Head_L->Last;  //先把New与已有节点连接 
   New->Next=Head_L;
   Head_L->Last->Next=New;
 //趁着还有着Head_L的上一个节点位置,及早把它与New连接 
   Head_L->Last=New;        //最后把New与Head_L连接 
   Traverse(Head);  
}
else cout <<“输入的序号有误!” <<endl ;
}

void Destory(void)
{
delete Array;
}

void Push(Position Top)
{
int X;
Position New=NULL;
cout <<“请输入要入栈的元素:” ; 
cin >>X ;
New=(struct Node *)malloc(LEN);
if(New==NULL)
   cout <<“空间不足!” <<endl ;
New->Element=X;     //跟创建的时候的插入是一样的 
New->Next=Top;
Top=New;
cout <<“入栈后:” ;
Traverse(Top);
}

void Delete(Position Head)
{
int SubLabel;
Position Head_L=Head->Next;
cout <<“请输入要删除元素对应的序号:” ;
cin >>SubLabel ;

void Pop(Position Top) //出栈 
{
int X;
Position Deletion=NULL;
if(IsEmpty(Top))
   cout <<“空栈!” <<endl ;
else
{
cout <<“出栈后: ” ;
Top=Top->Next;   //栈顶的下面一个元素变成栈顶 
Traverse(Top);
}
}

if(SubLabel>0&&SubLabel<=GetListLenth(Head))
{
while(SubLabel-1) //找到要删除的位置 
{
Head_L=Head_L->Next;
SubLabel–;
}
Head_L->Last->Next=Head_L->Next;
//把要删除的位置Head_L的前一个位置与Head_L的下一个位置连接起来 
Head_L->Next->Last=Head_L->Last; //建议画个图,很清晰 
delete Head_L;  //释放 
Traverse(Head);
}
else cout <<“输入的序号有误!” <<endl ;
}

int GetListLenth(Position Head)
 //获得元素个数,这与单链表,循环链表的想法是一样的 
{
int Lenth=0;
Position Head_L=Head->Next;
while(Head_L!=Head)
{
Lenth++;
Head_L=Head_L->Next;
}
return Lenth;
}