数据结构基础（4）C语言实现栈–链式存储（动态栈）
最后更新于：2022-04-01 11:18:45
写程序的时候，我们经常会说基本类型变量存在栈内存，引用类型的变量（对象，数组）存在堆内存。现在我们来看看栈这种数据结构是怎么实现的。
## 定义
一种可以实现“先进后出” 的存储结构
栈类似于往箱子放衣服，先放的最后拿
## 栈的分类：
静态栈：以数组方式实现，删除时删除下标最大的,插入时从最大下标+1插入
动态栈：以链表方式实现，删除和插入都是从头部
## 算法：出栈（POP），入栈（PUSH）
## 应用：
1.函数调用 :在函数f中调用另一个g函数，在g函数中调用k函数
执行到要调用g函数位置，先把g函数执行后下一句的地址以及变量压栈，执行g函数，执行到调用k函数的位置，再把k函数执行后的下一句压栈，然后执行k函数，执行后取出栈顶元素，赋给CPU，执行g函数中调用k函数后的下一句。
2.中断
3.表达式求值：3*2+5/6-4两个栈实现，一个放运算符，一个放数据
4.内存分配：把函数形参压入栈中
5.缓冲处理
6.走迷宫
## C语言实现：
下面是C语言实现动态栈的代码，为了方便在栈底部建立一个头结点，不存有效数据。先看图：
~~~
#include<stdio.h>
#include<malloc.h>
#include<stdbool.h>
//栈有一个不存放有效数据的头节点，Pbotom始终指向头结点。
/**
**定义节点的结构体
*/
typedef struct Node{
int data;//数据域
struct Node * PNext;//指针域
} Node,*PNext;
/**
**定义栈的结构体
*/
typedef struct Stack {
PNext top;
PNext bottom;
}Stack,* PStack;
/**
**初始化栈
*/
void init(PStack PStack )
{
//建立一个不存任何有限元素的头结点，作为栈底
PStack->bottom=malloc(sizeof(Node));
PStack->top=PStack->bottom;
PStack->top->PNext=NULL;
}
/**
*遍历栈
**/
void traverse(PStack Ps )
{
if(Ps->bottom==Ps->top)
{
printf("栈为空\n");
return ;
}
PNext pt=Ps->top;
while(pt!=Ps->bottom)//不能把pt换成ps->top这样就修改了链表。尴尬。。
{
printf("%d ",pt->data);
pt=pt ->PNext;
}
printf("\n");
return ;
}
/**
**入栈
*/
void push(PStack Pstack,int val)
{
PNext Pnew=malloc(sizeof(Node));//生成一个新节点
Pnew->data=val;
Pnew->PNext=Pstack->top;
Pstack->top=Pnew;
}
/**
**出栈
*/
void pop(PStack ps )
{
if(ps->top==ps->bottom)
{
printf("栈为空，无法完成出栈操作\n");
return;
}
PNext temp=ps->top;//引入辅助变量，用于释放内存
ps->top=ps->top->PNext;
free(temp);
temp=NULL;
}
/**
**清空栈
*/
void clear(PStack ps)
{
while(ps->top!=ps->bottom)
{
PNext temp=ps->top;
ps->top=ps->top->PNext;
free(temp);
}
}
int main()
{
Stack stack;
init(&stack);
push(&stack,6);
push(&stack,7);
push(&stack,8);
traverse(&stack);
pop(&stack);
traverse(&stack);
clear(&stack);
traverse(&stack);
push(&stack,7);
traverse(&stack);
return 0;
}
~~~