/* 
* Code example for CP264 Data Structures II
* queue by linked list
* HBF 
*/
#include <stdio.h>
#include <malloc.h>

typedef struct node {
  int data;
  struct node *next;
} qnode;

typedef struct queue {
  qnode *front;
  qnode *rear;
} queue;

void enqueue(queue *, int);
int dequeue(queue *);
qnode *dequeue1(queue *);
void dequeue2(queue *, qnode**);
void display(queue);
void clean(queue *);

int main() {
  int i, val;
  queue myq = {0};
  myq.front = NULL;
  myq.rear = NULL;
  for (i=1; i<=5; i++) {
     printf("Enqueue value:%d\n", i);
     enqueue(&myq, i);
  }
  printf("\nDisplay:\n");
  display(myq);

  printf("\nDequeue value: %d\n", dequeue(&myq));
  
  qnode *qnp = dequeue1(&myq);
  printf("\nDequeue1: %d\n", qnp->data);
  free(qnp);
  
  dequeue2(&myq, &qnp);
  printf("\nDequeue2: %d\n", qnp->data);
  free(qnp);
  
  printf("\nDisplay:\n");
  display(myq);
  clean(&myq); 
  return 0;
}

void enqueue(queue *q, int val) {
  qnode *ptr;
  ptr = (qnode*) malloc(sizeof(qnode));
  ptr->data = val;
  if (q->front == NULL) {
    q->front = ptr;
    q->rear = ptr;
    q->front->next = q->rear->next = NULL;
  } else {
    q->rear->next = ptr;
    q->rear = ptr;
    q->rear->next = NULL;
  }
}

int dequeue(queue *q) {
  int val = -1;
  if (q->front == NULL)
    printf("\nUNDERFLOW");
  else {
    qnode *ptr = q->front;
      val = ptr->data;
    q->front = ptr->next;
    free(ptr);
  }
  return val;
}

qnode *dequeue1(queue *q) {
  qnode *ptr = NULL;
  if (q->front) {
    ptr = q->front;
    if (q->front == q->rear) {
      q->front = NULL;
      q->rear = NULL;
    } else {
      q->front = ptr->next;
    }
  }
  return ptr;
}

void dequeue2(queue *q, qnode **npp) {
  qnode *ptr = NULL;
  if (q->front) {
    ptr = q->front;
    if (q->front == q->rear) {
      q->front = NULL;
      q->rear = NULL;
    } else {
      q->front = ptr->next;
    }
  }
  *npp = ptr;
}

int peek(queue q) {
  if (q.front == NULL) {
    printf("\nEMPTY");
    return -1;
  } else
    return q.front->data;
}

void display(queue p) {
  qnode *ptr = p.front;
  if (ptr == NULL)
    printf("\nEMPTY");
  else {
    while (ptr != p.rear) {
      printf("%d  ", ptr->data);
      ptr = ptr->next;
    }
    printf("%d  ", ptr->data);
  }
}

void clean(queue *q) {
  if (q->front != NULL) {
    qnode *temp, *ptr = q->front;

    while (ptr != NULL) {
      temp = ptr; 
      ptr = ptr->next;
      free(temp);
    }
    q->front = NULL;
    q->rear = NULL;
  }
}

/*
Enqueue value:1
Enqueue value:2
Enqueue value:3
Enqueue value:4
Enqueue value:5

Display:
1  2  3  4  5
Dequeue value: 1

Dequeue1: 2

Dequeue2: 3

Display:
4  5
 */