机试第5章

约瑟夫问题变体（队列解法）

用队列模拟循环队列

int n, p, m;
cin >> n >> p >> m;
queue<int> q;
for (int i = 1; i <= n; ++i)
    q.push(i);
for (int i = 1; i < p; ++i) // 让p号位于队首
{
    q.push(q.front());
    q.pop();
}

while (!q.empty())
{
    for (int i = 1; i < m; ++i)
    {
        q.push(q.front());
        q.pop();
    }
    if (q.size() == 1)
        cout << q.front() << "\n";
    else
        cout << q.front() << " ";
    q.pop();
}

括号匹配（栈）

bool judge(string str)
{
    stack<char> stk;
    for (int i = 0; i < str.size(); ++i)
        if (str[i] == '(')
            stk.push('(');
        else if (str[i] == ')')
        {
            if (!stk.empty())
                stk.pop();
            else
                return false;
        }
    return stk.empty();
}

简易计算器（栈）

unordered_map<char, int> pri;
pri['#'] = 0;
pri['$'] = 1;
pri['+'] = pri['-'] = 2;
pri['*'] = pri['/'] = 3;

stack<char> op;
stack<int> num;
string str;
str += '$';
op.push('#');
int idx = 0;

while (idx < str.size())
{
    if (str[idx] == ' ')
        idx++;
    else if (isdigit(str[idx]))
        num.push(getnum(str, idx));
    else
    {
        if (pri[op.top()]) < pri[str[idx]])
            {
                op.push(str[idx]);
                idx++;
            }
        else
        {
            double y = num.top();
            num.pop();
            double x = num.top();
            num.pop();
            num.push(cal(x, y, op.top()));
            op.pop();
        }
    }
}