【数据结构与算法】——队列

• 队列的定义
• 队列的基本操作

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头

队列采用链表而不用数组的原因：由于队列的结构是先进先出，出队列的时候，数组每次都需要覆盖掉第一个数据，效率很低，而链表可以直接在队头出数据，队尾入数据，时间复杂度都是O(1).

1. 定义一个队列

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

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
}Queue;

在有头指针的情况下，调用接口必然会涉及到改变头指针，因此这里有四种方案：

1. 采用二级指针
2. 使用返回值
3. 使用带哨兵位的结点
4. 将结构体包在一起

这里实现队列采用的是第四种方案

2. 队列初始化

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead=pq->ptail = NULL;

}

3. 队列的销毁

void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->phead;
	while (cur)
	{
		QueueNode* next = pq->phead->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
}

4. 入队列

void QueuePush(Queue* pq, QDataType x)
{
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		printf("malloc failn");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	assert(pq);
	if(pq->ptail == NULL)//第一次尾插数据
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
}

5. 出队列

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//判断队列是否为空
	if (pq->phead->next==NULL)//要判断是否只有一个结点，如果只有一个结点，直接free掉就可以
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QueueNode* next = pq->phead->next;//如果不判断，直接删除会出现野指针问题
		free(pq->phead);
		pq->phead = next;
	}
}

这里要判断是否只剩一个结点的情况，如果只有一个结点，将pq->phead释放掉之后，pq->ptail仍然指向原来结点的地址，会出现野指针的情况

6. 判断队列是否为空

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->ptail == NULL;
}

7. 队列数据的个数

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* cur = pq->phead;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

8. 取队头的数据

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(&pq));
	return pq->phead->data;
}

9. 取队尾的数据

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(&pq));
	return pq->phead->data;
}