写程序的时候，我们经常会说基本类型变量存在栈内存，引用类型的变量（对象，数组）存在堆内存。现在我们来看看栈这种数据结构是怎么实现的。
定义
一种可以实现“先进后出” 的存储结构
栈类似于往箱子放衣服，先放的最后拿
栈的分类：
静态栈：以数组方式实现，删除时删除下标最大的,插入时从最大下标+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;}
经受雨，面对另一个轮回。
