The Queue Data Structure:

Queue is a linear data structure. Here we follow that FIFO method i,e the First In First Out.For example, while standing in a Queue, the person whose reaches the counter first which means the person which is in the front of the Queue gets the ticket first. Similarly, in a queue, the elements are inserted at the last and deleted from the front. Unlike stack, we cannot do insertion and removal from the same end.
Real world examples:
Vehicles in a toll tax bridge.The vehicle that comes first leaves the booth first. The vehicle that comes last leaves last. Therefore, it follows the first-in-first-out (FIFO) strategy of a queue.

* Luggage checking machine. Luggage checking machine checks the luggage first that comes first. Therefore, it follows the FIFO principle of the queue.
Time Complexity:
Average case:
Access: O(n)
Insertion: O(1)
Deletion:O(n)
Basic Functions of Queue:
*Enqueue(insertion)
*Dequeue(deletion)
*is Empty(to check whether the queue is empty)
*Peek(Gets the element at the front of the queue without removing it)
*is Full(to check whether the queue is full.
A queue can be implemented in two ways
*Using Linked list
*Using Array
Types of Queue:
- Circular Queue
- Priority Queue
- Deque
Queue using Linked list:
Node class:
Here the Node class is defined. It contains the data part and the next part.

The enqueue function:
The insert at last function is used for this operation. We use two pointers here the front and the rear. The front points to the head since insertion is to be done the new node is inserted in the next part of the rear.

The dequeue function:
Since we have to perform insert at the front function we just have moved the pointer from front to the next.

is Empty function:
If we need to check whether the queue is empty first we have to check whether front is null.
Similarly, queue data structure can be implemented also using arrays.
You can try implementing a queue using stacks. hint: We need two stacks to implement a Queue because insertion and deletion cannot take place at the same end.
