栈的合法序列的讨论

xhy7599 · 2020-03-25 15:12:47 · 个人记录

引例

设栈的入栈序列是 1 2 3 4，则下列不可能是其出栈序列的是（）。

A. 1 2 4 3
B. 2 1 3 4
C. 1 4 3 2
D. 4 3 1 2

通过人工模拟出栈过程，我们不难得出其正确答案（D）

但当元素个数过多的时候，这种方法不可取，而且这种人工模拟过程浪费时间且容易出错。因此，我们要构建出数学模型，对这个问题进行进一步的分析。

下面我们对栈的合法输出序列问题进行完善，并从数学模型和算法实现两个角度讨论此问题。

问题描述

对一个栈的输入序列a1,a2,a3,… ,an,称由此栈依次出栈后所得到的元素序列为栈的合法输出序列。

例如，假设栈S的一个输入序列为1,2,3,4,5，则可得到多个输出序列，如1,2,3,4,5就是一个合法的输出序列，同理，5,4,3,2,1和3,2,1,4,5也分别是其合法的输出序列。分别求解下列问题：

（1）判断序列1,3,4,5,2是否是合法的输出序列

（2）对输入序列1,2,3,4,5，求出其所有的合法的输出序列

（3）设计算法以判断对输入序列1,2,3,… ,n，序列a1,a2,a3,… ,an是否是该栈的合法的输出序列（假设输出序列在数组A中）

（4）给出栈的合法的输出序列的规律

用引例中的人工模拟方法，可以验证序列1,3,4,5,2是合法输出序列

对于（2），我们可以把问题引申为：一个栈(无穷大)的进栈序列为1，2，3，…，n，有多少个不同的出栈序列？

我们从数学模型和算法实现角度研究栈的合法输出数列系列问题

求入栈序列对应的所有的合法输出序列种数

（一）数学模型（卡特兰数理论）

我们在坐标系里对此进行描述。

如果有n个元素，在平面直角坐标系中用x坐标表示入栈数，y坐标表示出栈数，则坐标(a,b)表示目前已经进行了a次入栈和b次出栈，则再进行一次入栈就是走到(a+1,b)，即横坐标加一，再进行一次出栈就是走到(a,b+1)，即纵坐标加一。

利用此方法来描述入栈与出栈的操作，在坐标系中具有一般性的规律。分别为：

在任意一次操作前，入栈次数始终小于等于出栈次数，即y≤x始终成立，所以路径一定始终在直线y=x下方。
在最后一步操作后，入栈次数一定等于出栈次数，所以路径的终点一定在直线y=x上

因此，题目相当于求从(0,0)走到(n,n)且不跨越直线y=x的路径数。

例如： (2,4,3,1,5,7,6)就是入栈序列(1,2,3,4,5,6,7)的合法出栈序列，因为其路径（如下图黄色线条所示）始终在直线y=x（蓝色线条）的下方

其线段对应着：(入,入,出,入,入,出,出,……,出,出)，线段向右延申一格记为一次入栈，线段向上延申一格记为一次出栈。

因此，我们得出了利用坐标系描述入栈出栈操作的方法。下面我们来讨论如何利用此方法求解合法出栈序列种数。

<1>. 出栈和入栈次数均为n次的情况（不考虑出栈次数>入栈次数的可能性）

首先，如果不考虑不能跨越直线y=x的要求，相当于从2n次入栈出栈操作中选n次进行入栈（或者理解为线段向右延申n次），则方案数为\ C_{2n}^{n}。

<2>. 出栈和入栈次数均为n次的情况（只考虑出栈次数>入栈次数的情况）

然后，在入栈n次出栈n次的基础上，考虑不合法的情况。对于不合法的出栈方案，一定有某次操作（即棕色线段）使得总出栈次数比总入栈次数多一次，即在坐标系下与直线y=x+1（即下图中深蓝色的线段）相交。

对于这种不合法情况，我们可以在坐标系上直观地看出其特点，即终点仍然落在直线y=x上，但路径经过了直线y=x+1。这种路径的描述不便于我们找出不合法出栈序列的规律，但我们对路径稍作调整，将路径与直线y=x+1的交点后的线段沿直线y=x+1对称处理（对称后的路径为下图绿色线段），如下图所示。

