CodingInterview-字符流中第一个不重复的字符

这道题使用了一个数组（哈希表）来保存每个字符出现的次数，使用了一个队列来保存输入的某些字符。

再处理输入和输出的过程中使用了“懒处理”的方式。其中，再输入的时候，如果遇到了之前出现过的字符，则不将其输入到队列中；而在输出的时候，遇到了出现过多次的字符，则都将它 pop 出队列，直到遇到第一个只出现了一次的字符。

使用这样的模型，就只会保存第一次出现的字符，所以队列的长度被控制在 256 个字符以内，可以认为内存开销是固定的 O(1)。并且输入字符的时候，时间复杂度为 O(1)；而输出的时候，遍历的数字的数目只有出现重复字符的数目次（不超过 n），所以时间复杂度为 O(n)，并且 n 不会超过 256。

class Solution
{
private:
    int times[256];
    queue<char> chars;
public:
    Solution(){
        for(int i=0;i<256;i++) times[i]=0;
    }
  //Insert one char from stringstream
    void Insert(char ch)
    {
        times[ch]++;
        if(times[ch]==1) chars.push(ch);
    }
  //return the first appearence once char in current stringstream
    char FirstAppearingOnce()
    {
        while(!chars.empty()){
            char t=chars.front();
            if(times[t]==1) return t;
            else chars.pop();
        }
        return '#';
    }

};