出栈顺序判断方法

数据结构中有一个铁路调度的问题，跟你说的差不多。
我是这样想的：对于某个给定的串，比如“52314”，每个数都先压栈然后出栈，也就是说每个数都必须进栈。5是先出栈，4是最后出栈。现在倒着想，让这些数字重新回去，看能否组成1,2,3,4……n，如果能够组成就说明给定的串是可行的，否则不可行。现在开始倒着往回走，先把最后一个数入栈，不符合出栈条件的，先存入栈中，接着入栈，符合出栈条件的，一直出栈，直到栈为空或不符合出栈条件；栈为空，表明该串可行，不符合出栈条件说明该串不可行。现在让4入栈，此时还不能出栈，因为最大值是5,；然后1入栈，也不能出栈；……；5入栈，可以出栈；下面是2,此时应该4出栈，2不能出栈，结束判断，该串不可行。

下面是我写的C语言程序：首先输入一个n，表明有n个数，然后输入n个数，这n个数用空格或换行隔开。输出yes说明可行，输出no说明不可行。

#include
int main()
{
int stack[1010], a[1010], top, i, n, p;
while(scanf("%d",&n) && n)
{

top=-1;//此时栈为空
p=n;//p用来表示此时应该是几出栈
for(i=1; i<=n; i++)
{
scanf("%d", &a[i]);
}
for(i=n; i>=1; i--)
{
top++;
stack[top]=a[i];//压栈

while(1)
{
if(top==-1||p!=stack[top]) break;//如果此时栈为空或者不符合出栈条件，停止出栈
else
{
top--;//否则出栈
p--;
}
}
}
if(top==-1) printf("Yes\n");
else printf("No\n");
}

return 0;
}

这个是我用C写的
#include
using namespace std;
int istrue(int b[5])
{int tmp[4]={0},tmp1=0,m=0,i;
for(i=0;i<5;i++)
{
tmp1 = b[i];
for(int j=i+1;j<5;j++)
if(tmp1>b[j])
{
tmp[m] = b[j];
m++;
}
for(int j=0;j if(tmp[j] return false;
m=0;
for(int j=0;j<5;j++)
tmp[j] = 0;
}
return true;
}
main()
{
int b[5]={0};
int a[5]={1,2,3,4,5};
for(int i=0;i<5;i++)
cin>> b[i];
if(istrue(b))
cout<<"OK"<else cout<<"error"<
}
思路就是如果一个数先出栈，那么比他小的数必须顺序出栈

C++写的。
先输入多少个数，然后输入出栈序列。
注意是从0开始的。也就是入栈序列是0 1 2 ... n-1

#include
using namespace std;

bool judge(int popsq[], int len)
{
if (0==len) return true;
int a,b;
bool *p = new bool[len];
for (int i=0; i p[popsq[0]] = true;
for (int i=1; i {
if (popsq[i]+1 < popsq[i-1])
{
for (int j=popsq[i]+1; j {
if (p[j] == false)
{
delete[] p;
return false;
}
}
p[popsq[i]] = true;
}
else
{
p[popsq[i]] = true;
}
}
delete[] p;
return true;
}

int main()
{
int len;
int *sq;
cout<<"number of numbers:";
cin>>len;
if (len<1) return 0;
sq = new int[len];
cout<<"pop sequence:";
for (int i=0; i>sq[i];
if (judge(sq,len)) cout<<"yes";
else cout<<"no";
cout< return 0;
}

---------------------------------------------昏哥线-----------------------------------------------
用二楼兄弟的方法又写了个，呵呵
这个是从1开始的

#include
using namespace std;

bool judge(int popsq[], int len)
{
if (0==len) return true;
int push=1;
int top=-1;
int *stack = new int[len];

for (int i=0; i {
while (popsq[i] >= push)
{
top++;
stack[top] = push;
push++;
}
if (stack[top] == popsq[i])
{
top--;
continue;
}
else
{
delete[] stack;
return false;
}
}
delete[] stack;
return true;
}

int main()
{
int len;
int *sq;
cout<<"number of numbers:";
cin>>len;
if (len<1) return 0;
sq = new int[len];
cout<<"pop sequence:";
for (int i=0; i>sq[i];
if (judge(sq,len)) cout<<"yes";
else cout<<"no";
cout< return 0;
}

最简单直接的方法就是用代码模拟入栈，出栈的过程：
如果栈顶等于下一个要出栈的数，就让栈顶出栈，同时从出栈序列拿掉；
如果栈顶不等于下一个要出栈的数，就从入栈序列取下一个入栈；
如果栈顶不等于下一个要出栈的数，入栈序列又空了，那么就是无效的出栈序列。
如果出栈序列空了，那就是符合了。

代码：（拿来做scala练手了，当伪代码看吧）

import scala.collection.mutable._;

object Main extends App {
assert(args.length == 2, "need parameters: ");
assert(args(0).length == args(1).length, "in/out length not equal");

val inseq = new Queue[Char]();
inseq ++= args(0);
val outseq = new Queue[Char]();
outseq ++= args(1);

val stack = new ArrayStack[Char]();

def checkValid(inseq: Queue[Char], outseq: Queue[Char], stack: ArrayStack[Char]): Boolean = {
if(outseq.isEmpty) {
// all out stack
true
} else if((stack.isEmpty || stack.top != outseq.front) && inseq.isEmpty) {
// can't progress, invalid
false
} else {
if((!stack.isEmpty) && stack.top == outseq.front) {
// match, out stack
stack.pop();
Console.println("out: " + outseq.front);
outseq.dequeue();
} else {
// in stack
stack.push(inseq.front);
Console.println("in: " + inseq.front);
inseq.dequeue();
}
checkValid(inseq, outseq, stack)
}
}
val ok = checkValid(inseq, outseq, stack);
Console.println(if(ok) "ok" else "invalid");
}