Pop Sequeue
题目描述
Given a stack which can keep M numbers at most. Push N numbers in the order of 1,2,3...,N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1,2,3,4,5,6,7 from the stack, but not 3,2,1,7,5,6,4.
输入格式
Each input file contains one test case. For each case, the first line contains 3 numbers(all no more than 1000): M(the maximum capacity of the stack), N(the length of push sequence), and K(the number of pop sequence to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.
输出格式
For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if else.
输入样例
5 7 3
1 2 3 4 5 6 7
3 2 1 7 5 6 4
5 6 4 3 7 2 1 输出样例
YES
NO
YES
题意
有一个容量限制为M的栈,先分别把1,2,3,n依次入栈,并给出一系列出栈顺序,问这些出栈顺序是否可能?
思路
按照题目的要求进行模拟,将1~n依次入栈,在入栈的过程中如果入栈的元素恰好等于出栈序列当前等待出栈的元素,那么就让栈顶元素出栈,同时把出栈序列当前等待出栈的元素位置标记后移1位。此时只要栈顶元素依然等于出栈序列当前等待出栈的元素,则继续出栈。
代码
1 #include<iostream>
2 #include<stack>
3 using namespace std;
4 const int maxn = 1010;
5 int arr[maxn]; //保存题目给的出栈序列
6 stack<int> st; //定义栈st,用以存放int型元素
7 int main()
8 {
9 int m, n, T;
10 cin>>m>>n>>T;
11 while(T--){ //循环T次
12 while(!st.empty()) //清空栈
13 st.pop();
14 for(int i=1;i<=n;i++) //读入数据
15 cin>>arr[i];
16 int current = 1; //指向出栈序列中的待出栈元素
17 bool flag = true;
18 for(int i=1;i<=n;i++){
19 st.push(i); //把i压入栈
20 if(st.size()>m){ //如果此时栈中元素个数大于容量m,则序列非法
21 flag=false;
22 break;
23 }
24 //栈顶元素与出栈序列当前位置的元素相同时
25 while(!st.empty()&&st.top()==arr[current]){
26 st.pop(); //反复弹栈并令current++
27 current++;
28 }
29 }
30 if(st.empty()==true&&flag==true){
31 cout<<"TES"<<endl;
32 }
33 else{
34 cout<<"NO"<<endl;
35 }
36 }
37 return 0;
38 }
最新文章
- WCF初探-28:WCF中的并发
- 岁末年初3Q大战惊现高潮,360震撼推出Android ";3Q"; IM即时通讯
- vpn establish capability from a remote deskstop is disabled错误的解决办法
- js 0.1+0.2!=0.3
- mysql和oracle的区别(功能性能、选择、使用它们时的sql等对比)
- git 新建分支/切换分支/合并分支 使用方法
- 【Gym 100685J】Just Another Disney Problem(交互/排序)
- Linux命令行下创建纳入版本控制下的新目录
- 【转】cocos2d-x 模仿计时器效果,动态增加分数&mdash;&mdash;2013-08-25 16
- 【Ruby on Rails学习二】在线学习资料的整理
- 黄聪:Microsoft Enterprise Library 5.0 系列教程(十) Configuration Application Block
- SoccerLeagueDB
- JNI调用问题(部分机型崩溃)
- vpx
- 第15课 右值引用(2)_std::move和移动语义
- 基于拖放布局的 Twitter Bootstrap 网站生成器
- mocha测试接口类型及测试报告收集
- Android studio实现简单的CRUD
- UVALive 4764 dp
- 【原】SPARK_MEM和SPARK_WORKER_MEMORY的区别
热门文章
- 一文详解 纹理采样与Mipmap纹理——构建山地渲染效果
- 安装火狐浏览器报错找不到VCRUNTIME140_1.DLL
- ciscn_2019_s_4***(栈迁移)
- 在对话框中设置前置任务(Project)
- SpringSecurity自定义注解和处理器
- 分布式系统一致性算法(Raft)
- JAVA中数组(Array)、字符串(String)、集合(List、Set)相互转换
- 【LeetCode】1418. 点菜展示表 Display Table of Food Orders in a Restaurant
- 【Leetcode】718. 最长重复子数组
- uniapp h5中解决跨域问题