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

struct Node
{
	int data;
	struct Node * next;
};

struct Node* front=NULL;
struct Node* rear=NULL;

struct Node * createNode()
{
	struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
	printf("Enter Data : ");
	scanf("%d",&newNode->data);
	newNode->next=NULL;
	return newNode;
}

void push_back()
{
	if(front == NULL && rear==NULL)
	{
		front=createNode();
		rear=front;
	}
	else
	{
		rear->next=createNode();
		rear=rear->next;
	}
}

void push_front()
{
	if(front==NULL && rear==NULL)
	{
		front=createNode();
		rear=front;
	}
	else
	{
		struct Node* newNode=createNode();
		newNode->next=front;
		front=newNode;
	}
}
void pop_front()
{
	if(front==NULL && rear==NULL)
	{
		printf("Queue is Empty");
		return;
	}
	else if(front==rear)
	{
		front=NULL;
		rear=NULL;
	}
	else
	{
		front=front->next;
	}
}
void pop_back()
{
	if(front==NULL && rear==NULL)
	{
		printf("Queue is Empty");
		return;
	}
	else if(front==rear)
	{
		front=NULL;
		rear=NULL;
	}
	else
	{
		struct Node* temp=front;
		while(temp->next!=rear)
		{
			temp=temp->next;
		}
		rear=temp;
		temp->next=NULL;
	}
}
void traverse()
{
	if(front==NULL && rear==NULL)
	{
		printf("Queue is Empty");
		return;
	}
	else
	{
		struct Node* temp=front;
		while(temp!=rear)
		{
			printf("%d ",temp->data);
			temp=temp->next;
		}
		printf("%d ",temp->data);
	}
}

void main()
{
	clrscr();
	while(1)
	{
		printf("\n1. Insert At End");
		printf("\n2. Insert At Begining");
		printf("\n3. Delete At End ");
		printf("\n4. Delete At Begining");
		printf("\n5. EXIT");
		printf("\n6. Traverse");
		int ch;
		printf("\nEnter Your Choice : ");
		scanf("%d",&ch);
		switch(ch)
		{
			case 1:
				push_back();
				break;
			case 2 :
				push_front();
				break;
			case 3 :
				pop_back();
				break;
			case 4 :
				pop_front();
				break;
			case 5 :
				exit(0);
				break;
			case 6 :
				traverse();
				break;
			default :
				printf("Invalid Choice!");
		}

	}
}