#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;
}