我们把对称前的黄色线段和对称后的绿色线段组成的路径称为新路径。因此，对于每一种不合法路径，我们都有新的路径与之一一对应，这个新的路径一定以(n-1,n+1)为终点。

在这里要注意得出新路径的逻辑顺序：首先，如果有一条路径经过了直线y=x+1，则这条路径非法；其次，这条非法路径从与直线y=x+1的交点到终点的那一段可以沿直线y=x+1对称；最后，对称后的路径一定以(n-1,n+1)为终点。

与前面 <1> 的计算方法同理，我们可以得出在出栈和入栈次数均为n次的前提下非法路径的种数，即\ C_{2n}^{n+1}。

综上，合法路径种数为\ C_{2n}^{n}-\ C_{2n}^{n+1}。

最后，我们对此式进行整理与化简，得出结果为为

\frac{C_{2n}^{n}}{n+1}

结论： 序列个数为 n的出栈序列种数=C(2n,n)/(n+1)

利用卡特兰数的这个规律，我们可以求解入栈序列元素个数为n时，其出栈共有多少种可能性。而且在求解所有合法出栈序列的算法中，我们也会用到类似的思想。

附上Catalan数前12项数表

（二）算法实现Ⅰ（组合数学理论）

我们可以把入栈记为1，出栈记为0，那么对于任意合法的入栈与出栈操作，都可以将其表示为一个0 1数列。这个0 1数列前缀子序列（即前若干项）中1的个数必须大于等于0的个数，表示入栈次数要大于等于出栈次数。如1 1 0 1 0 0（即入,入,出,入,出,出) ，它的任意前缀序列中1的个数是大于等于0的个数的。

例如：对于1 2 3这个入栈序列，1 1 0 1 0 0就是一个入栈出栈序列，第一个1代表元素1入栈，然后第二个1代表元素2入栈，然后第三个是0，代表出栈，即元素2出栈，然后第四个是1，代表元素3入栈，然后第五个是0，代表出栈，即元素3出栈，然后第六个是0，代表元素1出栈。最后1 1 0 1 0 0就代表了出栈序列2 3 1。

那么现在的问题就转换为如何求出所有符合条件的0 1序列了。具体求解思路如下：

对于这个 0 1 的合法序列，在任意时刻，1的数目一定大于等于0的数目（即入栈操作次数≥出栈操作次数）。我们把这个合法序列记为 vector<char> kind，用来存放0 1的序列，其功能为记录栈的入栈出栈操作。

我们还需要规定一个含有n个0和n个1的待入栈序列，这个待入栈序列存放的元素表示对栈的剩余操作次数。也就是说，每次从待入栈序列中取一个元素进入kind数列，最终待入栈序列为空时则栈的操作完成。这个待入栈序列记为count，其中count[0]表示待入栈序列中0的个数（也就是还需执行的出栈操作次数），count[1]同理。

为了满足这一条件，我们在以下情况满足时执行这两种操作

情况（1）插入1：剩余的待入栈数列中还有1，即还有未执行的入栈操作；
情况（2）插入0：剩余的待入栈数列中还有0，即还有未执行的出栈操作，且 栈中（即kind中） 1的数目大于0的数目；

执行完每次的操作后，对新的数列进行递归，并还原成原情况（以便下次操作）。

递归调用的函数如下

void func(vector<char>kind, int count[], int n)
{
    if (count[1] >= 1)    //情况（1），剩余数列中还有1
    {
        kind.push_back('1');
        count[1]--;
        func(kind, count, n); //递归
        count[1]++;
        kind.pop_back();     //还原到操作（1）前
    }
    if ((count[0] >= 1) && (count[0] > count[1]))
    {              //情况（2），剩余数列中还有0且0比1多
        kind.push_back('0');
        count[0]--;
        func(kind, count, n); //递归
        count[0]++;
        kind.pop_back(); //还原到操作（2）前
    }
    if (kind.size() == 2 * n)  //所有元素都扫描完毕，输出
    {
        vector<char>::iterator iter;
        for (iter = kind.begin(); iter != kind.end(); iter++)
        {
            cout << (*iter) << " ";
        }
        cout << endl;
    }
}

在这个函数的基础上，我们把0 1的合法序列kind转换成具体的出栈序列，即用链栈模拟存储元素。当(kind+i)='1'时入栈，当(kind+i)='0'时出栈，通过0 1操作向实际的栈转换，从而得出最终结果。

完整程序如下：

