本章总览
栈（Stack）只允许在一端进行插入或删除操作的线性表。
栈的相关名词：入栈、出栈、栈顶、栈底、后进先出。
栈的基本操作
InitStack(&S)：初始化一个空栈
StackEmpty(S)：判断一个栈是否为空，若栈为空则返回true，否则返回false
Push(&S,x)：进栈，若栈S未满，则将X加入使之成为栈顶
Pop(&S,&x)：出栈，若栈非空，则弹出栈顶元素，并用X返回
GetTop(S,&x)：读栈顶元素，若栈非空则用x返回栈顶元素
ClearStack(&S)：销毁栈，并释放S占用的内存空间
顺序栈：采用顺序存储的栈
#define MaxSize 50
typedef struct {
ElemType data[MaxSize];
int top;
}sqStack;
初始化
void InitStack(SqStack &S){
S.top == -1;
}
判断栈空
bool StackEmpty(SqStack S){
if(S.top == -1)
return true;
else
return false;
}
进栈
bool Push(SqStack &S,ElemType x){
if(S.top == MaxSize-1)
return false;
S.data[++s.top] = x;
return true;
}
出栈
bool Pop(SqStack &S,ElemType x){
if(S.top == -1){
return false;
}
x = S.data[S.top--];
return true;
}
读出栈元素
bool GetTop(SqStack S,ElemType &x){
if(S.top == -1){
return false;
}
x = S.data[S.top];
return true;
}
共享栈：将两个栈低设置在共享看空间的两端，栈顶向空间中间延伸
判空：0号栈top == -1
1号栈top == MaxSize
栈满：top1-top0 == 1
优点：存取时间复杂度扔为O(1)，但空间利用更加有效
栈链：采用链式存储的栈，所有的操作都在表头进行
typedef struct LNode{
ElemType data;
Struct Linknode *next;
} *LiStack;
