剑指Offer——字符流中第一个不重复的字符

题目描述：

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

输入描述:

如果当前字符流没有存在出现一次的字符，返回#字符。

分析：

利用一个队列来存储只出现一次的字符，再用一个2^8的数组来保存字符出现的次数。

如果字符出现超过一次就不加入队列中，

并且如果队列中的第一个元素表示的字符出现一次，那么就返回该字符；

如果第一个元素表示的字符出现超过一次，那么就将其出队，找真正的只有出现一次的字符，直到队列为空，说明没有只出现一次的字符。

代码：

 1 class Solution {
 2 public:
 3     //Insert one char from stringstream
 4     void Insert(char ch) {
 5         cnt[ch]++;
 6         if(cnt[ch] == 1) myQueue.push(ch);
 7     }
 8     //return the first appearence once char in current stringstream
 9     char FirstAppearingOnce() {
10         while(!myQueue.empty()) {
11             char ch = myQueue.front();
12             if(cnt[ch] == 1) return ch;
13             else myQueue.pop();
14         }
15         return '#';
16     }
17     int cnt[1 << 8];
18     queue<char> myQueue;
19 };