1.栈的概念和结构
概念：栈是一种线性表，它只能从固定的一端进行数据的插入和删除，这一端称为栈顶，另一端称为栈底。栈遵循先入后出的原则。
压栈：栈的插入操作可以称为进栈/压栈/入栈，入数据在栈的顶部。
出栈：栈的删除操作叫出栈，出的数据也是在栈顶。
进栈：
出栈：
2.栈的实现
栈的实现可以用数组或者链表来作底层，用数组的结构来实现会更简单一些，数组的插入数据也比较方便。
栈用数组来实现可以用定长数组也可以用变长数组实现。
变长数组：
栈的头文件：
// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈 typedef int STDataType; #define N 10 typedef struct Stack { STDataType _a[N]; int _top; // 栈顶 }Stack; // 支持动态增长的栈 typedef int STDataType; typedef struct Stack { STDataType* _a; int _top; // 栈顶 int _capacity; // 容量 }Stack; // 初始化栈 void StackInit(Stack* ps); // 入栈 void StackPush(Stack* ps, STDataType data); // 出栈 void StackPop(Stack* ps); // 获取栈顶元素 STDataType StackTop(Stack* ps); // 获取栈中有效元素个数 int StackSize(Stack* ps); // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 int StackEmpty(Stack* ps); // 销毁栈 void StackDestroy(Stack* ps);
初始化栈 ：
void StackInit(Stack* ps) { ps->_a = NULL; ps->_capacity = 0; ps->_top = -1; }
入栈：
void StackPush(Stack* ps, STDataType data) { if (ps->_capacity == ps->_top + 1) { if (ps->_capacity == 0) { ps->_a = (Stack*)malloc(sizeof(ps->_a)); ps->_capacity = 1; } else { int newcapacity = 2 * ps->_capacity; Stack* n = (Stack*)realloc(ps->_a, newcapacity * sizeof(ps->_a)); if (n==NULL) { exit(1); } ps->_a = n; } } ps->_top++; ps->_a[ps->_top] = data; }
出栈 :
void StackPop(Stack* ps) { ps->_top--; }
获取栈顶元素 :
STDataType StackTop(Stack* ps) { return ps->_a[ps->_top]; }
获取栈中有效元素个数 :
int StackSize(Stack* ps) { return ps->_top+1; }
检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(Stack* ps) { if (ps->_top == -1) return 0; else return 1; }
销毁栈 :
void StackDestroy(Stack* ps) { for (; ps->_top > -1; ps->_top--) { free(ps->_a[ps->_top]); ps->_a[ps->_top] = NULL; } }
