(PAT) 1051 Pop Sequence

怼烎@ 2022-05-11 06:28 225阅读 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 ###

求解思路:

我们可以定义一个辅助栈,用来执行进栈操作和出栈操作

然后定义一个bool型flag用来做标记

假设输入的有序 数列是 1 2 3 4 5 无序数列是 3 2 4 1 5

我们将有序数列的头部和无序数列的头部进行比较(定义两个数组指针可以用来进行遍历数组)

### 1 2 3 4 5 ###

### 3 2 4 1 5 ###

这里我们可以看到1小于3 我们将1入栈,指针++到2,依然小于3,继续入栈,指针++移动到3,此时相等了

这时,我们将指针++到4后退出入栈循环

(注意,要随时进行检测,如果栈容量大于最大容量的话,直接退出循环并令flag=false

之后将无序数列与栈顶比较,如果相等,则出栈,移动无序数列的指针到下一位后,继续进行比较

### 小于栈顶的话,分两种情况讨论 ###

情况(1) : 栈顶下方还有元素:此时将有序数列中的当前所指元素入栈并移动指针

情况(2): 栈顶下方没有元素了: 直接判定位false 退出

代码:

#include <iostream>
    #include <stack>
    using namespace std;
    
    bool legalSquence(int maxSize, int n) {
    
    	stack<int> mmStack;  //辅助栈
    	bool flag = true;
    	int positive_squence[1000] = { 0 };
    	int mass_squence[1000] = { 0 };
    
    	//元素输入部分
    	for (int i = 0; i < n; ++i) {
    		positive_squence[i] = i + 1;
    		cin >> mass_squence[i];
    	}
    
    	int positive_itr = 0;
    	int mass_itr = 0;
    
    	while (mass_itr < n) {
    
    		if (flag == false) {
    			break;
    		}
    
    		while (positive_itr < n && positive_squence[positive_itr] <= mass_squence[mass_itr]) {   //有序与无序的比较
    			mmStack.push(positive_squence[positive_itr]);
    			positive_itr++;
    			if (mmStack.size() > maxSize) {  //栈是否已满?退出:不退出;
    				flag = false;
    				break;
    			}
    		}
    		while (!mmStack.empty()) {
    			if (mmStack.top() == mass_squence[mass_itr]) {   //是否等于栈顶元素?
    				mmStack.pop();   //弹出
    				mass_itr++;
    			}
    			else if (mmStack.top() < mass_squence[mass_itr]) {   //特殊情况:下面还有元素
    				mmStack.push(positive_squence[positive_itr]);
    				positive_itr++;
    				if (mmStack.size() > maxSize) {
    					flag = false;
    					break;
    				}
    			}
    			else {    //特殊情况,下方没有元素
    				flag = false;
    				break;
    			}
    		}
    	}
    	return flag;
    }
    
    int main() {
    
    
    	int maxSize = 0;  //栈的容量
    	cin >> maxSize;
    	int n = 0;        //输入的序列长度
    	cin >> n;    
    	int testSeriesInd = 0;  //要检测的序列数
    	cin >> testSeriesInd;
    
    	bool Series[100] = { 0 };
    
    	for (int i = 0; i < testSeriesInd; ++i) {
    		bool flag = legalSquence(maxSize, n);
    		Series[i] = flag;
    	}
    
    	for (int i = 0; i < testSeriesInd; ++i) {
    		if (Series[i] == true) {
    			cout << "YES" << endl;
    		}
    		else {
    			cout << "NO" << endl;
    		}
    	}
    
    	return 0;
    }