题解 | 验证栈序列

#include <iostream>
#include <stack>
using namespace std;
//  入栈序列能等于出栈序列，输出是否;入栈序列一个个入栈，并于出栈序列比较，如果于出栈序列相等则出栈，循环语句，入栈前一个元素与下一个 出栈元素相等，则出栈，继续到没有元素出栈，把入栈输出，与出栈比较，不等则否
const int MAXN = 100005;
int main() {
    int q, n;
    int pushed[MAXN], popped[MAXN] ;
    stack<int> st;

    cin >> q;
    while( q--) {
    	while(!st.empty()) st.pop(); //这里多次输入，需要确保栈空
        int k = 0,flag = 0  ;
        cin >> n;
        for (int i = 0; i< n; i++)
            cin>> pushed[i];
         for (int i = 0; i< n; i++)
            cin>> popped[i];
         for (int i = 0; i< n; i++){
             int temp = pushed[i];
             st.push(temp);
             int top = st.top();
         while(top == popped[k]){
                st.pop();
                k++;
            if(!st.empty()) top = st.top();
         }
         }
         //栈中剩余元素，与popped出栈元素比较
         while(!st.empty()){
            if(st.top() == popped[k++]){
                st.pop();
            } else{
                flag = 1;
                break;
            }
         }
         if( flag == 1) cout << "No";//当flag为1是不匹配
         else cout << "Yes";
         cout << endl;
    }
}
// 64 位输出请用 printf("%lld")