Queue Basics

Queue data structure holds elements in FIFO (First in, First out) order. This means elements are removed from a queue in the same order as they are added to the queue. In example below, integers 1,5,2,4 are added to the Queue and then two integers are removed from queue:

•	Add 1, Queue contents:  1
•	Add 5, Queue contents: 1 <- 5
•	Add 2, Queue contents: 1 <- 5 < -2
•	Add 4, Queue contents: 1 <- 5 <- 2 <- 4
•	Remove an integer, Queue contents:  5 <- 2 <- 4
•	Remove an integer, Queue contents:  2 <- 4

Use cases for Queues

Order/ Request processing, where we need to process orders in the same order that the same were received.

Task scheduling.

Caching.

Tree traversal (using BFS).

Time Complexity of Java Queue operations

Following table shows time complexity metrics for an Queue operations:

Operation	Complexity
Add operation.	O(1)
Remove/Delete operation.	O(1)
Peek operation.	O(1)
Get size of Queue.	O(1)

Types of Queues.

Below are main types of Queues:

FIFO Queue: Queue that processes elements in FIFO order.

Circular Queue: fixed capacity Queue where last element of Queue points to first element of Queue.

Deque: Queue which allows elements to be added and removed from both ends.

Priority Queue: Here elements are stored in queue as per priority. For example elements are stored in sorted ascending order instead of input order. Removal removes the first element in the Queue as per sorted/ priority order.

Queues in Java JDK API.

Java provides Queue interface. Below are some java classes implement the Queue interface, so these can be used as Queues as per need:

•	LinkedList
•	LinkedBlockingQueue
•	ConcurrentLinkedQueue
•	ArrayDeque
•	LinkedBlockingDeque
•	ConcurrentLinkedDeque
•	PriorityQueue

Example code for instantiating using LinkedList as queue:

Queue< Integer > pgQueue=new LinkedList<Integer>();

Now we can perform operations like add(), remove(),element() on pgQueue instance.