写有“售后”的博客：一定回复评论和私信，答疑解惑到底，认真探讨大家的疑问，欢迎大家多多指出批评与建议！

  参考书籍：《大话数据结构》，《数据结构（C语言版）》

一、准备工作

1.何为队列

  我们已经学过了数据结构：栈(Stack)，栈就像一个只有一端开口的羽毛球筒，其中存放的羽毛球先进而后出。
  上图是队列的简图，相比栈，队列就显得“公平”很多，队列在队头删除数据，称为出队；在队尾插入数据，称为入队，使得数据可以先进先出，后进后出，就像在排队一样。

2.用线性表还是链表实现队列？

  我们首先定义两个指针，让它们分别指向队列的头和尾。

a)线性表的缺点

  缺点：头删或尾插操作的时间复杂度为O(n)
  对于一个线性表，如果我们将线性表队首定义为队列的头，队尾定义为队列的尾，进行队列尾插操作时，时间复杂度可为O(1)；进行队列头删操作时，需要抹除第一个数据，再依次遍历前移其它数据，队列头删操作时间复杂度为O(n)。
  对于一个线性表，如果我们将线性表队首定义为队列的尾，队尾定义为队列的头，进行队列头删操作时，时间复杂度可为O(1)；进行队列尾插操作时，需要依次遍历后移其它数据，再在线性表表头插入数据，队列尾插操作时间复杂度为O(n)。

b)单链表的头尾抉择

  我们以单链表的头作为队列的头实现头删操作，以单链表的尾作为队列的尾实现尾插操作。 理由如下：
  对于一个单链表，如果我们将单链表表首定义为队列的头，表尾定义为队列的尾，进行队列尾插操作时，时间复杂度可为O(1)；进行队列头删操作时，时间复杂度也可为O(1)。
  对于一个单链表，如果我们将单链表表尾定义为队列的头，表头定义为队列的尾，进行队列尾插操作时，时间复杂度可为O(1)；进行队列头删操作时（单链表的尾删），单链表的尾删操作需要找到尾结点的上一个节点，必须从头结点开始遍历了，时间复杂度为O(n).
  显然第一种定义方法时间复杂度最优。

c)双向链表的优缺点

  相比于单链表，双向链表不论怎么定义头和尾，队列的删插操作时间复杂度都为O(1)——因为尾结点可以找到上一个节点了，省去了单链表那么长一串的分析过程。
  但双向链表比头结点多了一个指向上一个节点的指针，围绕着这个指针要多写好多代码。
  综上我们选择单链表作为队列的大致结构。

二、队列的实现

  通过前面的分析我们已经确定了以单链表的头作为队列的头实现头删操作，以单链表的尾作为队列的尾实现尾插操作。

1.头文件及定义节点结构

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

typedef int QDataType;

typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

2.定义队列结构

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Q;

  指针phead指向队首节点，ptail指向队尾节点，所以数据类型用QNode*。size用于统计数据个数

3.初始化队列

void QInit(Q* q)
{
	assert(q);
	q->phead = q->ptail = NULL;
	q->size = 0;
}

4.入队——队列的尾插

void QPushBack(Q* q, QDataType x)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc");
	}
	newnode->data = x;
	newnode->next = NULL;

	if (q->ptail == NULL)
	{
		q->phead = q->ptail = newnode;
	}
	else
	{
		QNode* pcur = q->phead;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = newnode;
	}
	q->size++;
}

5.出队——队列的头删

void QPopFront(Q* q)
{
	assert(q);
	assert(q->phead);
	if (q->phead->next == NULL)
	{
		free(q->phead);
		q->phead = q->ptail = NULL;
	}
	else
	{
		QNode* pnext = q->phead->next;
		free(q->phead);
		q->phead = pnext;
	}
	q->size--;
}

6.获取队头数据

QDataType QHeadData(Q* q)
{
	assert(q);
	assert(q->phead);
	return q->phead->data;
}

  传过来的结构体指针不能为NULL，队列不能为NULL。

7.获取队尾数据

QDataType QTailData(Q* q)
{
	assert(q);
	assert(q->ptail);
	return q->ptail->data;
}

8.获取队内数据个数

int Qsize(Q* q)
{
	assert(q);
	return q->size;
}

9.判断队列是否为空

bool QEmpty(Q* q)
{
	assert(q);
	return q->size == 0;
}

10.销毁队列

void QDestroy(Q* q)
{
	assert(q);
	QNode* pcur = q->phead;
	while (pcur)
	{
		pcur = pcur->next;
		free(q->phead);
		q->phead = pcur;
	}
	q->ptail = NULL;
	q->size = 0;
}

11.在主函数中对接口进行测试示例

int main()
{
	Q q;
	QInit(&q);
	QPushBack(&q, 1);
	QPushBack(&q, 2);
	QPushBack(&q, 3);
	QPushBack(&q, 4);
	while (!QEmpty(&q))
	{
		printf("%d->", QHeadData(&q));
		QPopFront(&q);
	}
	QDestroy(&q);

	return 0;
}

  打印结果为1->2->3->4->
  QInit、QPushBack、QEmpty、QPopFront接口无误。

完~
感谢您的观看！