栈
栈的基本概念
栈是一种只允许在一段进行插入或者删除操作的线性表；因此，栈有着后进先出的特性
- 栈是一种线性表
- 这种线性表只允许在一端进行插入、删除操作
- 后进先出的操作特性
栈的基本操作
栈的基本操作主要有初始化一个空栈InitStack(&S)、判断一个栈是否为空StackEmpty(S)、进栈Push(&S,x)、出栈Pop(&S,x)、读栈顶元素GetTop(S,&x)、销毁栈ClearStack(&S)
栈的顺序存储结构
采用顺序存储结构的栈叫做顺序栈，它利用一组地址上连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针top指示当前栈顶的位置
#define MaxSize 50 //定义栈中元素的最大个数
typedef struct{
ElemType data[MaxSize];
int top; //栈顶指针
}SqStack;
栈顶指针：S.top，初始时设置S.top = -1，栈顶元素S.data[S.top]
进栈操作：栈不满时，栈顶指针先加1，再送值到栈顶元素
出栈操作：栈非空时，先取栈顶元素值，栈顶指针再减一
栈空条件：S.top = -1，栈满条件：S.top = MaxSize - 1，栈长S.top + 1
顺序栈的入栈操作上界MaxSize的约束，因此当对栈的最大使用空间估计不足时，有可能发生栈上溢
顺序栈的基本运算
初始化
void InitStack(&S){
S.top = -1; //初始化栈顶指针为-1
}
判断栈是否为空
bool StackEmpty(S){
if (S.top = -1)
return true;
else
return false;
}
进栈操作
bool Push(&S,x){
if (S.top == MaxSize - 1)
return false; //判断栈是否已满
S.data[++S.top] = x; //指针先自加一，然后元素入栈
return true;
}
出栈操作
bool Pop(&S,&x)(
if (S.top == -1)
return false;
x = S.data[S.top--]; //先出栈，指针再减一
return true;
)
需要注意的是，这里的指针指向的是栈顶元素，因此进栈的操作是S.data[++S.top] = x,出栈的操作为x = S.data[S.top--]；如果指针初始化为0（原来为-1），即指针指向的是栈顶元素的下一个位置，则入栈操作变为S.data[S.top++] = x，出栈操作变为x = S.data[--S.top]，相应的栈空、栈满条件也会变化
共享栈
利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间；两个栈的栈底分别设置在共享空间的两端，两个栈向共享空间中间延伸
共享栈是为了更好利用存储空间，只有当整个存储空间被占满时才发生上溢，其存取数据的时间复杂度均为O(1)
栈的链式存储结构
采用链式存储的栈称为链栈；链栈的优点是便于多个栈共享存储空间以及提高其效率，且不存在栈满上溢的情况
链栈通常采用单链表实现，规定所有操作都在单链表的表头进行；规定链栈没有头结点，头指针Lhead指向栈顶元素
栈的链式存储可表示为
typedef struct Linknode{
Elemtype data;
struct Linknode *next;
}*LiStack;
采用链式存储，便于结点的插入与删除；对于带头结点和不带头结点的链栈，在具体实现上有所不同
