目录
定义
栈(stack)是限定仅在表尾进行插入和删除的线性表。
允许插入和删除的一段称为栈顶(top)，另一端称为栈底(bottom)，不含任何元素的栈称为空栈。栈又称后进先出的(Last In First Out)线性表，简称LIFO结构。
栈的插入操作，叫作进栈，也称压栈、入栈。
栈的删除操作，叫作出栈，有的也叫弹栈。
栈的结构
//栈的结构 typedef int STDataType; typedef struct Stack { STDataType* a; int top; //栈顶,所存数据个数 int capacity; //容量 }ST;
栈的初始化
void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->capacity = 0; ps->top = 0; }
入栈函数
//入栈 void stackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity) { //若容量为0，开辟四个空间，否则开辟原先容量二倍的空间 int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity); if (!tmp) { printf("内存不够，空间开辟失败！"); exit(-1); } ps->a = tmp; ps->capacity= newcapacity; } ps->a[ps->top] = x; ps->top++; }
栈的销毁
void StackDistory(ST*ps) { assert(ps); free(ps->a); ps->capacity = 0; ps->top = 0; }
出栈函数(删除)
void StackPop(ST*ps) { assert(ps); assert(ps->top>0); ps->top -= 1; }
判断栈是否为空
bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0;//为空时返回1(true)，不为空返回0(flase) }
取栈顶函数
int StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; }
遍历栈函数
//栈的遍历必须先打印栈顶，然后出栈，再打印下一个(新的栈顶)， //遍历结束后该栈变为空栈，不在使用的化就进行销毁 void STPrintf(ST*ps) { assert(ps); while (ps->top) { printf("%d ", ps->a[ps->top]); ps->top--; } StackDistory(ps); }
计算栈的大小
void StackSize(ST*ps) { assert(ps); printf("%d", ps->top); }
使用
int main() { ST stack = { 0 }; StackInit(&stack); while (1) { int x; scanf("%d", &x); if (x == -1) break; stackPush(&stack, x); } STPrintf(&stack); printf("\n\n"); StackPop(&stack); StackPop(&stack); StackPop(&stack); STPrintf(&stack); printf("\n\n"); printf("%d", StackTop(&stack)); printf("\n\n"); printf("%d", StackEmpty(&stack)); printf("\n\n"); StackSize(&stack); printf("\n\n"); printf("%d", StackEmpty(&stack)); }
