//合法的出栈队列 //已知从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; }