《数据结构》02-线性结构4 Pop Sequence

谁借莪１个温暖的怀抱￠ 2022-05-04 14:28 181阅读 0赞

# 题目 #

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.

**Input Specification:**  
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 sequences 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.

**Output Specification:**  
For each pop sequence, print in one line “YES” if it is indeed a possible pop sequence of the stack, or “NO” if not.

**Sample Input:**

> 5 7 5  
> 1 2 3 4 5 6 7  
> 3 2 1 7 5 6 4  
> 7 6 5 4 3 2 1  
> 5 6 4 3 7 2 1  
> 1 7 6 5 4 3 2

**Sample Output:**

> YES  
> NO  
> NO  
> YES  
> NO

# 分析 #

题目大意就是一个容量限制为 m 的栈，一组数 1,2,3,…,n 顺序入栈，随机出栈，问出栈序列是否可能  
刚开始想的是找出一组规律，根据规律判断该出栈顺序是否合理，找着找着规律好像不太好找，索性进行模拟  
使用 v 数组存储输入序列，定义栈 s，让 1,2,…n 顺序入栈，定义 cur 指示当前 v 数组下标， 当 v\[cur\] 等于栈顶元素（s.top()）且栈 s 不为空，不断出栈且 cur+1 直到不等为止，当 1…n 入栈结束，或者栈 s 已满，退出入栈循环，最后判断 cur 与 n 的大小关系决定该顺序是否可能  
比如例序列 5 6 4 3 7 2 1，此时 m = 5，即栈的最大容量为 5

<table> 
 <thead> 
  <tr> 
   <th>当前入栈元素</th> 
   <th>栈 s</th> 
   <th>v 数组</th> 
   <th>cur</th> 
   <th>v[cur]</th> 
   <th>出栈</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>1</td> 
   <td>5 6 4 3 7 2 1</td> 
   <td>1</td> 
   <td>5</td> 
   <td>无</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1 2</td> 
   <td>5 6 4 3 7 2 1</td> 
   <td>1</td> 
   <td>5</td> 
   <td>无</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>1 2 3</td> 
   <td>5 6 4 3 7 2 1</td> 
   <td>1</td> 
   <td>5</td> 
   <td>无</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>1 2 3 4</td> 
   <td>5 6 4 3 7 2 1</td> 
   <td>1</td> 
   <td>5</td> 
   <td>无</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>1 2 3 4 5</td> 
   <td>5 6 4 3 7 2 1</td> 
   <td>1</td> 
   <td>5</td> 
   <td>5</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>1 2 3 4 6</td> 
   <td>5 6 4 3 7 2 1</td> 
   <td>2</td> 
   <td>6</td> 
   <td>6</td> 
  </tr> 
  <tr> 
   <td>无</td> 
   <td>1 2 3 4</td> 
   <td>5 6 4 3 7 2 1</td> 
   <td>3</td> 
   <td>4</td> 
   <td>4</td> 
  </tr> 
  <tr> 
   <td>无</td> 
   <td>1 2 3</td> 
   <td>5 6 4 3 7 2 1</td> 
   <td>4</td> 
   <td>3</td> 
   <td>3</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>1 2 7</td> 
   <td>5 6 4 3 7 2 1</td> 
   <td>5</td> 
   <td>7</td> 
   <td>7</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>1 2</td> 
   <td>5 6 4 3 7 2 1</td> 
   <td>6</td> 
   <td>2</td> 
   <td>2</td> 
  </tr> 
  <tr> 
   <td>1</td> 
   <td>1</td> 
   <td>5 6 4 3 7 2 1</td> 
   <td>7</td> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
 </tbody> 
</table>

#include<iostream>
    #include<vector>
    #include<stack>
    using namespace std;
    int main(){
        
    	int m,n,k;
    	cin>>m>>n>>k;
    	for(int i=0;i<k;i++){
        
    		stack<int> s;
    		vector<int> v(n + 1);
    		for(int j=1;j<=n;j++)
    			cin>>v[j];
    		int cur=1;
    		for(int j=1;j<=n;j++){
        
    			s.push(j);
    			if(s.size() > m)
    				break;
    			while(!s.empty() && s.top()==v[cur]){
        
    				s.pop();
    				cur++;
    			}
    		}
    		if(cur == n+1)
    			cout<<"YES"<<endl;
    		else
    			cout<<"NO"<<endl;
    	}
    	return 0;
    }