first_non-repeating_character_from_a_stream.cpp

/**
 * ZYRO9922
**/

#include <bits/stdc++.h>
#include <algorithm>

using namespace std;

template <typename T>
class Node {
public:
    T data;
    Node* next;
    Node* prev;

    Node(T d)
    {
        data = d;
        next = NULL;
        prev = NULL;
    }
};

template <typename T>
class DLL {

    Node<T>* head = NULL;
    Node<T>* tail = NULL;
public:

    void push_back(T c)
    {
        Node<T>* val = new Node<T>(c);

        if (head == NULL)
        {
            head = val;
            tail = val;
            return;
        }
        else
        {
            val->prev = tail;
            tail->next = val;
            tail = val;

            return;
        }
    }

    void delete_node(Node<T>* cur)
    {
        if (head == NULL || cur == NULL)
            return;

        if (head == cur)
            head = cur->next;

        if (tail == cur)
            tail = tail->prev;

        if (cur->next != NULL)
            cur->next->prev = cur->prev;

        if (cur->prev != NULL)
            cur->prev->next = cur->next;

        delete(cur);

        return;
    }

    Node<T>* get_node_tail()
    {
        return tail;
    }

    void peek_front()
    {
        if (head != NULL)
            cout << "\nList Front: " << head->data << endl;
        else
            cout << "List empty\n";

        return;
    }

    void printDLL()
    {
        while (head != NULL)
        {
            cout << head->data << "->";
            head = head->next;
        }
    }
};

/**
    https://www.geeksforgeeks.org/find-first-non-repeating-character-stream-characters/
    Give Input: geeksforgeeksandgeeksquizfor#
**/

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);

    freopen("output.txt", "w", stdout);
#endif

    //Map
    map<char, Node<char>*> m;

    // Doubly Linked List
    DLL<char> dll;

    char c;
    cin >> c;

    while (c != '#')
    {
        dll.peek_front();

        // If not present in Map
        // Add that charachter with it's reference
        if (m.find(c) == m.end())
        {
            dll.push_back(c);
            m[c] = dll.get_node_tail();
        }

        // Get reference of that charachter from Map
        // Delete it
        else
        {
            // Already deleted once. It's a repeated charachter
            if (m[c] != NULL)
            {
                dll.delete_node(m[c]);
                m[c] = NULL;
            }
        }
        cin >> c;
    }

    dll.peek_front();
}