该系列文章主要作数据结构（C语言版）学习的笔记。里面代码的注释很详细，同时提供给大家参考，欢迎指正和指教。
栈的链式存储结构
栈的链式存储结构，简称为链栈。
栈因为只是栈顶来做插入和删除操作，所以比较好的方法是将栈顶放在单链表的头部，栈顶指针和单链表的指针合二为一。
栈的链式存储结构
栈的链式存储结构代码实现
typedef int SElemType;
// 定义链栈
typedef struct StackNode{
SElemType data; // 存放栈的数据
struct StackNode * next;
}StackNode, *LinkStackPtr;
typedef struct LinkStack{
LinkStackPtr top; // top指针
int count; // 栈元素计数器
}linkStack;
栈的链式存储结构操作
一、链栈的基本操作：初始化、获取链栈的长度、判断是否为空、获取栈顶元素等
/**
* 初始化
*/
Status InitStack(linkStack *S){
S->top = (LinkStackPtr)malloc(sizeof(StackNode));
if(!S->top)
return ERROR;
S->top=NULL;
S->count=0;
return OK;
}
/**
* 获取元素
*/
Status visit(SElemType c){
printf("%d ",c);
return OK;
}
/**
* 清空栈
*/
Status ClearStack(linkStack *S){
LinkStackPtr p,q;
p=S->top;
while(p)
{
q=p;
p=p->next;
free(q);
}
S->count=0;
return OK;
}
/**
* 判断栈是否问空
*/
Status StackEmpty(linkStack S){
if (S.count==0)
return TRUE;
else
return FALSE;
}
/**
* 计算栈的长度
*/
int StackLength(linkStack S){
return S.count;
}
/**
* 获取栈顶并返回
*/
Status GetTop(linkStack S,SElemType *e){
if (S.top == NULL) {
return ERROR;
}else{
*e = S.top->data;
}
return OK;
}
二、进栈操作(Push)
对于链栈的进栈(Push)操作，假设元素值为e的新节点是s，top为栈顶指针，插入元素e的代码如下
/**
* 插入元素 e 为新的栈顶元素
*/
Status Push(linkStack * S, SElemType e){
LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
p->data = e;
p->next = S->top; //把当前的栈顶元素赋值给新结点的直接后继
S->top = p; // 将新节点p赋值给栈顶指针。
S->count++;
return OK;
}
三、出栈操作(Pop)
至于链栈的出栈操作，也是简单的三句操作。
- 假设变量p用来存储要删除的栈顶结点。
- 将栈顶指针下移一位
- 释放p。
/**
* 出栈
*/
Status Pop(linkStack * S, SElemType *e){
LinkStackPtr p;
if (StackEmpty(*S)) // 栈为空
return ERROR;
*e = S->top->data;
p = S->top; // 栈顶结点赋值给p
S->top = S->top->next; //栈顶指针下移一位
free(p);
S->count--;
return OK;
}
四、遍历链栈操作(Traverse)
/**
* 遍历
*/
Status StackTraverse(linkStack S){
LinkStackPtr p;
p=S.top;
while(p)
{
visit(p->data);
p=p->next;
}
printf("\n");
return OK;
}
测试代码
int main(int argc, const char * argv[]) {
@autoreleasepool {
int j;
linkStack s;
int e;
if (InitStack(&s)) { //将1到10依次进栈
for (j = 1; j <= 10; j++) {
Push(&s, j);
}
}
printf("栈中的元素依次为：");
StackTraverse(s);
Pop(&s,&e);
printf("弹出的栈顶元素 e=%d\n",e);
printf("栈空否：%d(1:空 0:否)\n",StackEmpty(s));
GetTop(s,&e);
printf("栈顶元素 e=%d 栈的长度为%d\n",e,StackLength(s));
ClearStack(&s);
printf("清空栈后，栈空否：%d(1:空 0:否)\n",StackEmpty(s));
}
return 0;
}
测试结果
对比顺序栈和链栈
- 时间复杂度：均为
O(1) - 空间性能：
- 顺序栈需要事先确定一个固定的长度，可能会存在内存空间浪费的问题。但是它的优势在于存取的时候很方便。
- 链栈要求每个元素都有指针域，也增加了内存开销，但是对于栈的长度无限制。
- 总体而言：如果栈的使用过程中元素变化不可预料，有时很小，有时很大，那么最好用链栈，反之，如果变化在可控范围，使用顺序栈更好。
网友评论