系列文章目录

前言

一、队列的概念及结构

1.队列的概念

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

2.队列的结构

二、队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

1.定义用链表表示的队列struct QueueNode

代码如下：

typedef int QDataType;
struct QueueNode             //队列结构,用链表来表示
{
	struct QueueNode* next;
	QDataType data;
};

2.定义队列的队头、队尾指针struct Queue

代码如下：

struct Queue                //队列头尾指针
{
	struct QueueNode* head;
	struct QueueNode* tail;
};

3.队列的初始化函数QueueInit

代码如下：

void QueueInit(struct Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

4.队列的销毁函数QueueDestroy

遍历队列，记住free前先存储下一个节点的地址。
代码如下：

void QueueDestroy(struct Queue* pq)
{
	assert(pq);
	struct QueueNode* cur = pq->head;
	while (cur)
	{
		struct QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

5.队列的队尾入数据函数QueuePush

先开辟一个结点，在分两种情况，一种情况队列一个节点都没有，那可以直接当节点，第二种情况队列一开始有节点，尾插数据即可。
代码如下：

void QueuePush(struct Queue* pq, QDataType x)   //队尾入数据
{
	assert(pq);
	struct QueueNode* newnode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
	if (newnode == NULL)
	{
		printf("开辟失败!\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail == NULL)   //无节点
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

6.队列的队头出数据函数QueuePop

代码如下：

void QueuePop(struct Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	if (pq->head->next==NULL)  //只有一个节点
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		struct QueueNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

7.队列的取出队头数据函数QueueFront

记住每次取数据前判断队列是否为空，不为空才进行下一步。
代码如下：

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

8.队列的取出队尾数据函数QueueBack

记住每次取数据前判断队列是否为空，不为空才进行下一步。
代码如下：

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

9.队列是否为空函数QueueEmpty

代码如下：

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

10.队列的长度函数QueueSize

代码如下：

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

总结

以上就是今天要讲的内容，本文仅仅简单介绍了队列的使用，对于队列提供了一些简便方法帮助我们解题，能使我们快速便捷地处理数据的函数和方法。另外这个结构虽然相比链表更简单，使用代码实现起来更容易写，但我们也要认真学习，以后会发现队列结构会带来很多优势，我们务必掌握。另外，如果有需要源码的私信我即可。还有，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。