栈
特点是先进后出（FILO）。本质是线性表，有两种存储结构：顺序栈和链式栈。栈的数学性质：Catalan数（N=
)为合法的出栈序列总数量。408必考一个序列合法的判定规则：任意出栈序列中，每个元素之后所有比它小的元素必须逆序（递减）出现。
顺序栈
主要操作（两个状态：栈空、栈满；两个操作:出栈、进栈；两个非法状态：上溢、下溢）
1、结构体定义
typedef struct{
int data[MaxSize];
int top;
}SqStack;
2、初始化栈
void InitStack(SqStack &st){
st.top=-1;//将栈顶指针置为-1
}
3、清空栈
void ClearStack(SqStack &st){
st.top=-1;
}
4、销毁栈
void DestroyStack(SqStack &st){
st.top=-1;
//若栈是动态分配的：free(st.data);
}
5、判空
int isEmpty(SqStack st){
if(st.top==-1)return 1;
else return 0;
}
6、判满
int isFull(SqStack st){
if(st.top==MaxSize-1)return 1;
else return 0;
}
7、求栈长
int StackLength(SqStack st){
return st.top+1;
}
8、入栈
int Push(SqStack &st,int x){
if(st.top==MaxSize-1)return 0;
++(st.top);//先移动指针，再元素进栈
st.data[st.top]=x;
return 1;
}
9、出栈
int Pop(SqStack &st,int &x){
if(st.top==-1)return 0;
x=st.data[st.top];//先取出元素，再移动指针
–(st.top);
return 1;
}
10、取栈顶
int GetTop(SqStack st,int &x){
if(st.top==-1)return 0;
x=st.data[st.top];
return 1;
}
说明：
1、在考试中，栈常常作为一个工具来解决其他问题，因此可以写的很简单：
1)初始化和定义：int satck[MaxSize];int top=-1;
2)进栈：stack[++top]=x;
3)出栈：x=stack[top–];
2、还要再提一点，对于自增操作，++a总比a++效率高，自减有类似的性质。
链栈
注意：考研中链栈的应用远比顺序栈少的多，注意时间分配。
主要操作（两个状态：栈空、栈满暂且认为不存在；两个操作:进栈、出栈）
1、结构体定义
//链栈节点定义
typedef struct LNode{
int data;
struct LNode *next;
}LNode;
2、初始化栈
void InitStack(LNode *&lst){
lst=(LNode*)malloc(sizeof(LNode));//制造一个头节点
lst->next=NULL:
}
3、清空栈
4、销毁栈
5、判空
int isEmpty(LNode *lst){
if(lst->next==NULL)return 1;
else return 0;
}
6、判满
7、求栈长
8、入栈
void Push(LNode *lst,int x){
LNode *p;
p=(LNode *)malloc(sizeof(LNode));
p->next=NULL;// 每当申请新节点的时候，将其指针域设置为NULL,是可以避免一些错误的好习惯
/*以下三句就是链表的头插法*/
p->data=x;
p->next=lst->next;
lst->next=p;
}
9、出栈
int Pop(LNode *lst,int &x){
LNode *p;
if(lst->next==NULL)return 0;//栈空则不能出栈，返回0
/*以下就是单链表的删除操作*/
p=lst->next;
x=p->data;
lst->next=p->next;
free(p);
return 1;
}
10、取栈顶
链栈的存储结构、基本操作与顺序栈类似，此处不再赘述，后续笔记补充具体代码。
