队列这东西，其实就是“先进先出”（fifo）

队列这东西，其实就是“先进先出”（FIFO），大家每天在食堂或者医院排队的时候，脑子里早就已经有这个算法的影子了。把排队的人看成是数据流，先来的肯定就先被服务，后来的只能在后面老老实实等着。这种先到先走的规矩，就是队列的核心所在。再想想栈和队列，那就是两个完全相反的兄弟。栈是入口出口在一头，所以是“后进后出”；队列入口和出口各有一处，自然就是“先进先出”。一个像电梯那样后进先出，一个像栈桥那样先进先出，差别大得很。C++里定义一个队列特别简单，只需要引入队列头文件，再写一个std::queue变量就行了。往后不管是入队还是出队，都在这个通道里完成。常用的操作也很简单：push是把元素扔到队尾，就像把餐盘放在传送带上一样；front可以让你看看队首是谁；back能告诉你队尾是谁；pop就是让队首的元素离开；empty判断队列是不是空的；size算算有多少个元素。这些操作时间复杂度基本都是O(1)，特别高效。除了日常排队这种简单的模型，队列在广度优先搜索（BFS）里面用处特别大。它从根节点开始一层一层往外扩散，每层的入队和出队都很顺畅，时间复杂度和空间复杂度都能控制住。不管是迷宫搜索还是图遍历，队列都在背后默默地帮忙加速呢。