# 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()`

```java
// "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

```java
/**
 * 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

```java
/**
 * 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.