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

第一题

题目简述

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

题目思路

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

代码

#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;
}