链栈的好处就是，不用考虑栈满的情况了
链栈需要用头插法的方式，来入栈，因为如果使用尾插法的话，进栈好进，但是出栈的时候，就有问题了，栈顶指针下不去了，我想了一下，也可以采用循环双链表的方式，但是头插法足够了
分析：
链栈结构体：
typedef struct linkstack{//链栈节点
struct Node *n;
struct linkstack *next;
};
链栈的长度：
定义一个全局变量sum=0；进栈+1，出栈-1，sum就是链栈的长度
int get_size(){ //栈中元素的个数
return sum;
}
判断链栈是否为空：
bool empty_stack(linkstack *&l){ //判断栈是否为空
if(sum==0){
return true;
}else{
return false;
}
}
得到栈顶元素：
Node* get_top(linkstack *&l){ //得到栈顶元素
return l->n;
}
进栈：（头插法）
void push_linkstack(linkstack *&l,Node *&n){//n节点进入栈，采用头插法
linkstack *s=new linkstack;
s->n=n;
s->next=l;
l=s;
sum++;
}
出栈：
Node* pop_stack(linkstack *&l){ //出栈
if(l->next==NULL){
return NULL;
}
Node *s=l->n;
linkstack *p=l;
linkstack *s1=l->next;
l=s1;
sum--;
delete p;
return s;
}
代码：
#include <iostream>
using namespace std;
typedef struct Node{
int data;
struct Node *next;
};
typedef struct linkstack{//链栈节点
struct Node *n;
struct linkstack *next;
};
int sum=0;
void Init_linkstack(linkstack *&l){
linkstack *s=new linkstack;
s->next=NULL; //定义头结点
}
void push_linkstack(linkstack *&l,Node *&n){//n节点进入栈，采用头插法
linkstack *s=new linkstack;
s->n=n;
s->next=l;
l=s;
sum++;
}
int get_size(){ //栈中元素的个数
return sum;
}
Node* get_top(linkstack *&l){ //得到栈顶元素
return l->n;
}
bool empty_stack(linkstack *&l){ //判断栈是否为空
if(sum==0){
return true;
}else{
return false;
}
}
Node* pop_stack(linkstack *&l){ //出栈
if(l->next==NULL){
return NULL;
}
Node *s=l->n;
linkstack *p=l;
linkstack *s1=l->next;
l=s1;
sum--;
delete p;
return s;
}
void create_Node(Node *&p){
Node *l=p,*s;
l->next=NULL;//定义头结点
int m;
while(1){
cin>>m;
if(m==-1){
break;
}
s=new Node;
s->data=m;
l->next=s;
l=s;
}
l->next=NULL;
}
int main()
{
Node *p=new Node;
cout<<"创建测试链表，输入-1结束："<<endl;
//创建测试数据链表
create_Node(p);
linkstack *ls=new linkstack;
cout<<"初始化链栈"<<endl;
Init_linkstack(ls);
Node *s=p->next;
cout<<"进入链栈："<<endl;
while(s!=NULL){
cout<<s->data<<" ";
push_linkstack(ls,s);
s=s->next;
}
cout<<endl;
cout<<"链栈长度："<<get_size()<<endl;
cout<<"栈顶元素："<<get_top(ls)->data<<endl;
cout<<"数据出栈："<<endl;
while(!empty_stack(ls)){
Node *p1=pop_stack(ls);
cout<<p1->data<<" ";
}
cout<<endl;
cout<<"链栈长度："<<get_size()<<endl;
return 0;
}
结果截图：