# include <bits/stdc++.h>
using namespace std;

template<class T>
struct node
{
    T value;  //储存的值
    node<T>* next; //储存的结点指针

    node() :next(nullptr) {} //构造函数
    node(T t) :value(t), next(nullptr) {}
};

template<class T>
class MyStack
{
    int counts;
    node<T>* head;
public:
    MyStack() { counts = 0; head = new node<T>; }
    void stackPush(T newnum); //入栈
    T stackPop();             //出栈
    T stackTop();             //获取栈顶元素
    int Counts();             //获取栈内元素个数
    bool isEmpty();           //判断是否为空
};

template<class T>
void MyStack<T>::stackPush(T newnum)
{
    node<T>* pnode = new node<T>(newnum);
    pnode->next = head->next;
    head->next = pnode;
    counts++;
}

template<class T>
T MyStack<T>::stackPop()
{
    if (head->next != nullptr)
    {
        node<T>* temp = head->next;
        head->next = head->next->next;
        T popVal = temp->value;
        delete temp;
        counts--;
        return popVal;
    }
}

template<class T>
T MyStack<T>::stackTop()
{
    if (head->next != nullptr)
    {
        return head->next->value;
    }
}

void printStack(vector<char> K)
{
    MyStack<int> St;
    int x = 1;
    vector<char>::iterator iter;
    for (iter = K.begin(); iter != K.end(); iter++)
    {
        if (*iter == '1') St.stackPush(x), x++;
        if (*iter == '0') cout<<St.stackTop()<<' ', St.stackPop();
    }
    cout << endl;
}

template<class T>
int MyStack<T>::Counts()
{
    return counts;
}

template<class T>
bool MyStack<T>::isEmpty()
{
    if (counts)
        return false;
    else
        return true;
}

//以上为链栈部分

void func(vector<char>kind, int count[], int n)
{
    if (count[1] >= 1)    //情况（1），剩余数列中还有1
    {
        kind.push_back('1');
        count[1]--;
        func(kind, count, n); //递归
        count[1]++;
        kind.pop_back();     //还原到操作（1）前
    }
    if ((count[0] >= 1) && (count[0] > count[1]))
    {              //情况（2），剩余数列中还有0且0比1多
        kind.push_back('0');
        count[0]--;
        func(kind, count, n); //递归
        count[0]++;
        kind.pop_back(); //还原到操作（2）前
    }
    if (kind.size() == 2 * n)  //所有元素都扫描完毕，输出
    {
        printStack(kind);  //打印栈
    }
}

int main()
{
    int n;
    cout << "please input the number:" << endl;
    cin >> n;
    int count[2] = { n ,n - 1 };
    vector<char>kind;
    kind.push_back('1');    //合法序列的第一个数一定是1
    func(kind, count, n);
    return 0;
}

（三）算法实现Ⅱ（二叉树理论）

由卡特兰数理论，我们联想到二叉树结构的类似问题，即n个节点的二叉树有多少种形态。对于此问题，我们可以逐步推导出其数学公式。

先考虑只有一个节点的情形，设此时的形态有f(1)种，那么很明显f(1)=1
如果有两个节点，我们就很自然想到，应该在f(1)的基础上考虑递推关系。那么，如果固定一个节点后，左右子树的分布情况为1=1+0=0+1，故有f(2) = f(1) + f(1)
如果有三个节点，（我们需要考虑固定两个节点的情况么？当然不，因为当节点数量大于等于2时，无论你如何固定，其形态必然有多种）我们考虑固定一个节点，即根节点。按照这个思路，还剩2个节点，那么左右子树的分布情况为2=2+0=1+1=0+2。所以有3个节点时，递归形式为f(3)=f(2) + f(1)*f(1) + f(2)。(这里的乘法，因为左右子树一起组成整棵树，根据排列组合里面的乘法原理即可得出)
对于有n个结点的情形，我们固定一个节点，那么左右子树的分布情况为n-1=n-1 + 0 = n-2 + 1 = … = 1 + n-2 = 0 + n-1。此时递归表达式为f(n) = f(n-1) + f(n-2)f(1) + f(n-3)f(2) + … + f(1)f(n-2) + f(n-1)
接下来我们定义没有节点的情况，此时也只有一种情况，即f(0)=1

那么则有:

f(0)=1，f(1)=1

f(2)=f(1)f(0)+f(0)f(1)

