Question

简单是数据结构题 急，，，，，，，，

1.将一个数，从操作数序列的头端移动到栈的头端（对应数据结构栈的push操作）
2.将一个数，从栈的头端移动到输出序列的尾端（对应数据结构的pop操作）

使用这2个操作，由一个操作数序列就可以得到一系列的输出序列，下面为由1 2 3 到 2 3 1 的过程：

操作数：1 2 3
栈：
输出端：

操作数：2 3
栈：1（栈底）
输出端：

操作数：3
栈：2 1（栈底）
输出端：

操作数：3
栈：1（栈底）
输出端：2

操作数：
栈：3 1（栈底）
输出端：2

操作数：
栈：1（栈底）
输出端：2 3

操作数：
栈：
输出端：2 3 1
现在对于任意一个N，输入端的数据一定是1，2，3...N
对于任意一个序列，请问是否能根据规则产生这样的序列；

例子：
输入：
5
1 2 3 5 4
输出：
Yes

我的代码：

//xieai999
#include <iostream>
#include <malloc.h>
using namespace std;

typedef struct study
{
int e[1000];
int top;
}LT;

void Creat(LT *&s)
{
s=(LT *)malloc(sizeof(LT));
s->top=-1;
}

void Display(LT *s,int a[],int n)
{
int *r=new int[n];
for(int i=0;i<n;i++)
r[i]=i+1;
int j=0;
for(int k=0;k<n;k++)
{
s->top++;
s->e[s->top]=r[k];
for(int g=0;g<n;g++)
{
if(s->e[s->top]==a[j])
{
s->top--;
j++;
}
else
break;
}
}

if(s->top==-1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
delete []r;
}

int main()
{
int n;
while(cin>>n)
{
int *a=new int[n];
for(int i=0;i<n;i++)
{
int x;
cin>>x;
a[i]=x;
}
LT *A;
Creat(A);
Display(A,a,n);
delete []a;
}
return 0;
}

麻烦高手运行下，，，看结果错在哪里？？？？？
谢谢，，，你的算法很好，，，我试啦，，，可是还是结果错误，，，这是怎么搞的？？？麻烦再看看，，，

在www.bianchengla.com专版的“2009数据结构上机练习”专版里面的练习的“可能出现么？”这个题目，，，谢谢你拉，，，

Answer 1

额...这个题不用那么麻烦

首先..可以标明每一个数在输出序列的位置..这样..输入序列便是乱序的
例如
将1 2 3 4 5
排为1 2 4 5 3
可看成把1 2 5 3 4
排成1 2 3 4 5
原问题即规约成利用一个栈进行排序的问题

令q1[i]表示经过处理的输入序列的第i个数字

考虑对于任意两个数q1[i]和q1[j]来说,它们不能压入同一个栈中的充要条件是什么(注意没有必要使它们同时存在于同一个栈中,只是压入了同一个栈).实际上,这个条件p是:存在一个k,使得i<j<k且q1[k]<q1[i]<q1[j].

首先证明充分性,即如果满足条件p,那么这两个数一定不能压入同一个栈.这个结论很显然,使用反证法可证.
假设这两个数压入了同一个栈,那么在压入q1[k]的时候栈内情况如下:
…q1[i]…q1[j]…
因为q1[k]比q1[i]和q1[j]都小,所以很显然,当q1[k]没有被弹出的时候,另外两个数也都不能被弹出(否则q2中的数字顺序就不是1,2,3,…,n了).
而之后,无论其它的数字在什么时候被弹出,q1[j]总是会在q1[i]之前弹出.而q1[j]>q1[i],这显然是不正确的.

接下来证明必要性.也就是,如果两个数不可以压入同一个栈,那么它们一定满足条件p.这里我们来证明它的逆否命题,也就是"如果不满足条件p,那么这两个数一定可以压入同一个栈."
不满足条件p有两种情况:一种是对于任意i<j<k且q1[i]<q1[j],q1[k]>q1[i];另一种是对于任意i<j,q1[i]>q1[j].
第一种情况下,很显然,在q1[k]被压入栈的时候,q1[i]已经被弹出栈.那么,q1[k]不会对q1[j]产生任何影响(这里可能有点乱,因为看起来,当q1[j]<q1[k]的时候,是会有影响的,但实际上,这还需要另一个数r,满足j<k<r且q1[r]<q1[j]<q1[k],也就是证明充分性的时候所说的情况…而事实上我们现在并不考虑这个r,所以说q1[k]对q1[j]没有影响).
第二种情况下,我们可以发现这其实就是一个降序序列,所以所有数字都可以压入同一个栈.
这样,原命题的逆否命题得证,所以原命题得证.

此时,条件p为q1[i]和q1[j]不能压入同一个栈的充要条件也得证.

所以只需要遍历一遍队列...找是否存在这样的k就可以了...

额...那你是不是遍历得有问题或者什么的....
你在哪个OJ提交的...我去试试

检查一下细节好了
会不会是Yes打成了YES(就跟我一样...)

然后输入的时候，再考虑一下数据不符合情况，例如重复输入，或者数字超过范围之类的

附我的源码

#include <stdio.h>
#include <string.h>
#define min(a,b) ((a>=b)?(b):(a))

int main(void)
{
int i,j,n,tmp;
int que[1001],mintn[1001];
while(scanf("%d",&n)!=EOF)
{
memset(que,0,sizeof(que));
for(i=1;i<=n;i++)
{
scanf("%d",&tmp);
if(que[tmp]||tmp>n||tmp<1)
{
printf("No\n");
goto sflag;
}
que[tmp]=i;
}
mintn[n]=que[n];
for(i=n-1;i>=1;i--)
mintn[i]=min(que[i],mintn[i+1]);
for(i=1;i<=n-2;i++)
for(j=i+1;j<n;j++)
if(que[i]<que[j]&&mintn[j+1]<que[i])
{
printf("No\n");
goto sflag;
}
printf("Yes\n");
sflag:;
continue;
}
return 0;
}

我用了一个优化
就是如果对于数对(i,j),都去枚举检查是否存在k使得p1[k]<p1[i]<p1[j]的话,那么复杂度就升到了o(n^3).解决方法就是,首先预处理出数组b,b[i]表示从p1[i]到p1[n]中的最小值.接下来,只需要枚举所有数对(i,j),检查b[j+1]是否小于p1[i]且p1[i]是否小于p1[j]就可以了.

然后...我是为了快速过题用的goto
这不是一种好的编程习惯...最好别用