【算法】队列理论就是这么简单

一、背景

前面分享了《数组就是简单系列》，接下来就是分享队列和栈了。

我们知道，我们可以通过索引下标来随机访问数组的元素。
但是有时候，我们会对访问顺序进行限制。
比如先进先出，就对应队列数据结构；后进先出对应栈数据结构。

接下来的几篇文章会介绍队列和栈的基础知识，以及用来解决什么问题，即实践与应用。

下面我们先来看看队列的基础知识和实践吧。

二、队列的定义

队列是一种先进先出的数据结构。
先进先出英文是 First In First Out，简称为FIFO。
具体含义就是首先处理添加到队列中的第一个元素。

一般，插入操作称为入队（enqueue），具体实现是将新元素放在了队列的最后。
而删除操作称为出队（dequeue），即将最前面的元素删除。

当然，语言内置的队列名字有点不一样。
名字大概是这样：入队(push)、出队(pop)、是否为空(empty)、队头(front)、队尾(back)、大小(size)。

三、队列初步实现

面试的时候，我经常会问如何使用数组实现一个队列。

一般都能回答上来，即使用一个下标表示队头和队尾。
如果个别几个回答出队时所有数据向前移动时，我就会和他探讨这个操作的复杂度，以及有没有优化空间。
经过的这样讨论，大家都可以想到使用下标来指向队头和队尾。

比如下面是使用vector实现的一个简单的队列，当然，这里没有进行边界检查。

class MyQueue {
    private:
        vector<int> data;
        int p_start;
    public:
        MyQueue() {p_start = 0;}
        void push(int x) {
            data.push_back(x);
        }
        void pop() {
            p_start++;
        }
        int front() {
            return data[p_start];
        }
};

上面这个实现是很简单，但是也有很多问题。
比如不断的入队和出队，data这个容器就会越来越大，但是前面的空间无法利用起来。

所以，这个时候，我会问面试者：该如何优化才能利用这些空间呢？

四、循环队列

面对空间问题，几乎所有人都能提出循环队列这个答案。

即默认容器是定长的。
通过维护一个头指针和尾指针来标记开始位置和结束位置，从而利用前面的空间。

这个时候有四连问：
1.入队该如何实现？
2.出队又该如何实现？
3.有什么注意事项吗？
4.怎么判断是否满了？

这四个如果都可以答上来，一般就可以说明这个人的基础知识还可以。
大概实现如下：

五、广度优先搜索

我们经常通过队列来实现广度优先搜索。
最经典的问题是寻找从根结点到目标结点的最短路径。

比如对于这样一个图，我们首先根节点A入队。

然后，从队首取出一个元素，将其所有的子节点B C D加入到队列。

接着，依次从队首取一个元素，并将元素的子节点加入到队列（重复的不要加）。

这样不断循环下去，就可以遍历图上的所有可以到达的点。

而且，可以看到，使用队列来搜索的话，是一层层的搜索的。
每搜索一层，子节点的距离就是当前节点与根节点的距离加一。
所以我们搜索的路径，就是根节点到当前节点的最短路径。

这里面有一个很关键的地方：子节点不能重复加入队列。
一般我们会使用一个容器来标记节点是否已经加入队列。

下面我们来看三道题吧。

六、岛屿的个数

题意：输入一个二维数组，值是0海水或1陆地。陆地上下左右方向挨着时代表陆地连接着。
求互相独立的岛屿个数。

思路：扫描二维数组，找到一个陆地后，就使用队列BFS将连续的陆地都标记为非陆地。
这样进行下去，既可以统计到岛屿的总个数。

注意事项：对于二维数组的上下左右，需要判断是否越界。
这个在《数组即使这么简单》系列里曾介绍过。

七、打开转盘锁

题意：有一个四个圆形拨轮的转盘锁，其实位置始终是0000，求最少旋转几下可以到达目标位置。
限制条件：有一些数字被封杀了，是死亡数字，遇到就代表无解，返回-1。

思路：典型的BFS题。只是这里多了一个死亡数字的限制条件。
所以搜索的时候，需要进行一个判断：遇到死亡数字时不能递归搜索。
具体见代码注释吧。

八、完全平方数

题意：给一个正整数，可以选一些平方数（允许重复），使得和等于这个数。求平方数最少可以是多少个？

思路：这道题方法很多，这里我们需要使用BFS的思想来做。
对于BFS，则是枚举一个平方数可以计算出那些数字，接着是两个平方数可以计算出那些数字，这样不断进行下去，直到找到答案。
队列初始条件可以是0。之后每次出队一个数字时，要加上所有的平方数。如果没找到答案，则去重入队。

注意事项：对于和已经大于给定的数字时，就不需要入队了。

九、最后

这篇文章简单的介绍了队列的基础知识与应用实践。
对于队列的实现，面试的时候经常会被问到，比如如何使用定长数组实现，如何进出队，满了怎么办等等。
而对于队列的应用，则主要用于解决搜索最优问题：即通过最少步数从起始位置到达目标位置。

之所以会这样，是因为队列对应于广度优先搜索。
其几何意义就是一层层的搜索，每搜一层，深度越深，那步数自然就越大了。
如果存在答案，则首次遇到的就是最优解。

-EOF-