#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <time.h>
#include <unistd.h>

#define TYPE int

typedef struct Node{
    TYPE data;
    struct Node *next,*back;
}Node;

typedef struct Deque{
    Node *head,*tail;
}Deque;

void reset(Deque *queue){ queue->head = queue->tail = NULL;}
int isEmpty(Deque *queue){ return !queue->head; }

void insertFirst(Deque *queue,TYPE val){
    Node *node = (Node*) malloc(sizeof(Node));
    node->data = val;
    node->back = NULL;
    if(isEmpty(queue)){
        node->next = NULL;
        queue->head = node;
    }else{
        node->next = queue->tail;
        (queue->tail)->back = node;
    }
    queue->tail = node;
}

TYPE first(Deque queue){
    if(!isEmpty(&queue))
        return (queue.tail)->data;
    return 0;
}

void removeFirst(Deque *queue){
    if(!isEmpty(queue)) {
        if(!(queue->tail)->next) // in case of last element in the queue
            reset(queue);
        else{
            Node *node = (queue->tail)->next;
            node->back = NULL;
            free(queue->tail);
            queue->tail = node;
        }
    }
}

void insertLast(Deque *queue, TYPE val){
    Node *node = (Node*) malloc(sizeof(Node));
    node->data = val;
    node->next = NULL;
    if(isEmpty(queue)){
        node->back = NULL;
        queue->tail = node;
    }else{
        (queue->head)->next = node;
        node->back = queue->head;
    }
    queue->head = node;
}

TYPE last(Deque queue){
    if(!isEmpty(&queue))
        return (queue.head)->data;
    return 0;
}

void removeLast(Deque *queue){
    if(!isEmpty(queue)) {
        if(!(queue->tail)->next) // in case of last element in the queue
            reset(queue);
        else{
            Node *node = (queue->head)->back;
            node->next = NULL;
            free(queue->head);
            queue->head = node;
        }
    }
}

void display(Deque queue){
    printf("Queue: \n");
    while(queue.tail) {
        printf("[%d]\n",queue.tail->data); queue.tail = queue.tail->next;
    }
}

int size(Deque queue){
    unsigned int i=0;
    while(queue.tail) {
        i++; queue.tail = queue.tail->next;
    }
    return i;
}

void BuildQueue(Deque *queue,int limit){
    unsigned int i=1;
    while(i<=limit)
        insertLast(queue,i++);
}

void status(char x[],int time){
    printf("%sReturning to main menu...\n",x); sleep(time); // Wait time
}

int main(){
    system("cls");
    Deque queue; reset(&queue);
    unsigned int i=0;
    printf("Welcome to the \"Deque\" program :\n\n");
    do{
        printf("Please choose what you want to do : \n");
        printf("1.Build a queue.\n2.Insert at the FIRST of the queue\n");
        printf("3.Insert at the END of the queue.\n4.Get value of FIRST element in the queue\n");
        printf("5.Get value of LAST element in the queue.\n6.Check if queue is empty\n");
        printf("7.Size of the queue\n8.Display the queue\n");
        printf("9.Exit\n");
        printf("\nChoise: ");
    }while(scanf("%d",&i) && !i);
    unsigned int val,limit;
    system("cls");
    switch(i){
        case 1:
            printf("What limit of this queue to be built: "); scanf("%d",&limit);
            BuildQueue(&queue,limit);
            status("Success Build.",2);
            break;
        case 2:
            printf("Value to be inserted at the FIRST of queue: "); scanf("%d",&val);
            insertFirst(&queue,val);
            status("Success insert operation.",2);
            break;
        case 3:
            printf("Value to be inserted at the LAST of queue: "); scanf("%d",&val);
            insertLast(&queue,val);
            status("Success insert operation.",2);
            break;
        case 4:
            printf("Value of FIRST element : [%d]\n", first(queue));
            status("Success operation.",2);
            break;
        case 5:
            printf("Value of LAST element : [%d]\n", last(queue));
            status("Success operation.",2);
            break;
        case 6:
            !isEmpty(&queue) ? printf("Queue is not Empty.\n") :  printf("Queue is Empty.\n") ;
            status("Success Checking operation.",2);
            break;
        case 7:
            printf("Size of queue : [%d]\n", size(queue));
            status("Success operation.",2);
            break;
        case 8:
            display(queue);
            status("Success display operation.",2);
            break;
        case 9:
            exit(0);
    }
    main();
    return 0;
}