链式队列的实现

//队列的结构定义
typedef int QDataType;
typedef struct QueueNode {
  QDataType val;
  struct QueueNode* next;
}QNode;
//将头指针和尾指针存放到一个结构体中组成队列，易于找到队列头和尾且无需使用二级指针
typedef struct QueueNode {
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;

//队列的初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}

//队列的打印
void QueuePrint(Queue* pq)
{
  assert(pq);
  if (pq->phead == NULL)
    printf("NULL\n");
  else
  {
    QNode *cur = pq->phead;
    while (cur)
    {
      printf("%d ", cur->val);
    }
    printf("\n");
  }
}

//入队列
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  newnode->val = x;
  newnode->next = NULL;
  if (pq->phead == NULL)
  {
    pq->phead = pq->ptail = newnode;
  }
  else
  {
    pq->ptail->next = newnode;
    pq->ptail = newnode;
  }
  pq->size++;
}

//出队列
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->ptail);
  if (pq->phead == pq->ptail)//队列中只有一个元素
  {
    pq->ptail = NULL;
  }
  QNode* tmp = pq->phead;
  pq->phead = pq->phead->next;
  free(tmp);
  tmp = NULL;
  pq->size--;
}

//取队头元素
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->phead);//空队列
  return pq->phead->val;
}

//取队尾元素
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->ptail);//空队列
  return pq->ptail->val;
}

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
  return pq->phead == NULL;
}

//求队列大小
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}

//销毁队列
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->phead;
  while (cur)
  {
    QNode* tmp = cur;
    cur = cur->next;
    free(tmp);
    tmp = NULL;
  }
  pq->phead = NULL;
  pq->ptail = NULL;
  pq->size = 0;
}

void test01()
{
    //定义一个队列
    Queue q;
    //初始化队列
    QueueInit(&q);
    //入队
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    QueuePush(&q, 5);
    //队列打印
    QueuePrint(&q);
    //出队列
    QueuePop(&q);
    QueuePop(&q);
    QueuePop(&q);
    //队列打印
    QueuePrint(&q);
    //取队头元素
    printf("%d\n", QueueFront(&q));
    //取队尾元素
    printf("%d\n", QueueBack(&q));
    //判断队列是否为空
    if (QueueEmpty(&q))
        printf("空\n");
    else
        printf("非空\n");
    //求队列大小
    printf("%d\n", QueueSize(&q));
    //销毁队列
    QueueDestroy(&q);
}
int main()
{
    test01();
}