#include <stdio.h>

/* 隊列的結構體 */
typedef int DataType;
#define NODE_LEN sizeof(NODE) 

/* 隊列的節點 */
typedef struct stNode
{
  DataType data;
  struct stNode* next;
}NODE;

/* 隊列 */
typedef struct stQueue
{
  NODE* head; //隊列的頭
  NODE* tail; //隊列的尾
}QUEUE;

/* 初始化隊列,不帶頭結點*/
int initQueue(QUEUE* INQueue)
{

  INQueue->head = NULL;
  INQueue->tail = NULL;

  return 0;
}

/* 從隊尾插入一個元素 */
int enQueue(QUEUE* InQueue,DataType InData)
{
  NODE* pNewNode = (NODE*)malloc(NODE_LEN);
  if (pNewNode == NULL)
  {
    return -1;
  }

  pNewNode->data = InData;
  pNewNode->next = NULL;

  /* 判斷，現在隊列里面有沒有節點 */
  if (InQueue->head == NULL)
  {
    InQueue->head = pNewNode;
    InQueue->tail = pNewNode;
  }
  else
  {
    InQueue->tail->next = pNewNode;
    InQueue->tail = pNewNode;
  }

  return 0;
}

/* 遍歷該隊列 */
int visitQueue(QUEUE InQueue)
{
  QUEUE* pstTemp = &InQueue;

  /* 判斷隊列是否為空隊列 */
  if (pstTemp->head == NULL)
  {
    printf("visitQueue: this queue is empty\n");
    return -1;
  }

  /* 遍歷該隊列中的所有元素 */
  while (pstTemp->head->next != NULL)
  {
    printf("%d ", pstTemp->head->data);
    pstTemp->head = pstTemp->head->next;
  }
  printf("%d \n", pstTemp->head->data);

  return 0;
}

/* 出隊列 */
int delQueue(QUEUE* InQueue,DataType* OutData)
{
  if (InQueue->head == NULL)
  {
    printf("delQueue: this queue is empty\n");
    return -1;
  }

  *OutData = InQueue->head->data;

  NODE* pstTemp = InQueue->head;
  InQueue->head = InQueue->head->next;

  delete pstTemp;
  return 0;
}

/* 判斷隊列是否是空隊列 */
int isEmptyQueue(QUEUE InQueue)
{
  if (InQueue.head == NULL)
  {
    return 0; //是空隊列
  }
  return 1; //不是空隊列
}

int main()
{
  /* 創建一個隊列 */
  QUEUE queue;
  DataType data;

  initQueue(&queue);

  /* 入隊列 */
  enQueue(&queue, 12);
  enQueue(&queue, 11);
  enQueue(&queue, 2);
  visitQueue(queue);

  /* 出隊列 */
  delQueue(&queue, &data);
  visitQueue(queue);
  printf("data = %d\n", data);

  visitQueue(queue);

  if (0 == isEmptyQueue(queue))
  {
    printf("This is empty queue\n");
  }
  else
  {
    printf("This is not empty queue\n");
  }
  return 0;
}