目录
前言
一.链栈的定义
二、链栈的c++语言结构描述表示
三、链栈中基本操作的实现
3.1链栈的初始化
3.2判断链栈是否为空
3.3求链栈的长度
3.4 链栈的入栈
3.4 链栈的出栈
3.5求栈顶元素
3.6销毁栈
四.链栈的具体实现
五.测试结果
六、总结
前言
本文参考王卓老师的数据结构视频和严蔚敏老师的《数据结构》
一.链栈的定义
栈：操作受限的线性表，限定仅在表尾进行插入和删除操作的线性表，即后进先出。这一端被称为栈顶，相对地，把另一端称为栈底。
链栈：用链式结构存储的栈（我实际用的是不带头结点的单链表）
例子：类似子弹压入弹夹，后放入的子弹可以先从弹夹弹出来。
二、链栈的c++语言结构描述表示
代码如下（示例）：
注意：我使用的是不带头节点的单链表
typedef struct LinkNode{
int data;//数据域
struct LinkNode *next;//指针域
}stackNode,*LinkStack;
三、链栈中基本操作的实现
3.1链栈的初始化
无需new，因为我是不带头结点的单链表
void initStack(LinkStack &s){s=NULL;//不需要头节点 }3.2判断链栈是否为空
当s==NULL时，栈为空，则返回1；否则，返回0
int stackEmpty(LinkStack s){if(s==NULL)return 1;return 0;}3.3求链栈的长度
长度表示有多少个节点
int stackLength(LinkStack s){int sum=0;stackNode *temp=s;while(temp!=NULL){sum++;temp=temp->next;}return sum;}3.4 链栈的入栈
p是新节点
关键处在于当栈为空的时候，p就是第一个节点；而当栈不为空时，则让p的next指针指向s，而s更新到p节点，相当于还是让p作为第一个节点
void push(LinkStack &s,int e){stackNode *p=new stackNode;p->data=e;p->next=NULL;if(s==NULL)s=p;else{p->next=s;s=p;}}3.4 链栈的出栈
当栈为空的时候，是无法弹出的
new一个p节点
而当栈不空时，则让p指向s的第一个节点，更新s，使s指向下一个节点，在删掉p
void pop(LinkStack &s,int &e){stackNode *p=new stackNode;if(s==NULL){cout<<"栈为空，无法弹出"<<endl;}else{p=s;e=p->data;s=s->next;delete p;cout<<"成功弹出栈顶元素"<<endl;}}3.5求栈顶元素
当栈不空时，返回第一个节点的数据
int top(LinkStack s){if(s==NULL)return -1;return s->data;}3.6销毁栈
void DestoryStack(LinkStack &S){stackNode *p;while(S){p=S;S=S->next;delete p;}S=NULL;cout<<"成功销毁"<<endl;}四.链栈的具体实现
#include <iostream>using namespace std;//不带头节点的 typedef struct LinkNode{int data;//数据域struct LinkNode *next;//指针域 }stackNode,*LinkStack;void initStack(LinkStack &s){s=NULL;//不需要头节点 }int stackEmpty(LinkStack s){if(s==NULL)return 1;return 0;}int stackLength(LinkStack s){int sum=0;stackNode *temp=s;while(temp!=NULL){sum++;temp=temp->next;}return sum;}void push(LinkStack &s,int e){stackNode *p=new stackNode;p->data=e;p->next=NULL;if(s==NULL)s=p;else{p->next=s;s=p;}}void pop(LinkStack &s,int &e){stackNode *p=new stackNode;if(s==NULL){cout<<"栈为空，无法弹出"<<endl;}else{p=s;e=p->data;s=s->next;delete p;cout<<"成功弹出栈顶元素"<<endl;}}int top(LinkStack s){if(s==NULL)return -1;return s->data;}//销毁栈 //所有节点void DestoryStack(LinkStack &S){stackNode *p;while(S){p=S;S=S->next;delete p;}S=NULL;cout<<"成功销毁"<<endl;}void menu(){cout<<"**************************"<<endl;cout<<"1.初始化"<<endl;cout<<"2.判断栈是否为空"<<endl;cout<<"3.求栈的长度"<<endl;cout<<"4.销毁栈"<<endl;cout<<"5.入栈"<<endl;cout<<"6.出栈"<<endl;cout<<"7.求栈顶元素"<<endl;cout<<"8.退出"<<endl;cout<<"**************************"<<endl;}int main(){int choice;LinkStack s;int e1,e2;while(1){menu();cin>>choice;switch(choice){case 1:initStack(s);cout<<"初始化成功"<<endl;break;case 2:if(stackEmpty(s))cout<<"栈为空"<<endl;elsecout<<"栈不为空"<<endl; break;case 3:cout<<"栈的长度为"<<stackLength(s)<<endl;break;case 4:DestoryStack(s);break;case 5:cout<<"请输入想要入栈的元素值："<<endl;cin>>e1;push(s,e1);cout<<"入栈成功"<<endl; break;case 6:pop(s,e2);cout<<"弹出的元素为"<<e2<<endl;break;case 7:if(top(s)!=-1)cout<<"栈顶元素为"<<top(s)<<endl;elsecout<<"栈为空"<<endl;break;case 8:cout<<"成功退出"<<endl;exit(0);default:cout<<"输入有误，请重新输入"<<endl;break;}}}五.测试结果
图一
图二
图三
图四
图五
图六
图七
六、总结
栈是一种操作受限的线性表，虽然操作受限，但是与线性表有点类似，只不过栈的插入和删除都在表尾而已。我实现的链栈其实与不带头节点的链表有很大关系，各位也可以参考下链表来学习链栈。
