【C语言/数据结构】队列：从概念到队列的实现

---

• 在日常生活中，我们去车站窗口买票，或去医院问诊都会进行排队，而排队表示着一种先到先买票，或先问诊的准则；前一个人走了，后面一个人补上前一个人的位置。
• 试想，大家正在排队购票的时候，走来了一个醉汉想要插队，正在排队的你会愿意吗？我想你一定会说，我不愿意。
• 所以排队也有着一种，后来的人，要在队尾排队等待，队头的人先得到服务，且正常情况下，也是队头的人先一步离开；
• 而数据结构中存在一种特殊的线性表，和咱们日常生活中的排队有着息息相关的的关系——队列(Queue)

---

一、队列的基础知识

1.队列的定义

        队列是一种特殊的线性表，只允许在一端插入数据，在另一端删除数据；插入数据的一端叫做队尾，插入数据的一端叫做队头；其有着先进先出的准则，FIFO(First In First Out)。

2.队列的功能接口

 初始化

 销毁

 插入数据

 删除数据

 获取队头元素

 获取队尾元素

 返回队列的元素个数

 判断队列是否为空

二、队列的设计思路

1.顺序结构实现队列

2.链式结构实现队列

3.两种结构之间的比较

• 链式结构实现队列：队头与队尾的设计，使得只存在第一个结点数据的删除，巧妙的避开了删除一个结点，需要找到一个结点的问题；插入和删除元素的时间复杂度为O(1)；
• 顺序结构实现队列：数组删除队头的元素时，后面的所有元素，需要向前挪动，其时间复杂度为O(N)；
• 总结：实现队列的最优结构是链式结构，下面将对链式结构实现队列进行深入讲解

三、队列的代码实现

1.初始化

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

2.毁销

// 销毁
void QueueDestory(Queue* qu)
{
	while (!QueueEmpty(qu))
	{
		QueuePop(qu);
	}
}

3.插入数据

// 队尾插入
void QueuePush(Queue* qu, QDateType x)
{
	assert(qu);
 
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (!newnode)
	{
		perror("malloc mistake");
		return;
	}
	newnode->Date = x;
	newnode->next = NULL;
 
	if (qu->ptail == NULL)
	{
		qu->phead = qu->ptail = newnode;
	}
	else
	{
		qu->ptail->next = newnode;
		qu->ptail = newnode;
	}
	qu->size++;
}

4.删除数据

// 队头删除
void QueuePop(Queue* qu)
{
	assert(qu);
 
    //没有元素的处理
	if (qu->size == 0)
		return;
    //只有一个元素的处理
	if (qu->ptail == qu->phead)
	{
		free(qu->phead);
		qu->phead = qu->ptail = NULL;
	}
    //多个元素的处理方法
	else
	{
		QNode* next = qu->phead->next;
		free(qu->phead);
		qu->phead = next;	
	}
    //不要忘了size -1
	qu->size--;
}

 5.获取队头元素

// 获取队头数据
QDateType QueueFront(Queue* qu)
{
	assert(qu);
	return qu->phead->Date;
}

 6.获取队尾元素

// 获取队尾数据
QDateType QueueBack(Queue* qu)
{
	assert(qu);
	return qu->ptail->Date;
}

7.返回队列的元素个数

// 获取队列长度
size_t QueueSize(Queue* qu)
{
	assert(qu);
	return qu->size;
}

 8.判断队列是否为空

// 判空
bool QueueEmpty(Queue* qu)
{
	assert(qu);
	return qu->size == 0 ? true : false;
}