栈的链式储存结构称为链栈。链栈的节点类型与链式线性表的节点类型
定义相同，不同的是它是仅在表头进行操作的单链表。链栈通常用不带头节
点的单链表来实现，栈顶指针就是链表的头指针 ，如图所示：
代码如下：
#include <stdio.h>
#include <stdlib.h> #define OK 1
#define ERROR 0
typedef int SElemType;
//栈的链式储存结构
typedef struct SNode {
SElemType data; //数据域
struct SNode *next; //指针域 }SNODE, *PSNODE;
//栈顶节点
typedef struct
{
PSNODE top; //栈顶指针
int count; //栈的长度 }LinkStack; //初始化栈顶节点
int Init_LS(LinkStack *s) {
s->top = (PSNODE)malloc(sizeof(SNODE));
if (!s->top)
return ERROR; s->top = NULL;
s->count = ;
return OK;
}
//判断栈是否为空
int Is_Empty(LinkStack *s) {
if (s->top == NULL)
{
printf("栈为空\n");
return OK;
} else {
printf("栈不为空\n");
return ERROR;
}
}
//遍历栈
int Traverse_LS(LinkStack *s) {
int i;
if (Is_Empty(s) == OK) return ERROR;
PSNODE p = s->top;
for(i=s->count;i>;i--)
{ printf("%d ", p->data);
p = p->next;
}
printf("\n");
return OK;
}
//链栈元素入栈
int Push_LS(LinkStack *s, SElemType e) { PSNODE p = (PSNODE)malloc(sizeof(SNODE));
if (!p) return ERROR;
p->data = e;
p->next = s->top; //新结点指向栈顶指针指向的地址
s->top = p; //更新栈顶指针
s->count++; // 节点增加1 return OK; }
// 获取栈顶元素
int GetTop(LinkStack *s, SElemType *e) {
if (Is_Empty(s) == OK) return ERROR;
*e = s->top->data;
return OK;
}
//链栈元素出栈
int Pop_LS(LinkStack *s, SElemType *e) {
if (Is_Empty(s) == OK) return ERROR; PSNODE temp = s->top;
*e = temp->data;
s->top = temp->next;
s->count--;
free(temp);
return OK;
}
//销毁栈
int Destroy_LS(LinkStack *s) {
PSNODE p,q=NULL;
if(Is_Empty(s)==OK) return ERROR;
p = s->top;
for (int i = s->count; i > ; i--)
{
q = p->next;
free(p);
p = q;
}
s->count = ;
return OK;
} int main() {
LinkStack s,*ps;
SElemType a, *e;
e = (SElemType*)malloc(sizeof(SElemType));
ps = &s;
Init_LS(ps);
int n;
Is_Empty(ps);
printf("请输入入栈元素的个数:");
scanf("%d", &n);
for(int i=;i<n;i++)
{
scanf("%d", &a);
Push_LS(ps, a);
}
Traverse_LS(ps);
Pop_LS(ps, e);
printf("弹出的元素为%d\n", *e);
Traverse_LS(ps);
GetTop(ps, e);
printf("栈顶元素为%d\n", *e);
if(Destroy_LS(ps)==OK) printf("栈销毁成功！"); return ;
}
我写的这个链栈的代码 稍微修改了一点 --把栈顶指针与count 组成一个结构体
count用来储存链栈的长度。如果链栈的长度很长而且经常需要返回长度 一个一个
算的话显得特别费时间；而使用count要方便的多 。
如果我们要把两个链栈合并，必然需要其中一个的栈底地址
而且如果这个链栈很大，我们要从栈顶开始寻找栈底地址 很麻烦吧
但是我们在LinkStack 中增加一个 PSNODE bottom指针，在入栈函数中
根据count来给bottom赋值。这样栈底地址就有了。
所以，数据结构的一些细节上的东西不是一成不变的，而是可以根据具体
的问题修改。