/*
5a) Write a program in C to create two queues using linked list and identify which queue is having
more number of elements and search for the duplicate elements is present in both queues display
the count of duplicates elements..
All standard operations of queue are to be performed
*/

#include <stdio.h>
#include <stdlib.h>

// A linked list (LL) node to store a queue entry
struct QNode {
    int key;
    struct QNode* next;
};

// The queue, front stores the front node of LL and rear stores the
// last node of LL
struct Queue {
    struct QNode *front, *rear;
};

// A utility function to create a new linked list node.
struct QNode* newNode(int k)
{
    struct QNode* temp = (struct QNode*)malloc(sizeof(struct QNode));
    temp->key = k;
    temp->next = NULL;
    return temp;
}

// A utility function to create an empty queue
struct Queue* createQueue()
{
    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;
    return q;
}

// The function to add a key k to q
void enQueue(struct Queue* q, int k)
{
    // Create a new LL node
    struct QNode* temp = newNode(k);

    // If queue is empty, then new node is front and rear both
    if (q->rear == NULL) {
        q->front = q->rear = temp;
        return;
    }

    // Add the new node at the end of queue and change rear
    q->rear->next = temp;
    q->rear = temp;
}

// Function to remove a key from given queue q
void deQueue(struct Queue* q)
{
    // If queue is empty, return NULL.
    if (q->front == NULL){
        printf("\nEmpty Queue!");
        return;
    }
    // Store previous front and move front one node ahead
    struct QNode* temp = q->front;
    printf("\nDequeued %d", temp->key);

    q->front = q->front->next;

    // If front becomes NULL, then change rear also as NULL
    if (q->front == NULL)
        q->rear = NULL;

    free(temp);
}

void display(struct Queue* q){
    struct QNode* temp = q->front;
    if (temp == NULL){
        printf("\nEmpty queue");
        return;
    }
    printf("\n");
    while(temp != NULL){
        printf("%d->", temp->key);
        temp = temp->next;
    }
}

void identifyLarger(struct Queue* q1, struct Queue* q2){
    int a=0, b=0;
    struct QNode* temp = q1->front;
    while(temp != NULL){
        a++;
        temp = temp->next;
    }

    temp = q2->front;
    while(temp != NULL){
        b++;
        temp = temp->next;
    }

    if (a>b){
        printf("\nQueue 1 has more number of elements");
    }
    else if (a==b){
        printf("\nBoth Queues have same number of elements");
    }
    else{
        printf("\nQueue 2 has more number of elements");
    }
}

void dupElem(struct Queue* q1, struct Queue* q2){
    struct QNode* t1= q1->front;

    int count = 0;
    printf("\nDuplicate elements: ");

    while (t1 != NULL){
        struct QNode* t2= q2->front;
        while(t2 != NULL){
            if (t1->key == t2->key){
                count++;
                printf("%d ", t1->key);
            }
            t2 = t2->next;
        }
        t1 = t1->next;
    }
    printf("\nHence there are %d duplicate elements", count);
}


// Driver Program to test anove functions
int main()
{
    struct Queue* q1 = createQueue();
    struct Queue* q2 = createQueue();

    int ch;
    int temp;
    while(1){
        printf("\n\tMENU\n");
        printf("\n1. Enqueue into Queue 1");
        printf("\n2. Enqueue into Queue 2");
        printf("\n3. Dequeue from Queue 1");
        printf("\n4. Dequeue from Queue 2");
        printf("\n5. Display Queue 1");
        printf("\n6. Display Queue 2");
        printf("\n7. Identify which Queue is having more number of elements");
        printf("\n8. Count and print the duplicate Elements");
        printf("\n9: Exit\n>>");

        scanf("%d", &ch);

        switch (ch)
        {
        case 1:
            printf("\nEnter data to enter into Queue 1 : ");
            scanf("%d", &temp);
            enQueue(q1, temp);
            break;
        case 2:
            printf("\nEnter data to enter into Queue 2 : ");
            scanf("%d", &temp);
            enQueue(q2, temp);
            break;
        case 3:
            deQueue(q1);
            break;
        case 4:
            deQueue(q2);
            break;
        case 5:
            display(q1);
            break;
        case 6:
            display(q2);
            break;
        case 7:
            identifyLarger(q1,q2);
            break;
        case 8:
            dupElem(q1, q2);
            break;
        case 9:
            exit(0)  ;
        default:
            printf("\nWrong Choice!");
            break;
        }

    }

    return 0;
}