f(3)=f(2)f(0)+f(1)f(1)+f(0)f(2)

… … … …

f(n)=f(n-1)f(0)+f(n-2)f(1)+……….+f(1)f(n-2)+f(0)f(n-1)

由此我们得出n个结点的二叉树共有f(n)种形态，和卡特兰数的递推公式异曲同工。但对于如何把二叉树的形态和合法出栈序列对应起来这个问题，需要我们利用中序遍历的特征加以解答。

我们首先给出结论

按照先序序列进栈，出栈的序列一定是一个中序序列

这个结论还有另外两种描述形式，即

（1）只要按照先序遍历的顺序入栈，无论怎么出栈肯定是符合中序序列的

（2）一个先序遍历对应的所有二叉树，每一棵都必定对应一个出栈序列。

这两种描述的逆命题也成立，因为已知先序遍历和中序遍历，就能得出一个二叉树的形态，反之也能求出唯一与其对应的遍历方式。

对于这个结论的证明，我们分入栈和出栈两部分论证。

入栈部分

先序序列是按照“根左右”的顺序进栈的，但其实际的入栈过程是左子树都处理完了，才开始访问右子树。例如，对于结点p，先序序列在访问该结点p以后该结点p进栈，然后访问p的左子树，然后根节点（p的左子）入栈，再访问p左子树根节点（p的左子）的左子树，直到左子树全部访问完再访问右子树。

压到最左边的结点时q时，在访问完q以后，q入栈，然后访问q的左子。虽然这个时候q的左子是空的，但是访问q的时候并不知道这一点，必须递归一次访问q的左子，进入先序遍历q的左子这一层递归时检测到是空的，才会知道到头了，该层递归跳出，然后开始出栈。

出栈部分

在出栈前，我们假设q的左子（遍历到底层的空结点）也有入栈出栈的两步操作（添加此过程不影响我们对过程的分析，而且这个添加的过程可以帮助我们更好的把握整个流程的顺序）。

我们来分析出栈顺序：第一个出栈的是这个空结点（q左子），然后是空结点的父节点q，然后按照我们前面分析的，这个时候算是q的左子树都处理完了，就开始访问空结点q的右子树。

右子树还是按照相同的过程，先把q的右子（也就是q的右子树的根节点）入栈，然后找右子树的最左结点，以此类推。此过程与左子树的操作过程完全一致。我们也暂不细研究右子树的出栈顺序，把它们看做右子树结点整体。q出栈以后，右子树结点进栈，然后右子树结点出栈。至此，q的父节点的左子树已经完成前序遍历进栈出栈。

“左”访问完了，然后出栈得到q的父节点，然后访问q父节点的右子树，以此类推。

综上，整个过程就是“左根右”，就是一个中序遍历的过程。这说明两方面内容：一是对于这棵树，按先序遍历进栈再出栈得到的是中序序列，二是这棵树的中序序列可以由按先序遍历进栈的情况下的一种出栈顺序得到。

因此，我们得到了一种求解全部合法出栈序列的方法，即构建出n个结点的全部二叉树，对于某个先序遍历，其对应的中序遍历则为合法的出栈排列。

（四）算法实现Ⅲ（回溯法）

我们可以采用回溯法和递归统计所有可能的出栈序列。

采用回溯法解答本题时，要注意着三个模型特征：

当所有的入栈序列已经全部入栈后，则只能出栈
当栈为空时，只能进栈
当仍有入栈元素且栈不为空时，可以入栈，也可以出栈

入栈 -> 递归处理下一个入栈元素 -> 恢复未入栈状态

出栈 -> 将出栈元素添加到出栈序列 -> 递归处理当前入栈元素 -> 恢复栈和出栈序列上一个的状态

具体程序如下：

#include <bits/stdc++.h>
using namespace std;

int tot, res, sta, n;
int r[2005], s[2005];

void recall(int m) {
    if (m == n + 1) {//若所有元素都入过栈，输出当前出栈序列
        tot++;
        cout << "Case #" << tot << ":" << endl;
        for (int i = 1; i <= res; i++) {
            cout << r[i] << ' ';
        }
        for (int i = sta; i > 0; i--) {
            cout << s[i] << ' ';
        }
        cout << endl;
        return;
    }
    if (sta > 0) {
        r[++res] = s[sta];
        sta--;
        recall(m);//栈顶元素出栈
        s[++sta] = r[res];
        res--;//回溯操作
    }
    s[++sta] = m;//当前元素入栈
    recall(m + 1);
    sta--;//回溯操作
}

