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


typedef struct Node
{
	int key;
	struct Node *next;
} Node;

typedef struct Queue
{
	int size;
	Node *front;
	Node *rear;
} Queue;

void init_queue(Queue *q);
int is_empty(Queue *q);
int queue_first(Queue *q);
int queue_last(Queue *q);
void print_queue(Queue *q);
int queue_size(Queue *q);
void enqueue(Queue *q, int val);
int dequeue(Queue *q);

int main(void)
{
	Queue queue;
	init_queue(&queue);
	print_queue(&queue);
	printf("size of queue: %d\n", queue_size(&queue));
	printf("first: %d\n", queue_first(&queue));
	printf("last: %d\n", queue_last(&queue));
	enqueue(&queue, 1);
	print_queue(&queue);
	printf("first: %d\n", queue_first(&queue));
	printf("last: %d\n", queue_last(&queue));
	enqueue(&queue, 2);
	print_queue(&queue);
	printf("first: %d\n", queue_first(&queue));
	printf("last: %d\n", queue_last(&queue));
	enqueue(&queue, 3);
	print_queue(&queue);
	printf("first: %d\n", queue_first(&queue));
	printf("last: %d\n", queue_last(&queue));
	printf("size of queue: %d\n", queue_size(&queue));
	dequeue(&queue);
	print_queue(&queue);
	dequeue(&queue);
	print_queue(&queue);
	dequeue(&queue);
	print_queue(&queue);
	dequeue(&queue);
	print_queue(&queue);
	printf("size of queue: %d\n", queue_size(&queue));
	enqueue(&queue, 1);
	print_queue(&queue);
	printf("size of queue: %d\n", queue_size(&queue));
	return 0;
}

void init_queue(Queue *q)
{
    q->size = 0;
    q->front = NULL;
    q->rear = NULL;    
}

int is_empty(Queue *q)
{
	if (q->size == 0) return 1;
	else return 0;
}

int queue_first(Queue *q)
{
    if (is_empty(q)) return -1;
    else return (q->front)->key;;
}

int queue_last(Queue *q)
{
    if (is_empty(q)) return -1;
    else return (q->rear)->key;;
}

void print_queue(Queue *q)
{
	if (is_empty(q))
		printf("Queue is empty!\n");
	else
	{	
		Node *t = q->front;
		
		printf("Queue:\n");
		while(t!=NULL)
		{
			printf("%d\t", t->key);            
			t=t->next;
		}
		printf("\n");
	}
}

int queue_size(Queue *q)
{
	return q->size;
}

void enqueue(Queue *q, int val)
{
	Node *new_node = (Node*)malloc(sizeof(Node));  
    new_node->key=val; 
    
    if (q->size==0)
		q->front = new_node;
    
    else
		(q->rear)->next = new_node;
        
    q->rear = new_node;
    new_node->next = NULL;
    q->size++;
}

int dequeue(Queue *q)
{
	int val;
    Node *tmp;
    if (q->size > 0)
    {
		val = (q->front)->key;
		tmp = q->front;
		q->front = (q->front)->next;
		if (q->size == 1)
			q->rear = (q->rear)->next;
		q->size--;
		free(tmp);
		return val;
    }
    else return -1;
}