队列与BFS搜索

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

[STL]排列函数next_permutation()

我们自然知道C++的STL提供了丰富的基本数据结构以及算法支持,但事实上在使用中,我们常常容易忽略它,因为学习STL本身也需要一定的时间成本。STL基于泛型编程(Generic Programming, GP),很多人看到这个术语就打了退堂鼓,之内诸如迭代器之流,也更是云里雾里,不知所云也不想探究之,所以明明很好的工具就在手边,但是却弃之不用,着实可惜。 认识这个函数纯属偶然,今天在POJ上做题,看到了一道题[1]的Discuss中提示使用这个函数会使大大简化题目的难度,那么这个函数究竟就以用来做什么呢? 从标题我们就可以知道,可以这个函数用来获取一组元素的全排列,根据其定义,当你输入一组元素后,函数会将这组元素进行排列,排列结果为这组元素按字典序的下一个排列。这里先解释两个名词:一个是字典序,一个是全排列。 所谓字典序,顾名思义,就是像字典上那样的规则对元素进行排列: 我这里从身旁随手的一本字典翻开一页,单词如下: career careerist carefree careful ca

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