Queue and breadth-first search

This is the 25th day of my participation in Gwen Challenge

Queue: First-in, first-out data structure

In a queue, first in, first out (FIFO), the first element to queue is first out.

Implementation of a simple queue

class MyQueue {
    / / the queue
    private List<Integer> data;         
    // Head pointer
    private int p_start;   

    public MyQueue(a) {
        data = new ArrayList<Integer>();
        p_start = 0;
    }
    /** * Adds an element from the end of the queue, returns true */ on success
    public boolean enQueue(int x) {
        data.add(x);
        return true;
    };    
    /** * Removes an element from the end of the queue, returns true */ on success
    public boolean deQueue(a) {
        if (isEmpty() == true) {
            return false;
        }
        p_start++;
        return true;
    }
    /** * get the header element */
    public int Front(a) {
        return data.get(p_start);
    }
    /** * Check whether the queue is empty */
    public boolean isEmpty(a) {
        returnp_start >= data.size(); }}Copy the code

Disadvantages of simple queues

The above implementation is simple, but in some cases inefficient. As the starting pointer moves, more and more space is wasted. When we have space constraints, it’s hard to accept.

Circular queue

With circular queues, we can use a fixed-size array and two Pointers to indicate the start and end positions, in order to reuse wasted storage. A circular queue is a linear data structure that operates on a FIFO (first-in, first-out) basis and the tail of the queue is connected behind the head of the queue to form a loop. It is also known as a “ring buffer”. One of the nice things about a circular queue is that we can use the space that the queue has previously used. In a normal queue, once a queue is full, we cannot insert the next element, even though there is still space in front of the queue. But with circular queues, we can use that space to store new values.

The implementation of a circular queue

class MyCircularQueue {
	private int[] data;
	private int head;// queue head pointer
	private int tail;// end of queue pointer
	private int size;

    /** Initializes a queue of length k */
    public MyCircularQueue(int k) {
        data = new int[k];
        head = -1;
        tail = -1;
        size = k;
    }
    
    /** return true */ on success
    public boolean enQueue(int value) {
        if(isFull()){
        	return false;
        }
        if(isEmpty()){
        	head = 0;
        }
        tail = (tail+1)%size;
        data[tail] = value;
        return true;
    }
    
    /** return true */ on success
    public boolean deQueue(a) {
        if(isEmpty()){
        	return false;
        }
        if(head == tail){
        	head = -1;
        	tail = -1;
        	return true;
        }
        head = (head+1)%size;
        return true;
    }
    
    /** get the header element */
    public int Front(a) {
        if(isEmpty()){
        	return -1;
        }
        return data[head];
    }
    
    /** Get the last element */
    public int Rear(a) {
        if(isEmpty()){
        	return -1;
        }
        return data[tail];
    }
    
    / * * to * / empty
    public boolean isEmpty(a) {
        return head == -1;
    }
    
    /** Determine the queue is full */
    public boolean isFull(a) {
        return ((tail+1)%size) == head; }}Copy the code

Queue and breadth-first search

Breadth-first search (BFS) means that nodes closer to the root are traversed earlier. Order of nodes: In the first round, we deal with the root node. In the second round, we deal with the node next to the root; In round three, we deal with nodes two steps from the root; And so on.

Queue enqueue and unqueue order: The root node is queued first. Then, in each round, we process nodes that are already in the queue one by one and add all neighbors to the queue. Note that newly added nodes are not traversed immediately, but are processed in the next round.

Nodes are processed in exactly the same order as they were added to the queue, first-in, first-out (FIFO). That’s why we use queues in BFS.

Pseudocode that a node may be accessed multiple times

/** * Get the shortest path */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // Store all nodes to be processed
    int step = 0;       // Depth of traversal
    // initialize
    add root to queue;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // Whether the node is in the queue of the node to be processed
        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;          // Return -1 if no node exists
}
Copy the code

Set filter criteria so that the node is not reused

/** * Get the shortest path */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // Store all nodes to be processed
    Set<Node> used;     // All nodes traversed exist
    int step = 0;       // Depth of traversal
    // initialize
    add root to queue;
    add root to used;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // Whether the node is in the queue of the node to be processed
        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;          // Return -1 if no node exists
}
Copy the code