常考知识点-队列讲解

🎈 作者：Linux猿

🎈 简介：CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬

在北工大历年考研数据结构中，队列是一个常考知识点，不但要掌握好队列的基本性质：队列的出队、入队、队列指针的操作等，还要学会与其它知识点的结合，比如：图的广度优先搜索、树的层次遍历等。接下来小编就为大家介绍下队列。

一、什么是队列？

举个栗子，当你在食堂买饭的的时候，需要排队，先排队的人可以先打饭，一个一个来，等前面人打饭结束之后，后面才能打饭，而后来的人需要排在队伍的后面，不能插队，即先进先出。同时，一定要与栈区分开，栈是先进后出。

二、性质

1、队列只允许在一端插入数据，另一端删除数据。允许插入的一端称为队尾，允许删除的一端称为队头。

2、队列是一种先进先出的线性表。

3、队列在C++STL中的基本操作如下：

queue<int> Q;//申请一个int类型的队列

Q.front(); //获取队列首元素

Q.push();//将元素压入队列，如Q.push(2);

Q.pop();//删除队首元素

Q.empty();//判断队列是否为空，为空返回真

Q.size();//获取队列元素的个数

三、真题解读：

北京工业大学2014年硕士研究生入学考试试题--896

填空题：

在图的广度优先搜索遍历算法中，使用的辅助结构是________。

【解题思路】

图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的广度优先遍历一般是先遍历到的顶点先访问，然后访问与该顶点相关的顶点入队，该性质和队列的性质相符合，故采用队列进行操作。

图的广度优先遍历使用队列方法，任意找出一顶点，先放入队列中，然后依次查找与该顶点相关的其他顶点，同时删除队首，以新的队首元素继续遍历与该节点相关的顶点；循环执行即可获得图的广度优先遍历。

如下图，该图为5个顶点的无向图。

图的广度优先遍历队列的存储过程如下，其中front表示队首位置，front之前均为已出队的数据。

四、小结

关于队列的知识点还有循环队列、双向队列，循环队列可以防止队列元素溢出，充分利用空间；双向队列两端都可插入和删除，便于操作，后续会针对循环队列和双向队列进行更为详细的讲解，敬请期待！

CSDN博客专家🏆，华为云享专家🏆，Linux、C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！

欢迎小伙伴们点赞👍、收藏⭐、留言💬