题解 | #字符流中第一个不重复的字符#

第七十七题

利用队列和hash

队列保存只出现过一次的，hash保存出现的次数

输出的时候，从队列中取出，如果队列头出现过多次，就删除，然后循环。如果循环到队列为空，就说明没有不重复的字符，返回#

class Solution
{
public:
    // 队列保存只出现一次的
    queue<char> q;
    unordered_map<char, int> mp;
    void Insert(char ch)
    {
        // 如果是第一次出现， 则添加到队列中
        if (mp.find(ch) == mp.end())
            q.push(ch);
        // 记录当前的值到map中
        ++mp[ch];
    }
    
    //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        // 如果说队列还有值 就从队列头取出结果，判断队列头是否是只出现一次的
        while (!q.empty()) {
            char ch = q.front();
            if (mp[ch] == 1)
                return ch;
            // 如果 不是第一次出现，则弹出，继续循环
            else
                q.pop();
        }
        // 如果队列是空的就返回#
        return '#';
    }
};