一 定义
概念
栈是一种特殊的线性表，只允许在固定的一端进行操作。该端叫做栈顶，相对的另一端叫做栈底。
符合LIFO（后进先出）的规则
关于栈顶的两个操作：
压栈/入栈/进栈：在栈顶部插入数据
出栈:栈顶删除，进行出数据
区别于顺序表：顺序表能在任意位置进行插入和删除，但是栈只允许在一端，进行操作的一端叫做栈顶
二 操作
1 结构定义
栈是线性结构，用顺序表和链表都可以。但是要符合LIFO的原则的话，如果采用单链表需要遍历，时间复杂度O(n),如果用顺序表时间复杂度O（1）。当然，链表采用特殊的方法的话，也可以做到O（1），但是为了简便，采用顺序表
区别于顺序表的size 这里引入top（只允许在一端操作，用top标识可以操作的端口）
typedef int StackDataType;
struct Stack {StackDataType* a;int top;//只用在栈顶操作 区别于顺序表的sizeint capacity;//方便扩容
};2 初始化
和顺序表初始化操作是一样的
注意：此时top初始化成0，也就意味着指向数组最后一个元素下标的下一个位置，相当于顺序表的size
如果想标识数组中元素的最后一个位置，可以用-1初始化
void InitStack(Stack* ps) {assert(ps);//指针解引用操作 因此判空ps->a = NULL;//top标识元素的下一个位置相当于顺序表中的sizeps->top = ps->capacity = 0;
}3 销毁
和顺序表的操作是一样的
void DestroyStack(Stack* ps) {assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}4 入栈
入栈相当于顺序表的尾插。由于top被初始化为0，因此先插入再top++
void PushStack(Stack* ps, StackDataType x)
{assert(ps);//容量检测if (ps->top == ps->capacity) {int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;StackDataType* tmp = (StackDataType*)realloc(ps->a, sizeof(StackDataType) * newCapacity);assert(tmp);ps->capacity = newCapacity;ps->a = tmp;printf("扩容成功\n");}ps->a[ps->top] = x;ps->top++;
}5 出栈
要注意不为空才能出栈。和顺序表的尾删操作是一样的
void PopStack(Stack* ps) {assert(ps);assert(ps->top > 0);//不为空才能出栈ps->top--;
}6 取栈顶元素
由于top标识最后一个元素的下一个位置，因此先要定位到最后一个元素的位置再进行操作
StackDataType TopStack(Stack* ps) {assert(ps);assert(ps->top > 0);int pos = ps->top - 1;return ps->a[pos];
}7 返回有效元素的个数
int SizeStack(Stack* ps){assert(ps);return ps->top;
}
8 判空
bool EmptyStack(Stack* ps) {assert(ps);return ps->top == 0;//为0则空 返回true 否则false
}
