点击加载图片
1.栈的概念及结构
栈存储数据的方式跟数组一样，都是将元素排成一行。只不过它还有以下3条约束。
●只能在末尾插入数据。
●只能读取末尾的数据。
●只能移除末尾的数据。
你可以将栈看成一叠碟子：你只能看到最顶端那只碟子的碟面，其他都看不到。另外，要加碟子只能往上加，不能往中间塞，要拿碟子只能从上面拿，不能从中间拿（至少你不应该这么做）。绝大部分计算机科学家都把栈的末尾称为栈顶，把栈的开头称为栈底。
尽管这些约束看上去令人很拘束，但很快你就会发现它们带来的好处。
我们先从一个空栈开始演示。
往栈里插入数据，也叫作压栈。你可以想象把一个碟子压在其他碟子上的画面。
首先，将5压入栈中。
点击加载图片
接着，将3压入栈中。
点击加载图片
再将0压入栈中。
点击加载图片
注意，每次压栈都是把数据加到栈顶（也就是栈的末尾）。如果想把0插入到栈底或中间，那是不允许的，因为这就是栈的特性：只能在末尾插入数据。
从栈顶移除数据叫作出栈。这也是栈的限制：只能移除末尾的数据。
来把栈中的一些数据弹出。
首先，弹出0。
点击加载图片
接着，弹出3。
点击加载图片
这就剩下5了。
点击加载图片
总结：
栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（LastInFirstOut）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
2.栈的实现
栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
2.1栈的结构定义
typedefintSTDataType;typedefstructStack{STDataType*a;//动态开辟数组intcapacity;//记录栈的容量大小inttop;//记录栈顶的位置}Stack;
2.2函数接口的实现
首先是在Stack.h文件中进行函数声明
Stack.h
#pragmaonce#include
在Stack.c文件中进行函数的定义
Stack.c
#define_CRT_SECURE_NO_DEPRECATE1#include'Stack.h'voidStackInit(Stack*ps){assert(ps);//初始化时，可附初值，也可置空ps->a=NULL;ps->capacity=0;ps->top=0;}voidStackDestroy(Stack*ps){assert(ps);//若并未对ps->a申请内存，则无需释放if(ps->capacity==0)return;//释放free(ps->a);ps->a=NULL;ps->capacity=ps->top=0;}voidStackPush(Stack*ps,STDataTypedata){assert(ps);//若容量大小等于数据个数，则说明栈已满，需扩容if(ps->capacity==ps->top){//若为第一次扩容，则大小为4，否则每次扩大2倍intnewCapacity=ps->capacity==0?4:ps->capacity*2;STDataType*tmp=(STDataType*)realloc(ps->a,sizeof(STDataType)*newCapacity);if(tmp==NULL){perror('reallocfail');exit(-1);}ps->a=tmp;ps->capacity=newCapacity;}//压栈ps->a[ps->top]=data;ps->top++;}voidStackPop(Stack*ps){assert(ps);assert(!StackEmpty(ps));//出栈ps->top--;}STDataTypeStackTop(Stack*ps){assert(ps);assert(!StackEmpty(ps));//返回栈顶的数据returnps->a[ps->top-1];}boolStackEmpty(Stack*ps){assert(ps);//返回topreturnps->top==0;}intStackSize(Stack*ps){assert(ps);returnps->top;}
联系客服