int main() {
    cin >> n;
    tot = 0; res = 0; sta = 0;
    recall(1);
    cout << "There are total " << tot << " sequences.";
    return 0;
}

判断栈的输出序列是否合法

（一）检查数列的局部单调性

我们先给出这样的一个结论

凡是合法的出栈序列，每个数后面的比它小的数，必然是按递减次序排列的。

为了证明这个结论，我们可以将入栈元素按入栈顺序由1到n进行编号，对于入栈序列1到n，第x个元素入栈时，那么前x-1个数一定已经全部入栈。则当第x个数出栈时，栈中若剩余编号小于x元素，则这些元素一定在存储器中倒序排列。

这个结论还可以用更加严谨的过程来证明，即假设在出栈过程中的某一个步骤时，栈中存留的元素有n个，分别是S1到Sn。

此时，对于元素 Sn，有两种可能性。

在下一步时，可以选择弹出Sn。那么，比Sn小的所有元素，只有两种可能：

a. 还未出栈（不可能还未入栈，因为比它大的元素Sn已经入栈了）：则一定在Sn后以递减的顺序出现在出栈队列中（因为入栈的顺序是严格递增的）

b. 已经出栈：此时，比这个元素还小的元素如果还没出栈，当它即将出栈的时候，就会又递归回到1）的情况。

可以不弹出Sn而是继续入栈，则又回到 1）的情况。

因此，我们得出这样的结论：凡是合法的出栈序列，每个数后面的比它小的数，必然是按递减次序排列的。

利用这个理论，我们可以较快地判断所含元素较少的栈的输出序列是否合法。

在算法实现方面，我们新建数组A存储序号x之前的元素，并扫描数组A以验证其是否逆序。该算法时间复杂度为O（n²）

具体程序如下：

#include<bits/stdc++.h>
using namespace std;

int n, t;
bool checkValidOrder(int *q,int p)
{
    int* A = new int[n]; 
    int x(0);
    for (int i = p + 1; i < n; i++)
        if (q[i] < q[p]) A[x++] = q[i];
    for (int i = 0; i < x; i++)
        if (A[i] < A[i - 1]) return false;
    return true;
    delete[] A;
}

int main() {
    cin >> n;
    int *Q=new int[n];
    for (int j = 0; j < n; j++) {
        cin >> t;
        Q[j]=t;
    }
    for (int i = 0; i < n - 1; i++)
        if (!checkValidOrder(Q, i)) {
            cout << "No";
            break;
        }
    else cout << "Yes";
    delete[] Q;
}

（二）模拟栈的出入操作

我们可以对整个出入栈的过程进行模拟。

先假定给定的出栈序列是合法的且将出栈序列压入到一个队列当中。然后开始模拟入栈操作（即按照从1到n的次序入栈），当某个元素入栈后如果其编号等于队头元素编号则说明此元素应当进行出栈操作同时还要进行出队操作。如果到最后栈为空，则说明该出栈序列是合法的，否则为非法。

在算法实现方面，我们用队列存放待判定数列，并用栈模拟入栈出栈的步骤。该算法时间复杂度为O（n）。

具体程序如下：

#include<bits/stdc++.h>
using namespace std;

bool checkValidOrder(queue<int>& q)
{
stack<int> s;
int n = q.size();
for (int i = 1; i <= n; i++){
s.push(i);
//栈非空且栈顶元素等于队头元素，说明该元素需要出栈
while (!s.empty() && s.top() == q.front())
{
s.pop();
q.pop();
}
}
//栈为空说明出栈序列合法，否则非法
return s.empty() ? true : false;
}

int main() {
int n, t;
queue<int> Q;
cin >> n;
for (int j = 0; j < n; j++) {
cin >> t;
Q.push(t);
}
if (checkValidOrder(Q)) cout << "Yes";
else cout << "No";
}

（三）卡特兰数模型法

在 求入栈序列对应的所有的合法输出序列种数（一） 中，我们运用坐标系来表示入栈出栈操作，从而计算合法输出序列种数。本篇文章会采用类似的方法，进而发掘卡特兰数的坐标系模型在判断栈的输出序列是否合法中的应用。

