队列和广度优先搜索-一一网

这是我参与更文挑战的第25天，活动详情查看：更文挑战

队列：先入先出的数据结构

在队列中，遵循先入先出（FIFO）的原则，先入队的元素将优先出队。

简单队列的实现

class MyQueue {
    // 队列
    private List<Integer> data;         
    // 对头指针
    private int p_start;   

    public MyQueue() {
        data = new ArrayList<Integer>();
        p_start = 0;
    }
    /** 
    * 入队操作
    * 从队尾加入一个元素，成功返回true
    */
    public boolean enQueue(int x) {
        data.add(x);
        return true;
    };    
    /** 
    * 出队操作
    * 从队尾删除一个元素，成功返回true
    */
    public boolean deQueue() {
        if (isEmpty() == true) {
            return false;
        }
        p_start++;
        return true;
    }
    /** 
    * 获取队头元素 
    */
    public int Front() {
        return data.get(p_start);
    }
    /** 
    * 判断是否为空队列
    */
    public boolean isEmpty() {
        return p_start >= data.size();
    }     
}
复制代码

简单队列的缺点

上面的实现很简单，但在某些情况下效率很低。随着起始指针的移动，浪费了越来越多的空间。当我们有空间限制时，这将是难以接受的。

循环队列

使用循环队列，我们可以使用固定大小的数组和两个指针来指示起始位置和结束位置，目的是重用被浪费的存储。循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

循环队列的实现

class MyCircularQueue {
	private int[] data;
	private int head;//队头指针
	private int tail;//队尾指针
	private int size;

    /** 初始化长度为k的队列 */
    public MyCircularQueue(int k) {
        data = new int[k];
        head = -1;
        tail = -1;
        size = k;
    }
    
    /** 入队，成功则返回true */
    public boolean enQueue(int value) {
        if(isFull()){
        	return false;
        }
        if(isEmpty()){
        	head = 0;
        }
        tail = (tail+1)%size;
        data[tail] = value;
        return true;
    }
    
    /** 出队，成功则返回true */
    public boolean deQueue() {
        if(isEmpty()){
        	return false;
        }
        if(head == tail){
        	head = -1;
        	tail = -1;
        	return true;
        }
        head = (head+1)%size;
        return true;
    }
    
    /** 获取队头元素 */
    public int Front() {
        if(isEmpty()){
        	return -1;
        }
        return data[head];
    }
    
    /** 获取队尾元素 */
    public int Rear() {
        if(isEmpty()){
        	return -1;
        }
        return data[tail];
    }
    
    /** 判空 */
    public boolean isEmpty() {
        return head == -1;
    }
    
    /** 判断队满 */
    public boolean isFull() {
        return ((tail+1)%size) == head;
    }
}
复制代码

队列和广度优先搜索

广度优先搜索（BFS）即越是接近根节点的节点将越早地遍历。结点的处理顺序：在第一轮中，我们处理根结点。在第二轮中，我们处理根结点旁边的结点；在第三轮中，我们处理距根结点两步的结点；等等。

队列的入队和出队顺序：首先将根结点排入队列。然后在每一轮中，我们逐个处理已经在队列中的结点，并将所有邻居添加到队列中。值得注意的是，新添加的节点不会立即遍历，而是在下一轮中处理。

结点的处理顺序与它们添加到队列的顺序是完全相同的顺序，即先进先出（FIFO）。这就是我们在 BFS 中使用队列的原因。

节点可能被多次访问到的伪代码

/**
 * 获取最短路径
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // 存放待处理的所有节点
    int step = 0;       // 遍历的深度
    // initialize
    add root to queue;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // 节点是否在待处理节点的队列中
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                add next to queue;
            }
            remove the first node from queue;
        }
    }
    return -1;          // 不存在节点时返回-1
}
复制代码

设置过滤条件，节点不被重复使用

/**
 * 获取最短路径
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // 存放待处理的所有节点
    Set<Node> used;     // 存在被遍历过的所有节点
    int step = 0;       // 遍历的深度
    // initialize
    add root to queue;
    add root to used;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // 节点是否在待处理节点的队列中
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                if (next is not in used) {
                    add next to queue;
                    add next to used;
                }
            }
            remove the first node from queue;
        }
    }
    return -1;          // 不存在节点时返回-1
}
复制代码