进入和输出的数组为order1，和order2,。当栈为空或者栈顶元素！=order2[i],则入栈，且队列进“in”。否则,即栈不为空且栈顶元素与order[i]相等，则出栈，队列进“out”。
不断进行上面2个判断，直至两个数组遍历完，或者在中途中达不到目标顺序，使程序停止。
结果为“NO”的结束条件是，当栈为空或者栈顶元素！=order2[i]时，数组order1已经遍历了即j==n时，表示出栈顺序不一致。
代码1：使用容器stack和queue
1 #include<iostream> 2 #include<stdio.h> 3 #include<string> 4 #include<string.h> 5 #include<algorithm> 6 #include<math.h> 7 #include<vector> 8 #include<stack> 9 #include<queue> 10 using namespace std; 11 int n; 12 int i,j; 13 char order1[12],order2[12]; 14 void cal() 15 { 16 stack<int>st; 17 queue<string>q; 18 for(i=0,j=0;i<n&&j<=n;)// j可以为n,作为判断结束的条件 19 { 20 if(st.empty()||st.top()!=order2[i]) 21 { 22 if(j==n) 23 { 24 cout<<"No."<<endl<<"FINISH"<<endl; 25 return ; 26 } 27 st.push(order1[j++]); 28 q.push("in"); 29 } 30 else 31 { 32 st.pop(); 33 q.push("out"); 34 i++; 35 } 36 } 37 cout<<"Yes."<<endl; 38 string ch; 39 while(!q.empty()) 40 { 41 ch=q.front(); //q.front返回的是对头元素的引用，是地址 42 cout<<ch<<endl;//输出的是字符串ch，ch为字符串数组的首地址 43 q.pop(); 44 45 } 46 cout<<"FINISH"<<endl; 47 } 48 49 int main() 50 { 51 while(cin>>n) 52 { 53 cin>>order1>>order2; 54 cal(); 55 56 } 57 58 return 0 ; 59 }
代码二：使用容器vector
区别在于输出“in”和“out”是用标记输出的，而没有用队列方便
1 #include<iostream> 2 #include<stdio.h> 3 #include<string> 4 #include<string.h> 5 #include<algorithm> 6 #include<math.h> 7 #include<vector> 8 #include<stack> 9 #include<queue> 10 #define N 12 11 #define IN 0 12 #define OUT 1 13 using namespace std; 14 15 char o1[N],o2[N]; 16 int seq[N*2]; 17 int n; 18 int idx; 19 bool cal() 20 { 21 vector<char> V; 22 int i,j; 23 for(i=0,j=0;i<n&&j<=n;) 24 { 25 if(V.empty()||V.back()!=o2[i]) 26 { 27 if(j==n) 28 { 29 return 0; 30 } 31 V.push_back(o1[j++]); 32 seq[idx++]=IN; 33 34 } 35 else 36 37 { 38 V.pop_back(); 39 seq[idx++]=OUT; 40 i++; 41 } 42 } 43 return 1; 44 45 } 46 47 int main() 48 { 49 50 while(cin>>n) 51 { 52 idx=0; 53 cin>>o1>>o2; 54 if(cal()) 55 { 56 cout<<"Yes."<<endl; 57 for(int i=0;i<n*2;i++) 58 { 59 if(seq[i]) 60 cout<<"out"<<endl; 61 else 62 cout<<"in"<<endl; 63 } 64 65 } 66 else 67 { 68 cout<<"No."<<endl; 69 } 70 cout<<"FINISH"<<endl; 71 } 72 return 0 ; 73 }
一：
vector类常用函数如下：
1，构造函数 vector();
2,增加函数 push_back(x),向量尾部增加一个元素x。
3，删除函数 pop_back()，删除向量最后一个元素。clear（），删除所有元素。
4，遍历函数
reference back()，返回尾元素的引用。
reference front(),返回首元素的引用。
5，判断函数 bool empty(),向量是否为空。
6，大小函数 size()
7,其他 函数 swap(),交换两个同类型向量的数据。
二：
队列和堆栈
1，构造函数，queue(),stack();
2,队列和堆栈共有函数
bool empty(),
int size();
push(x); 将x压入队尾（栈顶）；
pop(),当队列（栈）非空，删除队头（栈顶）元素。
3遍历函数
队列独有 为 front(),返回队头元素引用，back（），返回队尾元素引用。
堆栈独有为 top（），返回栈顶元素的引用。
原文：http://www.cnblogs.com/zn505119020/p/3561825.html