Queue

Queue 是一种先进先出(FIFO)的数据结构

队列操作 Operations of Queue:

enqueue and dequeue

The insert operation is also called enqueue and the new element is always added at the end of the queue.

The delete operation is called dequeue. You are only allowed to remove the first element.

Queue Usage Example

Java - peek(), offer(), poll(), size()

// "static void main" must be defined in a public class.
public class Main {
    public static void main(String[] args) {
        // 1. Initialize a queue.
        Queue<Integer> q = new LinkedList();
        // 2. Get the first element - return null if queue is empty.
        System.out.println("The first element is: " + q.peek());
        // 3. Push new element.
        q.offer(5);
        q.offer(13);
        q.offer(8);
        q.offer(6);
        // 4. Pop an element.
        q.poll();
        // 5. Get the first element.
        System.out.println("The first element is: " + q.peek());
        // 7. Get the size of the queue.
        System.out.println("The size is: " + q.size());
    }
}

In Java, Queue interface, with a couple of implementation e.g. BlockingQueue, LinkedList, and PriorityQueue.

Read more: https://javarevisited.blogspot.com/2017/03/difference-between-stack-and-queue-data-structure-in-java.html#ixzz5cXO0AOx6

Queue Implementation

Queue Using Array

Circular Queue

Use a fixed-size array and two pointers to indicate the starting position and the ending position. And the goal is to reuse the wasted storage we mentioned previously.

Queue using Linked List

...

Queue and BFS

BFS

Two main scenarios of using BFS: do traversal or find the shortest path

--

One common application of Breadth-first Search (BFS) is to find the shortest path from the root node to the target node.

Similar to tree's level-order traversal, the nodes closer to the root node will be traversed earlier.

The processing order of the nodes is the exact same order as how they were added to the queue, which is First-in-First-out (FIFO). That's why we use a queue in BFS.

BFS Template I - Pseudocode

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        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;          // there is no path from root to target
}

BFS Template II - Pseudocode - using hashset to avoid visiting same node twice

/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    Set<Node> used;     // store all the used nodes
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    add root to used;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        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;          // there is no path from root to target
}

There are two cases you don't need the hash set used:

1. You are absolutely sure there is no cycle, for example, in tree traversal;

2. You do want to add the node to the queue multiple times.