目录

前言：

暑期复习之队列的简单理解

一·队列的设计思路

二·队列的具体代码详解

1.初始化队列

2.销毁队列

3.入队列

4.出队列

5.取队头元素

6.取队尾元素

7.判空函数

8.获取总的数据元素个数

三·队列的总结

前言：

暑期复习之队列的简单理解

队列是一种特殊的线性表，和栈很类似，但是他两的运算规则不同。

一·队列的设计思路

队列是一种基于先进先出的数据结构，是一种只能在一端进行插入，在另一端进行删除操作的特殊线性表，它按照先进先出的原则存储数据，先进入的数据，在读取数据时先被读出来。

 入队列：进行插入操作的一端称为队尾

 出队列：进行删除操作的一端称为队头

 

typedef int QElemType;

typedef struct QueueNode//队列中结点的结构体
{
	struct QueueNode* next;  //指针域
	QElemType data;   //数据域
}QNode;

typedef struct Queue//队列的结构体
{
	QNode* head;    //头指针
	QNode* tail;    //尾指针
}Queue;

二·队列的具体代码详解

1.初始化队列

队列有头指针和尾指针，初始化就是将结构体中的成员变量赋一个初始值，既然成员变量是两个指针，直接赋值为空就OK。

//初始化队列
void QueueInit(Queue* ps)
{
	assert(ps != NULL);
	ps->head = NULL;
	ps->tail = NULL;
}

2.销毁队列

先让指向结点的指针指向head，利用while循环进行释放结点空间，最后让头尾指针为空。

//销毁队列
void QueueDestroy(Queue* ps)
{
	assert(ps != NULL);
	QueueNode* s = ps->head;
	while (s != NULL)
	{
		QueueNode* next = s->next;
		free(s);
		s = next;	
	}
	ps->head = ps->tail = NULL;
}

3.入队列

先创建一个节点空间，并初始化。然后利用if判断队列是否为空，如果队列为空直接将头尾指针都指向新节点，如果不为空，直接修改尾指针的next域，最后要记得将尾指针指向新节点。

//入队列
void QueuePush(Queue* ps, QElemType x)
{
	assert(ps != NULL);
	QueueNode* newdata = (QueueNode*)malloc(sizeof(QueueNode));
	newdata->data = x;
	newdata->next = NULL;
	if (ps->head == NULL)
	{
		ps->head = ps->tail = newdata;
	}
	else
	{
		ps->tail->next = newdata;
		ps->tail = newdata;
	}
}

4.出队列

先判空，再利用一个临时的变量来处理与head之间的关系，最后还要注意边检条件，如果删到了最后一个节点，那么要注意释放掉这最后的一个节点后，尾指针就变成了一个野指针，所以要加入一个判断，如果到了最后一个节点head为空了，那么尾指针也要为空。

//出队列
void QueuePop(Queue* ps)
{
	assert(ps != NULL);
	assert(!QueueEmpty(ps));
	QueueNode* next = ps->head->next;
	free(ps->head);
	ps->head = next;
	if (ps->head == NULL)
	{
		ps->tail = NULL;
	}
}

5.取队头元素

//取队头元素
QElemType QueueFront(Queue* ps)
{
	assert(ps != NULL);
	assert(!QueueEmpty(ps));
	return ps->head->data;
}

6.取队尾元素

//取队尾元素
QElemType QueueBack(Queue* ps)
{
	assert(ps != NULL);
	assert(!QueueEmpty(ps));
	return ps->tail->data;
}

7.判空函数

直接判断头指针是否为空。

//判空函数
bool QueueEmpty(Queue* ps)
{
	assert(ps != NULL);
	return ps->head == NULL;
}

8.获取总的数据元素个数

利用计数器变量来计算,很简单的计数，最后返回n值。

//获取队列总的数据个数
int SizeQueue(Queue* ps)
{
	assert(ps != NULL);
	int n = 0;
	QueueNode* s = ps->head;
	while (s)
	{
		++n;
		s = s->next;
	}
	return n;
}

三·队列的总结

（1）队列属于特殊的一种线性表结构。

（2）先进先出的运算规则。

（3）比较难的就是入队列和出队列中的边界条件，防止野指针出现。