# Queue

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

`enqueue`

and `dequeue`

Theinsertoperation is also calledenqueueand the new element is always`added at the end of the queue`

.Thedeleteoperation is calleddequeue. You are only allowed to`remove the first element`

.

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**.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....

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.

Last modified 2yr ago