2020考研-王道数据结构-栈和队列-栈和队列的应用

ゝ一世哀愁。 2022-01-29 09:15 360阅读 0赞

# 第一题 #

##### 题目简述 #####

括号匹配问题。给定一个只包含\{、【、（、）、】、\}的括号序列，判断这个序列是否合法。

##### 题目思路 #####

这四个题目，第一题和第三题比较重要，对于二和四是纯模拟题目。括号匹配问题是典型的栈的应用。思路是当遇到左括号时入栈，遇到右括号时，出栈，出栈的时候需要判断栈顶的左括号和我当前的右括号是否匹配，如果匹配则继续判断下一个，不匹配的话直接得出结论，括号序列不匹配，直至括号序列判断到结尾。

##### 代码 #####

#include <iostream>
    #include <stack>
    
    using namespace std;
    
    const int N = 200; // 字符串的最大长度
    char str[N];
    
    bool judge()
    {
        
    	stack<char> stk;
    	for (int i = 0; str[i]; i++)
    	{
        
    		switch (str[i])
    		{
        
    		case '(':stk.push('('); break;
    		case '[':stk.push('['); break;
    		case '{':stk.push('{'); break;
    		case ')':{
        
    			if (!stk.size() || stk.top() != '(') return false;
    			stk.pop();
    			break;
    		}
    		case ']':{
        
    			if (!stk.size() || stk.top() != '[') return false;
    			stk.pop();
    			break;
    		}
    		case '}':{
        
    			if (!stk.size() || stk.top() != '{') return false;
    			stk.pop();
    			break;
    		}
    		default:
    			break;
    		}
    	}
    	return true;
    }
    
    int main()
    {
        
    	while (true)
    	{
        
    		cin >> str;
    		if (judge()){
        
    			cout << "匹配" << endl;
    		}
    		else
    		{
        
    			cout << "不匹配" << endl;
    		}
    	}
    }

# 第二题 #

##### 题目简述 #####

火车道路上有n节车厢，这n节车厢中分为硬卧车厢用H表示，软卧车辆用S表示，现在给你一个只包含H、S的序列，通过栈操作，使所有的硬卧车厢排列在软卧车厢之后。

##### 代码 #####

#include <iostream>
    #include <stack>
    
    using namespace std;
    
    const int N = 200; // 字符串的最大长度
    
    char str[N];
    
    // 利用栈调整列车，遇见硬卧车辆入栈，最后再把硬卧车辆加进火车列
    void calc()
    {
        
    	stack<int> stk;
    	for (int i = 0; str[i]; i++)
    	{
        
    		if (str[i] == 'H') stk.push(i);
    		else cout << i << " ";
    	}
    	while (stk.size()){
        
    		cout << stk.top() << " ";
    		stk.pop();
    	}
    	cout << endl;
    }
    
    int main()
    {
        
    	while (cin >> str)
    	{
        
    		calc();
    	}
    	return 0;
    }

# 第三题 #

##### 题目简述 #####

利用栈实现递归计算  
 P n ( x ) = \{ 1 , n = 0 2 x , n = 1 2 x P n − 1 ( x ) − 2 ( n − 1 ) P n − 2 ( x ) , n > 1 P\_n(x)= \\begin\{cases\} 1, & \\text \{n = 0\} \\\\ 2x, & \\text\{n = 1\}\\\\2xP\_\{n-1\}(x) - 2(n-1)P\_\{n-2\}(x) ,&\\text\{n > 1\} \\end\{cases\} Pn(x)=⎩⎪⎨⎪⎧1,2x,2xPn−1(x)−2(n−1)Pn−2(x),n = 0n = 1n > 1

##### 题目思路 #####

感觉有点为了用栈而用栈的意思了，其实大家的思路就是，从第三项一直递推到第n项，我当时也是这么写的代码，我不知道这和栈有啥关系，感觉完全没必要用上栈，答案中的代码也是，感觉没必要用上栈。

##### 代码 #####

#include <iostream>
    #include <algorithm>
    #include <stack>
    
    using namespace std;
    
    struct Node
    {
        
    	int val;
    	int n;
    
    	Node(int tval, int tn) :
    		val(tval), n(tn)
    	{
        };
    };
    
    // 利用栈模拟递归，假设p1 到pn全部已经计算出来
    int P(int n,int x)
    {
        
    	if (n == 0) return 1;
    	if (n == 1) return x << 1;
    	stack<Node> stk;
    
    	int f0 = 1, f1 = x << 1;
    	for (int i = n; i >= 2; i--){
        
    		stk.push(Node(0, i));
    	}
    	while (stk.size())
    	{
        
    		Node node = stk.top();
    		stk.pop();
    		node.val = (x << 1) * f1 - ((node.n - 1) << 1) * f0;
    		f0 = f1;
    		f1 = node.val;
    	}
    	return f1;
    }
    
    int main()
    {
        
    	int n, x;
    	while (cin >> n >> x)
    	{
        
    		cout << "P(" << n << "," << x << ")=" << P(n, x) << endl;
    	}
    	return 0;
    }

# 第四题 #

纯模拟问题代码可以写，但没必要，/哈哈哈

##### 题目简述 #####

模拟一个区汽车轮渡口的调度系统，规定调度口只有两类车【客车】和【货车】。规定，一艘船的容量为10辆车，并且客车先于货车上船，并且每上4辆客车就上一辆货车，若客车不足4辆，就把剩余货车上船。