数据结构之——队列详解 ( 1 )

目录

前言     

一.队列

2.1队列的概念及结构

        1.定义：

        2.理解

二.队列的实现

1. 队列的数据结构

2.队列的初始化函数 

3.释放空间

4.入队——插入元素（从队尾处）

        图解：

         函数代码：

5.检查队列是否为空

6.出队——删除元素（从队头处）

        图解：

        函数代码：

7.返回队列的队头元素值

8.返回队列的队尾元素值 

9.求队列的长度

---

前言     

        栈和队列都是两个特殊类型的线性表，之前讲过了关于栈型线性表的特点和功能实现，博客如下： 数据结构之——栈的操作讲解与功能实现

        感兴趣的伙伴们可以去看看，接下来就需要来了解了解队列了。

一.队列

2.1队列的概念及结构

        1.定义：

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

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

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

        2.理解

        队列名副其实就是排队，就好比在医院看病，排了一字长龙，那么先挂号的病患就有优先看病的权力，后来排上队的人就得慢慢等了，这与栈的特征是完全相反的！

        队列既然也是线性表，那么就具有两种实现方式：顺序存储类型和链式存储类型。

        顺序存储就是用数组实现，比如有一个ｎ个元素的队列，数组下标0的一端是队头，入队操作就是通过数组下标一个个顺序追加，不需要移动元素，但是如果删除队头元素，后面的所有元素就要往前移动一次，若删除多个头元素，那么就要移动n次，所对应的时间复杂度就是O(n)，性能和效率自然低下；而且在删除元素时，会造成空间的丢失，如下图：

        若使用链表实现，链式存储的头部删除极为简单方便，而且链表中也有单链表形式和双向链表形式，本人认为使用单链表好一些，毕竟队列的实现很简单，双向链表有大材小用，杀鸡焉用牛刀的做法了。

        对比来看，链式队列比顺序队列的好处就在于，链式队列节省空间。

二.队列的实现

 

1. 队列的数据结构

typedef int QUEUENode;
 
//单向链式结构体数据类型
typedef struct QuNode {
	QUEUENode data;
	struct QuNode* next;
}QN;
 
//封装链式结构体QN的一个结构体队列
typedef struct Queue {
	QN* head;//队列头指针
	QN* tail;//队列尾指针
}Queue;

2.队列的初始化函数 

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

3.释放空间

//释放空间
void QueueDestory(Queue* pq) {
	assert(pq);
	QN* cur = pq->head;
	while (cur) {
		QN* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	pq->head = pq->tail = NULL;
}

4.入队——插入元素（从队尾处）

图解：

 函数代码：

//入队
void QueuePush(Queue* pq, QUEUENode x) {
	assert(pq);
	//开辟节点
	QN* newnode = (QN*)malloc(sizeof(QN));
	//若开辟失败
	if (newnode == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	//开辟成功：
	else {
		newnode->data = x;
		newnode->next = NULL;
	}
	//若队列为空
	if (pq->tail == NULL) {
		pq->head = pq->tail = newnode;
	}
	//若队列不为空
	else {
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

---

5.检查队列是否为空

在删除元素时，需要进行检查队列中是否有元素，若有元素，则断言false，通过该语句照常进行删除；若没有元素，则断言true 确认为空，程序报错！

//暴力检查
bool QueueEmpty(Queue* pq) {
	assert(pq);
	return pq->head == NULL && pq->tail == NULL;
}

注：C语言中没有bool类型，所以需要用到头文件#include即可使用

6.出队——删除元素（从队头处）

图解：

函数代码：

//出队
void QueuePop(Queue* pq) {
	assert(pq);
    //判断队列是否为空
	assert(!QueueEmpty(pq));
 
    //表明队列不为空，可以正常删除元素
    //情况1：
	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
 
    //情况2：
	else {
		QN* del = pq->head;
		pq->head = pq->head->next;
		free(del);
		del = NULL;
	}
}

---

7.返回队列的队头元素值

//返回队头元素
QUEUENode Queuehead(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

该函数的作用就是方便我们去打印输出队头元素的值

8.返回队列的队尾元素值 

//返回队尾元素
QUEUENode Queuetail(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

该函数的作用就是方便我们去打印输出队尾元素的值

9.求队列的长度

//队列长度
int QueueSize(Queue* pq) {
	assert(pq);
	int n = 0;
	QN* cur = pq->head;
	while (cur) {
		++n;
		cur = cur->next;
	}
	return n;
}

---

测试： 

 

记得测试完需要使用QueueDestory释放空间函数，否则会造成内存泄漏！！！ 

注：队列的增删方式只能为：头部删除元素，尾部插入元素