C++之栈的应用-------判断出栈序列是否合法

//合法的出栈队列
//已知从1至n的数字序列，按顺序入栈，每个数字入栈后即可出栈，也可在栈中停留，
//等待后面的数字入栈出栈后，该数字在出栈，求该数字序列的出栈序列是否合法
#include<iostream>
#include<stack>
#include<queue>
using namespace std;

/*
数字序列的合法出栈序列特点，设出栈序列为int a[] = {1,2,3,....i}，其中a[i-1]是最后出栈的元素；如a[]是合法的出栈序列，则应该满足如下条件之一
1.a[i]>a[i-1] 
或
2.当a[i]<a[i-1]时,
    1)若a[i]+1=a[i-1]，a[0]至a[i]之间的出栈序列合法
    2）若a[i]+1<a[i-1]，则a[i]+1至a[i-1]-1的数字需要在a[i-1]之前弹出
*/

//利用数组实现
//很复杂，最差的情况下算法复杂度为O(n^2)
bool isStackSequeue(const int *a,int n) {
    bool  validate = true;
    //从出栈序列的第二个数开始,到出栈序列的倒数第三个数结束
    for (int i = 1; i < n; i++) {
        if (i == n - 1) {
            //出栈序列合法，终止循环
            break;
        }
        //如果当前出栈元素a[i]在原始队列[1:n]中排在前一个元素的后面
        if (a[i] > a[i - 1]) {
            continue;
        }
        if (a[i] < a[i - 1]) {
            //如果当前的出栈元素比前一个出栈元素小一,则a[0]:a[i]的出栈顺序合法
            if (a[i] + 1 == a[i - 1]) {
                continue;
            }
            //如果当前出栈元素a[i]与前一个出栈元素a[i-1]在原始队列相隔多个元素
            //判断两者之间间隔的元素是否在前一个出栈元素之前出栈了
            if (i - 2 + 1 < a[i - 1] - a[i] - 1) {
                //a[i]:a[i-1]之间的元素并没有完全出栈，说明出栈队列不对
                validate = false;
                break;
            }
            //遍历a[i]:a[i-1]之间的元素a[i]+1:a[i-1]-1,观察它们是否在a[i-1]之前出栈了
            for (int m = a[i] + 1; m < a[i - 1]; m++) {
                //判断在a[i]+1至a[i-1]-1的元素m是否在a[i-1]之前出栈了
                for (int j = 0; j < i - 1; j++) {
                    //如果元素m没有在a[i-1]之前出栈，则出栈队列不合法
                    if (j == i - 2) {
                        if (a[j] == m) {
                            break;
                        }
                        return false;
                    }
                    //元素m在a[i-1]之前出栈了，继续判断m+1是否也出栈了
                    if (a[j] == m)
                        break;
                }
            }
        }
    }
    return validate;
}

//利用栈实现
//算法复杂度为O(2n) ,只有n个元素进栈出栈（只统计元素进栈和出栈的次数）
bool isStackSequeue2(const int* a, int n) {
    stack<int> s;
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            //当a[i]==1时，模拟数字1的入栈出栈
            if (a[i] == 1) {
                s.push(1);
                s.pop();
            }
            //当a[i]>1时，模拟1:a[i]之前数字的入栈
            else {
                for (int j = 1; j <= a[i]; j++)
                    s.push(j);
                //a[i]元素出栈
                s.pop();
            }
        }
        else {
            //如果当前元素a[i]比前一个元素a[i-1]大，则将a[i-1]:a[i]之间的元素压入栈
            if (a[i] > a[i - 1]) {
                for (int m = a[i - 1] + 1; m <= a[i]; m++)
                    s.push(m);
                //a[i]元素出栈
                s.pop();
            }
            //如果当前元素a[i]比a[i-1]小，则弹出s的栈顶元素，比较s.top()与a[i]的大小
            else {
                //当前a[i]元素出栈顺序合法
                if (s.top() == a[i]) {
                    s.pop();
                    //进入下一个循环，验证a[i+1]元素
                    continue;
                }
                //出栈队列不合法
                return false;
            }

        }
    }
    return true;
}
//利用栈和队列实现 模拟出栈队列
//算法复杂度为O(3n)，只统计进栈和出栈的次数
bool isStackSequeue3(queue<int> order) {
    stack<int> s;
    int n = order.size();
    for (int i = 1; i <= n; i++) {
        s.push(i);
        while (!s.empty()&&s.top() == order.front()) {
            s.pop();
            order.pop();
        }
    }
    if (!order.empty()) {
        return false;
    }
    return true;
}

int main() {
    int n;
    cout << "请输入数字序列的个数n:";
    cin >> n;
    int train = 1;
    int* a;
    while (n) {
        a = new  int[n];
        queue<int> q;
        
        while (train)
        {
            cout << "请输入出栈序列：";
            for (int i = 0; i < n; i++) {
                cin>>train;
                a[i] = train;
                q.push(train);
            }
            cout << "isStackSequeue:"  << isStackSequeue(a, n) << endl;
            cout << "isStackSequeue2:" << isStackSequeue2(a, n) << endl;
            cout << "isStackSequeue3:" << isStackSequeue3(q) << endl;
            cout << "是否继续(0:退出，1：继续)：";
            cin>>train;
        }
        delete[] a;
        cout << "请输入序列的个数n(输入0退出):";
        cin>>n;

    }

    return 0;
}