n个元素出栈不同排列个数\frac{1}{n+1}C_{2n}^{n}

中缀转后缀

  1. 遇到操作数直接加入表达式

  2. 遇到界限符，"("入栈，“)”则依次弹出栈内运算符，直到遇到“(”，"("与“)”不加入表达式

  3. 遇到运算符，若优先级高于栈顶运算符，则入栈，否则依次弹出优先级高于或等于当前运算符的运算符

栈的基本定义和基本实现

1.定义顺序存储的栈(数组实现)

#define MaxSize
typedef struct{
	int data[MaxSize];
	int top;
}SqStack;

2.顺序存储栈基本操作

//判栈空
bool StackEmpty(SqStack S){
	if(S.top==-1)
		return true;
	else
		return false;
}
//入栈
bool Push(SqStack &S,int x){
	if(S.top==MaxSize-1)  //栈满
		return false;
	S.data[++S.top]=x;
	return true;
}
//出栈
bool Pop(SqStack &S,int &x){
	if(S.top==-1)  //栈空
		return false;
	x=S.data[S.top--];
	return true;
}

3.定义链式存储的栈(单链表实现)

typedef struct SNode{
	int data;
	struct SNode *next;
}SNode,*LiStack;

4.单链表实现的栈，栈顶在链头的基本操作

//初始化链栈
bool InitStack(LiStack &S){
	S=(SNode *)malloc(sizeof(SNode));
	S->next=NULL;
	return true;
}
//判空
bool StackEmpty(LiStack S){
	if(S->next==NULL)
		return true;
	else
		return false;
}
//入栈(单链表的头插法)
bool Push(LiStack &S,int x){
	SNode *p=SNode *)malloc(sizeof(SNode));
	p->data=x;
	p->next=S->next;
	S->next=p;
	return true;
}
//出栈(单链表的头删法)
bool Pop(LiStack &S,int &x){
	if(StackEmpty(S))
		return false;
	SNode *p=S->next;
	x=p->data;
	S->next=p->next;
	free(p);
}