poj 1363:火车合法的出栈次序——合法的出栈次序

    技术2025-05-04  17

    #include <stdio.h> #include <stack> #include <queue> bool check_is_valid_order(std::queue<int> &order){ std::stack<int> S;//临时栈 int n = order.size();//获得测试队列,即出栈次序的长度 for (int i = 1; i <= n; i++){ S.push(i);//将1,2,3,4,5,6,7,8......入栈 while(!S.empty() && order.front() == S.top()){//如果栈S不为空,且 测试队列的头 == 栈顶 S.pop();//栈顶和队列头同时弹出 order.pop(); } } if (!S.empty()){//如果栈S不为空,说明测试队列的次序 不满足合法出栈次序 return false; } return true; } int main(){ int n; int train; scanf("%d", &n); while(n){ scanf("%d", &train); while (train){ std::queue<int> order; order.push(train); for (int i = 1; i < n; i++){ scanf("%d", &train); order.push(train); } if (check_is_valid_order(order)){ printf("Yes\n"); } else{ printf("No\n"); } scanf("%d", &train); } printf("\n"); scanf("%d", &n); } return 0; }

     

     

     

     

     

     

     

     

     

     

    Processed: 0.010, SQL: 9