First non-repeating character in a stream

'''
 Logic:
  queue consists only the characters which is non-repeated and also in order.after
  inserting every character,we go through queue and pop elements whose frequency is
  more than 1.
 Time Complexity : O(n) because for loop also runs for whole array and while loop
   also runs for whole array in worst case
'''
from collections import deque
class Solution:
    def firstNonRepeating(self, s):
        cur_dict={}
        q=deque([])
        ans=''
        for i in range(len(s)):
            if s[i] in cur_dict.keys():
                cur_dict[s[i]]+=1
            else:
                q.append(s[i])
                cur_dict[s[i]]=1
            while q and cur_dict.get(q[0],0)>1:
                    q.popleft()
            if len(q)>0:
                ans+=q[0]
            else:
                ans+='#'
        return ans

'''
*DLL will contain the non-repeating characters in order of stream,and head of
 DLL contain first non-repeating character.

*We are also maintining two array:
  repeated:It keeps track of characters visited more than one times.
  indll: It keeps address of node of characters present in DLL.
*Iterate through string and do following steps:
   i)If repeated[current_char] is true, ignore this character.
     because current_char is already repeated two or more times in the stream.
   ii)If repeated[current_char] is false and inDLL[current_char] is NULL means
      current_char is seen the first time then Append current_char to DLL and
      store address of new DLL node in inDLL[currnt_char].
   iii)If repeated[current_Char] is false and inDLL[x] is not NULL current_char is seen
       a second time then Get DLL node of current_char using inDLL[current_char]
       and remove the node. Also, mark inDLL[current_char] as NULL and
       repeated[current_char] as true.
'''

struct Node{
    char data;
    Node *prev,*next;
    Node(char k){
        data=k;
        prev=NULL;
        next=NULL;
    }
};

class Solution {
    public:
        string FirstNonRepeating(string s){
            bool repeated[256];
            Node * indll[256];
            memset(repeated,false,sizeof(repeated));
            memset(indll,NULL,sizeof(indll));
            string ans="";
            Node *head=NULL,*tail=NULL;

            for(int i=0;i<s.size();i++){
                int k=s[i];
                if(repeated[k]==false){
                    if(indll[k]==NULL){  //if character is not in dll
                        Node *temp=new Node(s[i]);
                        temp->prev=NULL;
                        temp->next=NULL;
                        if(!head){
                            head=tail=temp;
                        }
                        else{
                            tail->next=temp;
                            temp->prev=tail;
                            tail=temp;
                        }
                        indll[k]=temp;
                    }
                    else{   //if character is in dll,then remove that
                        repeated[k]=true;
                        if(head==NULL){indll[k]=NULL;continue;}
                        if(head==indll[k]){head=head->next;if(head)head->prev=NULL;}
                        else if(tail==indll[k]){tail=tail->prev;if(tail)tail->next=NULL;}
                        else{
                             Node *p=indll[k]->prev;
                             Node *n=indll[k]->next;
                             p->next=n;
                             n->prev=p;
                        }
                        indll[k]=NULL;
                    }
                }
               if(head)ans+=head->data;
               else ans+="#";

            }
            return ans;
        }

};