模型详见：

求入栈序列对应的所有的合法输出序列种数（卡特兰数法）

在这里简单地给出模型的概述。

利用此方法来描述入栈与出栈的操作，在坐标系中具有一般性的规律。分别为：

在任意一次操作前，入栈次数始终小于等于出栈次数，即y≤x始终成立，所以路径一定始终在直线y=x下方。
在最后一步操作后，入栈次数一定等于出栈次数，所以路径的终点一定在直线y=x上

因此，合法输出序列对应的路径（简记为合法路径）一定是一条从(0,0)走到(n,n)且不跨越直线y=x的路径。

例如： (2,4,3,1,5,7,6)就是入栈序列(1,2,3,4,5,6,7)的合法出栈序列，因为其路径（如下图黄色线条所示）始终在直线y=x（蓝色线条）的下方

这条合法路径是我们通过坐标系得出的，那么反过来，如果我们也可以通过路径反推出坐标系的描述，那自然就可以验证此路径是否合法了。

下面来讨论如何把出栈序列对应到坐标系中。

我们仍然以出栈序列 (2,4,3,1,5,7,6) 为例，即分析从出栈序列导出上图的黄色路径的过程。

把出栈序列命名为A序列（其中A[0]=0），对于这个序列的每一个元素来说，其大小与其前一个元素的大小关系只有两种可能：大于或小于（即A[i]>A[i-1]或A[i]<A[i-1])。我们把这两种情况分别称为情况1和情况2，对于这两种情况，路径的变化也遵循着相应的规则。

情况1：A[i]>A[i-1],则路径末端点向右平移到A[i]处，之后再向上平移一个单位
情况2：A[i]<A[i-1],则路径末端点向上平移一个单位

按照这种描述，则出栈序列 (2,4,3,1,5,7,6)对应的情况分别为(1,1,2,2,1,1,2)，我们把情况1记为绿色线段，情况2记为橙色线段，则其对应着下图的路径描述。

利用情况1和情况2的规则构建出的路径，与原图中所给路径一样，而此路径不越过直线y=x，因此路径合法，即出栈序列 (2,4,3,1,5,7,6)合法。

这是一个从出栈情况导出路径描述的一种特殊情况，对于如何证明其一般性，我们要进一步分析情况1和情况2的具体含义。

情况1

对于情况1，A[i]>A[i-1]时，前A[i]个元素一定已经全部入栈（因为序列是逐个入栈的，每次入栈的元素都比前一个入栈的元素大），且A[i+1]及其之后的元素一定全部没有入栈（否则，若A[i+1]以后的某个元素入栈，这个元素一定在A[i]之前出栈，此时A[i]将会作为情况2处理）。

因此，此时入栈的情况一定是有且只有前A[i]个元素入栈，则此时路径末端的横坐标在A[i]处，表示执行了A[i]次入栈操作。因为出栈数列中第i个元素为元素A[i]，所以纵坐标+1，表示A[i]出栈。

情况2

对于情况2，A[i]<A[i-1]时,因为前A[i]个元素一定已经全部入栈的规律仍然成立，所以此时对于元素A[i-1]，一定已经在情况1中记录了它的入栈。这时只要记录其出栈就行了，也就是路径末端纵坐标+1，表示A[i]出栈。

总结一下：对于横坐标，A[i]>A[i-1]时，要表示前A[i]个元素都已入栈，则路径末端横坐标平移至A[i]；A[i]<A[i-1]时，那么其入栈已经被记录，所以不用平移。对于纵坐标，出栈序列中的每一个元素都对应这纵坐标+1，所以对于每次情况的判断后都将纵坐标+1。

下面把这个规律运用到算法实现中，即扫描整个出栈序列，对每个元素做情况1或情况2的判断，并执行相应的对路径末端点平移的操作。

如果每次操作后，路径末端点都满足x≥y，则该路径合法，否则路径非法。相应的，我们就解决了判断出栈序列是否合法的问题。

具体程序如下：

#include<bits/stdc++.h>
using namespace std;

bool checkValidOrder(int A[],int n)
{
    int x = 0, y = 0;
    for (int i = 1; i < n; i++) {
        if (A[i] > A[i - 1]) x = A[i], y++;      //情况1
        if (A[i] < A[i - 1]) y++;                //情况2
        if (y > x) return false;                 //路径越过了直线y=x，则为非法路径
    }
    return true;
}

