栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除插操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出的原则。
压栈：栈的插入操作叫做压栈/进栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。
栈的实现：
关于栈的接口：
1. 栈结构的实现
2.栈的初始化
3.入栈
4.出栈
5.取栈顶元素
6.判断栈是否为空
7.栈元素的个数
8.栈的销毁
1. 栈结构的实现
typedef int StackDataType;
typedef struct Stack
{
StackDataType* data;
int top;//记录栈顶的下一个位置的下标
int capacity;
}Stack;
2.栈的初始化
void StackInit(Stack* ps)
{
assert(ps);//传进来的地址不能为空
ps->data = NULL;
ps->capacity = 0;
ps->top = 0;
}
3.入栈
void StackPush(Stack* ps, StackDataType x)
{
assert(ps);
if (ps->capacity == ps->top)//判断容量是否已经满了 满了进行扩容；
{
int newcapacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity);
StackDataType* temp = (StackDataType*)realloc(ps->data, newcapacity * sizeof(StackDataType));
if (temp == NULL)
{
perror("realloc:");
exit(-1);
}
ps->data = temp;
ps->capacity = newcapacity;
}
ps->data[ps->top] = x;
ps->top++;
}
4.出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));//出栈操作 栈不能为空 判空接口实现在6
ps->top--;
}
5.取栈顶元素
StackDataType StackTop(Stack* ps)
{
assert(ps);
assert(!StackEmpty(ps));//取栈顶元素，栈不能为空
return ps->data[ps->top - 1];//top是栈顶的下一个位置的下标，所以要减一
}
6.判断栈是否为空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
7.栈元素的个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
8.栈的销毁
void StackDistory(Stack* ps)
{
assert(ps);
free(ps->data);
ps->data = NULL;
ps->capacity = 0;
ps->top = 0;
}
今天就到这了！！！ 下次见！
