一、链栈的定义
有两种方式实现栈，分别是顺序存储结构和链式存储结构，这里我们把通过链式存储结构实现的栈成为链栈，链栈相对于顺序栈其最大优势是可以动态地分配存储空间，所以通常不会出现栈满的情况，这里我们通过不带头结点的单链表实现链栈（是因为栈的主要操作都是在栈顶进行操作的），即第一个结点设为栈顶从而方便操作。
如下图，也就是一个不带头结点的单链表，即不带头结点的链栈，其中Lhead指针指向栈中的栈顶元素：
链栈的类型定义代码如下：
#include<stdio.h> #include<stdlib.h> typedef struct StackNode { int data;//存放栈中元素 struct StackNode *Lhead;//栈顶指针 ，记录栈顶元素的位置 } *LinkStack;//链栈的类型定义
二、链栈的初始化
初始化一个空栈，将链栈类型的变量S标识为空，即S=NULL，如下代码：
/*链栈的初始化，初始化一个空栈*/ bool InitStack(LinkStack &S) { S=NULL; return true; }
三、判断链栈是否为空栈
当链栈S为空时表示为空栈，否则不为空，通过if条件语句判断，即S==NULL，如下代码：
/*判断链栈是否为空*/ bool EmptyStack(LinkStack S){ if(S==NULL) return true; else return false; }
四、进栈（插入操作）
同单链表当中动态分配新结点的步骤类似，创建一个值为x的新结点p（通过malloc()函数动态分配，需在开头加头文件#include<stdlib.h>），首先将x值赋给新结点p的数据域中，然后将新结点p插入到链栈的栈顶前，最后再将新结点p作为当前栈顶元素，完整代码如下：
/*进栈（插入操作）*/ void PushStack(LinkStack &S, int x) { StackNode *p; p = (StackNode*)malloc(sizeof(StackNode));//动态分配创建一个新结点p p->data = x; //将x放入新结点p的数据域中 p->Lhead = S; //将新结点p插入到当前链栈的栈顶前 S = p; //将新结点p作为栈顶元素 }
五、出栈（删除操作）
出栈操作首先必须判断栈是否为空，即S==NULL，然后通过变量x，将栈顶元素S->data赋给x取出，然后将指针p指向原栈顶（为要删除的结点），并将栈顶S指向下一个结点，最后通过free()函数释放要删除的结点p，完整代码如下：
/*出栈（删除操作）*/ bool PopStack(LinkStack &S,int &x) { StackNode *p; if(S==NULL)//若栈为空，则报错 return false; x=S->data;//x记录当前栈顶元素 p=S;//p指针指向原栈顶 S=S->Lhead;//S指向下一个结点 free(p);//释放栈顶元素 return true; }
六、读取链栈的栈顶元素
通过变量x使其存储栈顶结点，即S->data，读取链栈的栈顶元素的代码如下：
/*读取链栈的栈顶元素*/ bool GetTopStack(LinkStack &S,int &x) { if(S==NULL) return false; x=S->data; return true; }
七、链栈的建立
链栈的建立通过输入要建立的栈的元素个数来一键建立链栈，每次输入入栈的元素，然后通过PushStack()函数使其入栈，代码如下：
/*链栈的建立*/ void CreateStack(LinkStack &S,int x) { int number; printf("请输入要建立的栈中的元素个数：\n"); scanf("%d",&number); for(int i=0; i<number; i++) { printf("输入第%d个入栈的元素：\n",i+1); scanf("%d",&x); PushStack(S,x); } }
八、链栈的遍历输出
链栈的遍历输出也就是遍历链栈，使p指针等于S，然后每次指向下一个结点，同时输入此时指针p指向结点的值p->data，代码如下：
/*链栈的遍历输出*/ bool PrintStack(LinkStack S) { StackNode *p=S; if(p==NULL) return false; while(p!=NULL) { printf("%d ",p->data); p=p->Lhead; } }
链式存储结构实现栈完整代码
链式存储结构实现栈的完整代码如下：
#include<stdio.h> #include<stdlib.h> typedef struct StackNode { int data;//存放栈中元素 struct StackNode *Lhead;//栈顶指针 ，记录栈顶元素的位置 } *LinkStack;//链栈的类型定义 /*链栈的初始化，初始化一个空栈*/ bool InitStack(LinkStack &S) { S=NULL; return true; } /*判断链栈是否为空*/ bool EmptyStack(LinkStack S) { if(S==NULL) return true; else return false; } /*进栈（插入操作）*/ void PushStack(LinkStack &S, int x) { StackNode *p; p = (StackNode*)malloc(sizeof(StackNode));//动态分配创建一个新结点p p->data = x; //将x放入新结点p的数据域中 p->Lhead = S; //将新结点p插入到当前链栈的栈顶前 S = p; //将新结点p作为栈顶元素 } /*出栈（删除操作）*/ bool PopStack(LinkStack &S,int &x) { StackNode *p; if(S==NULL)//若栈为空，则报错 return false; x=S->data;//x记录当前栈顶元素 p=S;//p指针指向原栈顶 S=S->Lhead;//S指向下一个结点 free(p);//释放栈顶元素 return true; } /*读取链栈的栈顶元素*/ bool GetTopStack(LinkStack &S,int &x) { if(S==NULL) return false; x=S->data; return true; } /*链栈的建立*/ void CreateStack(LinkStack &S,int x) { int number; printf("请输入要建立的栈中的元素个数：\n"); scanf("%d",&number); for(int i=0; i<number; i++) { printf("输入第%d个入栈的元素：\n",i+1); scanf("%d",&x); PushStack(S,x); } } /*链栈的遍历输出*/ bool PrintStack(LinkStack S) { StackNode *p=S; if(p==NULL) return false; while(p!=NULL) { printf("%d ",p->data); p=p->Lhead; } }
一个简单的链栈的基本实现例子
例如，通过链式存储结构创建一个栈，其元素个数为4，为{2，7，0，-3}，创建后依次输出从栈顶到栈底的元素值，首先通过输入一个元素，使其进栈，然后读取当前栈顶元素；执行一次出栈操作。然后读取当前栈顶元素，最后再依次输出从栈顶到栈底的元素值，如下代码：
#include<stdio.h> #include<stdlib.h> typedef struct StackNode { int data;//存放栈中元素 struct StackNode *Lhead;//栈顶指针 ，记录栈顶元素的位置 } *LinkStack;//链栈的类型定义 /*链栈的初始化，初始化一个空栈*/ bool InitStack(LinkStack &S) { S=NULL; return true; } /*判断链栈是否为空*/ bool EmptyStack(LinkStack S) { if(S==NULL) return true; else return false; } /*进栈（插入操作）*/ void PushStack(LinkStack &S, int x) { StackNode *p; p = (StackNode*)malloc(sizeof(StackNode));//动态分配创建一个新结点p p->data = x; //将x放入新结点p的数据域中 p->Lhead = S; //将新结点p插入到当前链栈的栈顶前 S = p; //将新结点p作为栈顶元素 } /*出栈（删除操作）*/ bool PopStack(LinkStack &S,int &x) { StackNode *p; if(S==NULL)//若栈为空，则报错 return false; x=S->data;//x记录当前栈顶元素 p=S;//p指针指向原栈顶 S=S->Lhead;//S指向下一个结点 free(p);//释放栈顶元素 return true; } /*读取链栈的栈顶元素*/ bool GetTopStack(LinkStack &S,int &x) { if(S==NULL) return false; x=S->data; return true; } /*链栈的建立*/ void CreateStack(LinkStack &S,int x) { int number; printf("请输入要建立的栈中的元素个数：\n"); scanf("%d",&number); for(int i=0; i<number; i++) { printf("输入第%d个入栈的元素：\n",i+1); scanf("%d",&x); PushStack(S,x); } } /*链栈的遍历输出*/ bool PrintStack(LinkStack S) { StackNode *p=S; if(p==NULL) return false; while(p!=NULL) { printf("%d ",p->data); p=p->Lhead; } } /*主函数*/ int main() { LinkStack S; int x,e; InitStack(S);//初始化 CreateStack(S,x);//创建一个链栈 GetTopStack(S,x);//读取栈顶元素 printf("读取栈顶元素,当前栈顶元素为：%d\n",x); printf("创建的链栈元素从栈顶到栈底依次为：\n"); PrintStack(S); printf("\n"); printf("输入一个要进栈的元素：\n"); scanf("%d",&e); PushStack(S,e);//进栈 GetTopStack(S,x); printf("读取栈顶元素,当前栈顶元素为：%d\n",x); PopStack(S,x);//出栈 GetTopStack(S,x); printf("执行一次出栈操作后,当前栈顶元素为：%d\n",x); printf("此时链栈元素从栈顶到栈底依次为：\n"); PrintStack(S); }
运行结果如下：
