队列与BFS搜索

队列(queue)是一种简单的数据结构,它所遵循的规则是先进先出(First in First out, FIFO),对比LIFO的数据结构“栈”,你可以阅读[这篇文章]。这里所说的队列和我们现实中的队列是一样的,就比如说公交车排队,早到的,排在靠前位置的人自然可以优先上车(假设大家都很文明),利用这种特性,人们可以用来管理各种各样需要按照先后循序的事物,比如银行,因为银行的服务窗口有限,不能同时给所有人提供服务,所以利用计算机提供一个队列系统,给客户一个排队号码,计算机系统可以根据这个排队号码的大小来决定为谁优先提供服务。 按照和栈类似的介绍方法,为了使代码的表意更加明确,我使用C++标准库提供的队列适配器queue来构造队列这种数据结构。 使用queue需要引用头文件: [crayon-5a5fd0663909a622215776/] 初始化一个空的队列: [crayon-5a5fd066390ae393650748/] 令一个元素进入队尾: [crayon-5a5fd066390b232

栈(stack)是一种数据结构,它遵循一个简单的规则,即后进先出(Last in First out, LIFO)。 栈的工作方式很容易理解,用一个图表形象的表示就是这样,见图1: 这个只有上端开口的容器,就是用来存放数据的栈,我们要取容器中的东西,必须从最顶端开始,一个一个拿掉,才能取到我们想要的,而如果要放一个元素呢,也只能放在最顶端,这也就是栈的后进先出原则。 这样的数据结构可以使用C++标准库来实现,非常简单,下面就对C++标准库中的栈做一点简介: C++提供了三种顺序容器(sequential container)vector(支持快速随机访问)、list(支持快速插入删除)、deque(双端队列),vector比较类似与数组,而list则更加像链表结构。C++标准库为顺序容器提供了三种容器适配器(adaptor), 不要被名字吓到,所谓适配器,就像你的电脑电源适配器一样,将交流电(这里是顺序容器)做出一定的调整,来适合电脑工作,也就是说,容器适配器,是利用容器来...