一、算法设计思想
1.ABCD顺序入栈，任意时刻出栈，共多少种排列 (Catalan数：(1/n+1)·C 2nn)
一定不存在这种情况：i<j<k，Str[i]>Str[k]>Str[j]。只需要在全排列的基础上减去不满足的情况。
ABCD、ABDC、ACBD、ACDB、ADCB、BACD、BADC、BCAD、BCDA、BDCA、CBAD、CBDA、CDBA、DCBA
2.共享栈
第一个栈从数组头开始存储，第二个从数组尾开始存储。当top1+1=top2或者top1=top2-1的时候栈满。
3.模拟队列
一个栈是s1用来模拟入队，另一个栈s2用来模拟出队。当s1和s2都为空时，队列才为空；
（1）入队：当s1不满时，直接进栈；当s1栈满时，s1元素退栈至s2再进栈，如果此时s2非空，则不能入队。
（2）出队：当s2非空时，直接退栈；当s2为空时，s1元素全部退栈至s2再退栈，如果此时s1为空，则队列为空，不能出队。
二、代码实现
1.ABCD顺序入栈，任意时刻出栈，共多少种排列
void AllRange(char *str,int k,int m)
{
if(k==m){
static int cnt=1;
char a,b,c;
//排除i<j<k，Str[i]>Str[k]>Str[j]的情况
for(int i=0;i<=m-2;++i){
a=Str[i];
for(int j=i+1;j<=m-1;++j){
b=Str[j];
for(int k=j+1;k<=m;++k){
c=Str[k];
if(a>b&&a>c&&b<c)
return;
}
}
}
printf("第%d个排列是%s\n",cnt,Str);
}
else{
for(int i=k;i<=m;++i){
Swap(&Str[i],&str[k]); //交换使用地址传递
AllRange(Str,k+1,m);
Swap(Str+i,Str+k); //回溯前进时交换的回退再交换回来
}
}
}
2.共享栈
//结构体
typedef struct
{
int data[maxSize];
int top1,top2;
}ShareStack;
//入栈
int push(ShareStack &ss,int x,int flag) //flag：操作栈的编号
{
if(ss.top1+1==ss.top2)
return 0;
if(flag==1){
ss->data[++ss.top1]=x;
return 1;
}
else if(flag==2){
ss->data[--ss.top2]=x;
return 1;
}
return 0;
}
//出栈
int pop(ShareStack &ss,int &x,int flag)
{
if(flag==1){
if(ss.top1==-1)
return 0;
x=ss.data[top1--];
return 1;
}
else{
if(ss.top2==MAXSIZE)
return 0;
x=ss.data[top2++];
return 1;
}
return 0;
}
3.模拟队列
//判断是否为空
if(isEmpty(s1)&&isEmpty(s2))
return 1;
else
return 0;
//入队
int enQueue(SqStack &s1,SqStack &s2,int x)
{
int y;
if(s1.top==maxSize-1){ //如果s1栈满
if(!isEmpty(s2)) //s2非空，不能入栈
return 0;
else{ //s2为空，s1元素逐个退栈到s2
while(!isEmpty(s1)){
pop(s1,y);
push(s2,y);
}
push(s1,x); //x入栈s1
return 1;
}
}
else{ //s1不满，直接进栈
push(s1,x);
return 1;
}
}
//出队
int deQueue(SqStack &s1,SqStack &s2,int &x)
{
int y;
if(!isEmpty(s2)){ //s2不空，直接退栈
pop(s2,x);
return 1;
}
else{ //s2为空
if(isEmpty(s1)) //s1也为空，队列为空，不能退栈
return 0;
else{
while(!isEmpty(s1)){ //s1退栈到s2
pop(s1,y);
push(s2,y);
}
pop(s2,x); //s2退栈，实现出队
return 1;
}
}
}