栈特点是先进后出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.topMaxSize-1)return 1; else return 0; }7、求栈长int StackLength(SqStack st){ return st.top1; }8、入栈int Push(SqStack st,int x){ if(st.topMaxSize-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; xst.data[st.top];//先取出元素再移动指针 --(st.top); return 1; }10、取栈顶int GetTop(SqStack st,int x){ if(st.top-1)return 0; xst.data[st.top]; return 1; }说明1、在考试中栈常常作为一个工具来解决其他问题因此可以写的很简单1)初始化和定义int satck[MaxSize];int top-1;2)进栈stack[top]x;3)出栈xstack[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-nextNULL: }3、清空栈4、销毁栈5、判空int isEmpty(LNode *lst){ if(lst-nextNULL)return 1; else return 0; }6、判满7、求栈长8、入栈void Push(LNode *lst,int x){ LNode *p; p(LNode *)malloc(sizeof(LNode)); p-nextNULL;// 每当申请新节点的时候将其指针域设置为NULL,是可以避免一些错误的好习惯 /*以下三句就是链表的头插法*/ p-datax; p-nextlst-next; lst-nextp; }9、出栈int Pop(LNode *lst,int x){ LNode *p; if(lst-nextNULL)return 0;//栈空则不能出栈返回0 /*以下就是单链表的删除操作*/ plst-next; xp-data; lst-nextp-next; free(p); return 1; }10、取栈顶链栈的存储结构、基本操作与顺序栈类似此处不再赘述后续笔记补充具体代码。应用后续笔记有具体代码括号如何配对表达式求值递归转非递归出栈序列合法性单栈操作双栈操作。。。