int main() {
    int n, t;
    cin >> n;
    int* A = new int[n + 1];  //用数组A存放输入的出栈序列
    A[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> t;
        A[i] = t;
    }
    if (checkValidOrder(A,n)) cout << "Yes";
    else cout << "No";
}

给出栈的合法输出序列的规律

在前文中我们已提到，可以将入栈元素按入栈顺序由1到n进行编号，对于入栈序列1到n，第x个数入栈时，那么前x-1个数一定已经全部入栈。则当第x个数出栈时，栈中若剩余编号小于x元素，则这些元素一定在存储器中倒序排列。

这个结论还可以用更加严谨的过程来证明[9]，即假设在出栈过程中的某一个步骤时，栈中存留的元素有n个，分别是S1到Sn。

此时，对于元素 Sn，有两种可能性。

在下一步时，可以选择弹出Sn。那么，比Sn小的所有元素，只有两种可能：

a. 还未出栈（不可能还未入栈，因为比它大的元素Sn已经入栈了）：则一定在Sn后以递减的顺序出现在出栈队列中（因为入栈的顺序是严格递增的）

b. 已经出栈：此时，比这个元素还小的元素如果还没出栈，当它即将出栈的时候，就会又递归回到1）的情况。

可以不弹出Sn而是继续入栈，则又回到 1）的情况。

因此，我们得出这样的结论： 凡是合法的出栈序列，每个数后面的比它小的数，必然是按递减次序排列的 。

利用这个理论，我们可以较快地判断所含元素较少的栈的输出序列是否合法。

拓展

对于2.2的问题，我们对输入的序列有较严格的要求，即输入序列为f(n)=n的数组。但对于更一般的情况，原来的一系列结论是否成立，需要我们进一步地探究。

我们先把原情况中的f(n)=n改成非等差但严格单调递增的数列，即下述问题

对一个栈的输入序列a1,a2,a3,… ,an,称由此栈依次出栈后所得到的元素序列为栈的合法输出序列（满足a1<a2<…<an）

例如，假设栈S的一个输入序列为1,3,4,6,7则可得到多个输出序列分别求解下列问题：

（1）求出其所有的合法的输出序列

（2）判断栈的输出数列是否合法

对于因为栈的合法的输出序列规律是对数列的序号而言的，所以一定始终成立，这里不再赘述。

（1）中理论仍然成立，因为（1）的证明并没有用到数列等差的前提条件。

对于（2）而言，模拟法一定成立。逆序法需要修改函数体，但因为输入数列仍满足单调递增条件，所以此方法仍然成立。

因此，我们得出结论：2所述方法对满足a1<a2<…<an的输入序列仍然成立。

更一般性的问题，若a1,a2…an无序且存在重复元素，则这些理论则需要重新修正。

在这里我们给出（2）问的拓展形式：

题目描述:

给出两个序列 pushed 和 poped 两个序列，其取值从1到 n(n≤100000)。已知入栈序列是 pushed，如果出栈序列有可能是 poped，则输出 Yes，否则输出 No。

输入格式

第一行一个整数 n 表示序列长度；
第二行 n个整数表示入栈序列；
第三行 n个整数表示出栈序列；

输出格式

输出答案（Yes/No）

题目详见https://www.luogu.com.cn/problem/P4387

与原先的情况相比，本题的入栈序列更具一般化，从等差递增数列变成了任意数列。我们仍然尝试用模拟法解决此问题，则需要考虑题目变化可能带来的影响。

变化1：数列元素的乱序性

我们假设数列中没有重复元素，则使用模拟法时，入栈序列的每一个元素和其序号之间构成唯一的相互映射。因此，我们可以用map记录栈中元素与序号的映射，并用模拟法加以解决。

具体程序如下：

#include<bits/stdc++.h>
using namespace std;

map<int, int> Num;
bool checkValidOrder(queue<int>& q,int *S)
{
    stack<int> s;
    int n = q.size();
    for (int i = 0; i < n; i++) {
        s.push(Num[S[i]]);
        while (!s.empty() && s.top() == q.front())
        {
            s.pop();
            q.pop();
        }
    }
    return s.empty() ? true : false;
}

