题目

设计算法以判断对输入序列1,2，3，…，n，序列 a1,a2,…,an 是否是该栈的合法输出序列。

思路

这里的“顺序”指输入序列的顺序。
判断合法栈的输出序列方法：对于相邻的两个数a1,a2,如果为升序，则记录下顺序小于a2而不等于a1,a2的数，压栈；如果为降序，则将a2与栈顶数进行比较，如果相等，则该部分正确；如果不相等，则整个序列错误。

代码

#include <iostream>
using namespace std;

const int maxlen = 100;
class Stack {
public:
	Stack();
	bool full() const;
	bool empty() const;
	void push(int x);
	int top()const;
	void pop();
private:
	int count;
	int data[maxlen];
};
Stack::Stack() {
	count = 0;
}
bool Stack::full()const {
	return count == maxlen-1;
}
bool Stack::empty()const {
	return count == 0;
}
void Stack::push(int x) {
	if ( full()) cout<<"Overflow";
	else {
		data[count] = x;
		count++;
	}
}
int Stack::top()const {
	if (empty())return UNDERFLOW;
	else return data[count - 1];
}
void Stack::pop() {
	if (empty())cout<<"Underflow";
	else count -= 1;
}

int main() {
	int size;
	cin >> size;
	int a[maxlen];
	int x;
	for (int i = 0; i < size; i++) {
		cin >> x;
		a[i] = x;
	}
	Stack q;
	int c=0;
	int flag = 0;
	for (int i = 1; i < size+1; i++) {
		if (i == a[c]) {
			c++;
			if (a[c] < a[c -1]) {
				c++;
				int top = q.top();
				if (a[c-1] == top) {
					q.pop();
					continue;
				}
				else {
					cout << "wrong sequence";
					flag = 1;
					break;
				}
			}
			else continue;
		}
		q.push(i);
	}
	if (flag == 0)cout << "correct sequence";
	return 0;
}

如果有错误请大佬指出！感谢！

栈的合法输出序列

最近写栈的实验题，附加题中涉及合法输出序列。

<1>假设栈的输入序列为1、2、3、…、n，设计算法实现对给定的一个序列，判定其是否是此栈合法的输出序列。
<2>假设栈的输入序列为1、2、3、…、n，设计算法求出所有可能的出栈序列。

第一问在网上可以找到规律——判断出栈序列是否合法
它的规律在于出栈序列中，元素i之后所有比i小的元素间必须是降序排列的，元素i从头向后遍历。
因此在判断是，需要引入两个循环和一个变量表示最小值，然后依次进行比较。

bool StackArray::JudgeMatchedStackArray(int a[],int len)
{
    int low=0;//表示一遍遍历中的最小值
    for(int i=0;i<len;++i)//元素i从头向后依次遍历
    {
        low=a[i];
        for(int j=i;j<len;++j)//从元素i开始向后遍历，验证规律
        {
            if(a[j]<a[i])//首先要找之后比元素i小的元素
            {
                if(a[j]>low)
                    return false;
                else    //验证这些元素按照降序排列
                    low = a[j];
            }
        }
    }
    return true;
}

第二问较为复杂，基本思路是用递归解决。
这里贴两个提供思路的网址：

一、
（1）
我们之前谈到，合法的出栈序列条件： 对于每个已出栈数之后的且小于此数的数都必须按降序排列。例如1 2 5 3 4。对于5来说，后面的3,4都小于5，可是3,4却是升序的。则肯定不是合法的出栈序列。
由此可以想到我们可以求出所有的全排列，然后从中剔除掉非法序列。显然，当序列的长度增加时，多余的计算太多，效率太低。
（2）
模拟入栈出栈过程，每次都有两种选择，要么入栈要么出栈。显然按照递归方式是可行的。但是又有一个问题，一般递归，很少牵扯到递归层次之间数据传送问题。而模拟这个过程时，栈的信息从上层传到下层，最后回到上层时，必然栈的状态早已被下层改了。解决办法就是，下层返回时，回复栈的原状态。这样递归就不会出错了。
——求所有的出栈序列

伪代码来源

dostack(输入队列，中间栈，输出队列)  

if(输入队列为空)  
{  
        if(中间栈为空)  
    {
        输出输出队列中的结果 
    }
    else  
    {
        中间栈出栈，放入输出队列  

        dostack(输入队列，中间栈，输出队列)
    }
}
else  
{
        if(中间栈非空) 
    { 
            新建输入队列2、中间栈2、输出队列2 //这种情况下有两个出栈方式，
        //因此需要保存一下原状态，再分别对两个进行处理

            中间栈2出栈并放入输出队列2  

        dostack(输入队列2，中间栈2，输出队列2)
    }

    输入队列出队一个数并压入中间栈  

    dostack(输入队列，中间栈，输出队列) 
}

而要计算一个栈的出栈序列有多少种可能？
可以在上述代码1中添加一个技术变量，最后用它来表示可能种数。
而对于不需要输出所有可能的题目而言，也由相应的计算公式：
对于I(n)有C(2n,n)-C(2n,n-1)个出栈序列

代码块

void StackArray::PopOrderStackArray(StackArray other,QueueArray another)
//该类为输入栈，other 表示中间栈，another 表示输出队列
{
    if(EmptyStackArray())
    {
        if(other.EmptyStackArray())
            another.printQueueArray();
        else
        {
            another.insertQueueArray(other.PopStackArray());
            PopOrderStackArray(other,another);
        }
    }
    else
    {
        if(!other.EmptyStackArray())
        {
            StackArray a(*this),b(other);
            QueueArray c(another);
            c.insertQueueArray(b.PopStackArray());
            a.PopOrderStackArray(b,c);
        }
        other.PushStackArray(PopStackArray());
        PopOrderStackArray(other,another);
    }
    return ;
}

运行结果如下：

1 2 3
1 3 2
2 1 3
2 3 1
3 2 1