数据结构学习篇（7）---队列

1. 队列的概念及结构

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

• 入队列：进行插入操作的一端称为队尾。
• 出队列：进行删除操作的一端称为队头。

队列和栈是有所不同的，比如入栈顺序是1 2 3 4，但是出栈顺序可以有多种，不一定是 1 2 3 4，因为它可以边进边出，所以是一个一对多的关系；而队列的入队列顺序和出队列顺序是一样的，是一个一对一的关系，正是基于队列的这种性质，它可以用于保持公平性（例如做一个抽号机：比如吃饭排队拿取号码，先来的先拿，后来的后拿）。

也可以利用队列来做一个好友推荐（广度优先遍历）

假如要给小徐推荐好友，那么就以小徐为起点，首先让小徐进入队列，然后让小徐出队列（第一圈结束）的同时，让小徐的好友小明和小王入队列，这也就意味着当小徐出队列时，队列中剩下的都是小徐的朋友，然后按照顺序让小明出队列，出队列的同时让小明的朋友入队列，然后让小王出队列（第二圈结束），出队列的同时让小王的朋友入队列，这时小徐的朋友都出队列了，剩下的都是小徐朋友的朋友（也就是处于第三圈上的好友），这个时候就可以将队列中的好友推荐给小徐，不断循环这个步骤，就可以一步一步扩大好友圈。

2. 队列的功能实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。那么确定了使用链表，就要考虑是使用双向链表还是单向链表，因为双向链表肯定是可以实现队列功能的，但是我们优先考虑能不能使用单链表来实现，如果单链表能实现，就不使用双向链表，因为单向链表比双向链表更加节省空间。

2.1 一级指针还是二级指针

在数据结构的学习中，已经讨论过很多次到底是用一级指针还是二级指针的问题，我也混淆了很久，最简单的记忆方法就是去看你到底要不要去通过形参ppehad改变实参plist，若不不想改变实参，那形参就直接用一级指针接收即可，如果想要通过形参改变实参，那么就使用二级指针接收，因为只有对二级指针进行一次解引用，才能读取到实参部分，然后对*pphead的改变，就相当于是对plist的改变。

在队列的实现中，因为队列的本质是单链表，我在学习单链表的过程中，是使用二级指针来完成相应的功能的，在学习双向链表中，是使用一级指针来完成相应的功能的，这是因为在双向链表中引入了“头节点”，也就是“哨兵位”，因为指向哨兵位的指针plist是不需要被改变的，所以用一级指针接收即可，这一点我在双向链表的章节中也提到过；所以对于这节中的队列，为了避免二级指针的繁琐，也直接使用一级指针来接收，但是是使用一种新的方式来解决这个问题：直接将指向链表头节点和尾节点的指针封装成一个结构体，所以想要改变这两个指针，就相当于改变这个结构体，比如要改变实参int p，那形参就传int*p（也就是接收整型变量p的地址&p），要改变实参int* p，那就传int** pp（也就是接收指针p的地址），所以现在要改变实参结构体变量stuct Name p，那么形参就传struct Name* p(也就是接收结构体变量p的地址&p)，这就转化为了只需要传一级指针，而不是二级指针。

typedef int QDataType; // 链式结构：表示队列 typedef struct QListNode { struct QListNode* next; QDataType val; }QNode; // 队列的结构 typedef struct Queue { QNode* phead; QNode* ptail; int size;//存入一个数据就计数一次，方便后面计数函数的实现，同时也降低了时间复杂度 }Queue; // 初始化队列 void QueueInit(Queue* pq); // 队尾入队列 void QueuePush(Queue* pq, QDataType x); // 队头出队列 void QueuePop(Queue* pq); // 获取队列头部元素 QDataType QueueFront(Queue* pq); // 获取队列队尾元素 QDataType QueueBack(Queue* pq); // 获取队列中有效元素个数 int QueueSize(Queue* pq); // 检测队列是否为空 bool QueueEmpty(Queue* pq); // 销毁队列 void QueueDestroy(Queue* pq);

这种方法既避免了传多个参数，又避免了传二级指针！

2.2 队列的初始化

代码实现：

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

2.3 入队列的实现

// 队尾入队列 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode));//开辟动态空间 if (newnode == NULL) { perror("malloc fail"); return; } //进行初始化 newnode->val = x; newnode->next = NULL; //进行插入 if (pq->ptail == NULL) { pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; }

2.4 出队列的实现

// 队头出队列 void QueuePop(Queue* pq) { assert(pq); assert(pq->size != 0); //一个节点的情况 if (pq->phead ->next == NULL) { free(pq->phead);//free的是指针指向的节点，而不是释放指针，注意区别 pq->phead = pq->ptail = NULL; } //多个节点的情况 else { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->size--; }

注意：这里面的free函数释放的是指针所指向的节点的空间，也就是malloc动态开辟的内存空间，而不是指针pq->phead或者pq->ptail。

2.5 队列其他功能的实现

// 获取队列头部元素 QDataType QueueFront(Queue* pq) { assert(pq); assert(pq->phead);//头节点如果为NULL，说明没有节点存入，那读取就没有意义了 return pq->phead->val; } // 获取队列队尾元素 QDataType QueueBack(Queue* pq) { assert(pq); assert(pq->ptail);//尾节点如果为NULL，说明没有节点存入，那读取就没有意义了 return pq->ptail->val; } // 获取队列中有效元素个数 int QueueSize(Queue* pq) { assert(pq); return pq->size; } // 检测队列是否为空 bool QueueEmpty(Queue* pq) { asswet(pq); return pq->size == 0; } // 销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QNode* pcur = pq->phead; while (pcur) { QNode* next = pcur->next; free(pcur); pcur = next; } pq->phead = pq->ptail = NULL; pq->size=0; }