int main() {
    int n, t;
    queue<int> Q;
    cin >> n;
    int* S = new int[n + 1];
    for (int i = 0; i < n; i++) {
        cin >> t;
        pair<int, int> p; 
        p.first = t;
        p.second = i;
        Num.insert(p);
        Q.push(Num[t]);
    }
    for (int i = 0; i < n; i++) cin >> S[i];
    if (checkValidOrder(Q,S)) cout << "Yes";
    else cout << "No";
    delete[] S;
}

通过此程序可以看出，当入栈序列乱序但元素无重复时，构建map<元素，序号>可以把这个特殊情况还原为原先的问题。

变化2：数列元素的重复性（且在乱序的基础上）

入栈序列最一般的形式即为乱序且可能重复，此时采用判断局部出栈序列是否逆序的方法显然不可行了。这时候我们考虑的模拟法仍然成立，模拟法具有一般性。

总结与展望

本篇讨论一共从三个角度对栈的合法输出序列进行了分析，分别是求入栈序列对应的所有合法出栈序列；判断栈的输出序列是否合法和探究栈的合法输出序列的一般性规律。在探究过程中，我们运用了栈、数列、树等数据结构，并结合卡特兰数在数据结构中的应用给出了一些相关结论。

在本篇讨论中，出栈序列的所有可能性只针对不含重复元素的入栈序列。那对于含有重复元素的数列，其规律是否仍然成立，则需要我们在后续学习中继续探究。

参考文献

1.CSDN博主「syzdev」的原创文章《关于出栈序列，判断合法的出栈序列》，原文链接：https://blog.csdn.net/syzdev/article/details/7849254

2.卢开澄，卢华明．组合数学：清华大学出版社，2006

3.CSDN博主「zz198808」的原创文章《给定一个入栈序列，求所有可能的出栈序列》，原文链接：https://blog.csdn.net/zz198808/article/details/7585385

4.CSDN博主「fanmingleia」的原创文章《n个节点的二叉树有多少种形态》，原文链接：https://blog.csdn.net/iG_xdd/article/details/79808519

5.知乎答主「brucewall」（原名闵家兴）的原创答复，原文链接：https://www.zhihu.com/question/58529163/answer/872599940

6.CSDN博主「Boss_Song」的原创文章《回溯法输出所有出栈序列》，原文链接：https://blog.csdn.net/M_P_S/article/details/86062716

7.CSDN博主「Zee_Chao」的原创文章《检验合法的出栈序列（C++）》，原文链接：https://blog.csdn.net/Zee_Chao/article/details/89971101

8.CSDN博主「Arvid Y」的原创文章《判断是否是合法的出栈序列（详细》，原文链接：https://blog.csdn.net/weixin_44489823/article/details/101164695

9.CSDN博主「Dark-Rich」的原创文章《栈的合法输出序列的数学证明》，原文链接：https://blog.csdn.net/tlzhatao/article/details/14052141

10.洛谷作者「深入浅出」上传题目《P4387 【深基15.习9】验证栈序列》，原题链接https://www.luogu.com.cn/problem/P4387

11.数据结构：C++描述/胡学钢，张晶主编.一北京人民邮电出版社，2011.8

栈的合法序列的讨论

引例

问题描述

求入栈序列对应的所有的合法输出序列种数

（一） 数学模型（卡特兰数理论）

<1>. 出栈和入栈次数均为n次的情况（不考虑出栈次数>入栈次数的可能性）

<2>. 出栈和入栈次数均为n次的情况（只考虑出栈次数>入栈次数的情况）

（二） 算法实现Ⅰ（组合数学理论）

（三） 算法实现Ⅱ（二叉树理论）

（四） 算法实现Ⅲ（回溯法）

判断栈的输出序列是否合法

（一） 检查数列的局部单调性

凡是合法的出栈序列，每个数后面的比它小的数，必然是按递减次序排列的。

（二） 模拟栈的出入操作

（三） 卡特兰数模型法

求入栈序列对应的所有的合法输出序列种数（卡特兰数法）

情况1

情况2

给出栈的合法输出序列的规律

拓展

题目详见https://www.luogu.com.cn/problem/P4387

总结与展望

参考文献

完结撒花~

（一）数学模型（卡特兰数理论）

（二）算法实现Ⅰ（组合数学理论）

（三）算法实现Ⅱ（二叉树理论）

（四）算法实现Ⅲ（回溯法）

（一）检查数列的局部单调性

（二）模拟栈的出入操作

（三）卡特兰数模型法