牛客 吐泡泡 （栈和队列）

题目描述
小鱼儿吐泡泡，嘟嘟嘟冒出来。小鱼儿会吐出两种泡泡：大泡泡"O"，小泡泡"o"。
两个相邻的小泡泡会融成一个大泡泡,两个相邻的大泡泡会爆掉。
（是的你没看错，小气泡和大气泡不会产生任何变化的，原因我也不知道。）
例如:ooOOoooO经过一段时间以后会变成oO。

输入描述:
数据有多组，处理到文件结束。
每组输入包含一行仅有’O’与’o’组成的字符串。
输出描述:
每组输出仅包含一行，输出一行字符串代表小鱼儿吐出的泡泡经过融合以后所剩余的泡泡。

输入
ooOOoooO

输出
oO

说明
自左到右进行合并

备注:
对于100%的数据，
字符串的长度不超过100。

题目分析：考虑用栈去做，但是其中情况有很多，我刚开始做的时候就是没搞清楚大关系与小关系的位置，最后输出的时候，记得如果用的是栈那就反向输出，因为栈的性质就是先进后出。可以开一个新的数组储存正向的，然后反向遍历输出即可。

栈

#include <bits/stdc++.h>
using namespace std;
char a[1010], b[1010];
stack<char> s;
int main()
{
   
    while (~scanf("%s", a))
    {
   
        int la = strlen(a);
        for (int i = 0; i < la; ++i)
        {
   
            if (s.empty()) //如果为空直接入栈无法匹配
                s.push(a[i]);
            else if (s.top() == a[i])
            {
   
                if (s.top() == 'o') //同为小气泡
                {
   
                    s.pop();
                    if (s.size() && s.top() == 'O') //融合为大气泡时如果前面存在大气泡，出栈
                        s.pop();
                    else
                        s.push('O'); //否则入栈两个小气泡合成的大气泡
                }
                else if (s.top() == 'O') //如果相同，又是大气泡那直接出栈
                    s.pop();
            }
            else
                s.push(a[i]);
        }
        int h = 0;
        while (!s.empty())
        {
   
            b[++h] = s.top();
            s.pop();
        }
        for (int i = h; i >= 1; --i)
            putchar(b[i]);
        puts("");
    }
    return 0;
}

队列

#include <bits/stdc++.h>
using namespace std;
deque<char> st;
string str;
int main()
{
   
    while (cin >> str)
    {
   
        for (int i = 0; str[i]; ++i)
        {
   
            char c = str[i];
            if (st.empty() || st.back() != c)
                st.push_back(c);
            else
            {
   
                if (c == 'o')
                {
   
                    st.pop_back();
                    if (!st.empty() && st.back() == 'O')
                        st.pop_back();
                    else
                        st.push_back('O');
                }
                else
                    st.pop_back();
            }
        }
        while (!st.empty())
        {
   
            cout << st.front();
            st.pop_front();
        }
        puts("");
    }
}

附加题

动态数组模拟，有点像约瑟夫环
题目描述
编号为1、2、3、…、n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。从指定编号 为1的人开始，按顺时针方向自1开始报数，报到指定值m时停止报数，报第m的人出列，并将他的密码作 为新的m值，从他在顺时针方向的下一个人开始，重新从1开始报数，如此类推，直至所有的人全部出列 为止。输入n（n<=1000），m（m<=30000）及密码值（<=10000），试设计一个程序求出列顺序 。
输入
有二行，第一行，N和M，第二行，N个小于等于10000的密码值，中间用空格隔开。
输出
只有一行，就是出列的顺序，编号间以空格隔开。
样例输入
6 7
1 4 2 8 5 7

样例输出
1 2 6 3 5 4

AC代码

#include <bits/stdc++.h>
using namespace std;
int a[1010], vis[1010];
vector<int> q;
int n, m, cnt;
int main()
{
   
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for (int i = 1; i <= n; ++i)
    {
   
        if (q.size() == n - 1) //如果还剩最后一个人
        {
   
            for (int j = 1; j <= n; ++j) //直接遍历看看还有谁没有标记过，如果没有那就是他
                if (!vis[j])
                    q.push_back(j);
            break;//这个break很有必要，因为这是一个无限循环，一定要有一个终点，终点就是最后一个人出栈
        }
        if (!vis[i]) //如果当前的人没有被标记
        {
   
            ++cnt;        //就一直加
            if (cnt == m) //如果等于预期的数字那就要进行一段操作
            {
   
                m = a[i];       //首先就要重新更新m的值
                q.push_back(i); //然后把被点到的人放入数组
                vis[i] = 1;     //标记此人，相当于删除去此人
                cnt = 0;        //清空，开始下一次循环
            }
        }
        if (i == n) //因为模拟的是圆桌，人与人形成一个环，所以如果到了最后一个编号那就重新开始
            i = 0;
    }
    for (int i = 0; i < q.size(); ++i)//按照题目的意思输出即可
    {
   
        if (i == 0)
            printf("%d", q[i]);
        else
            printf(" %d", q[i]);
    }
}