---

What is a Queue Data Structure?

A queue is a container of objects (a linear collection) that are inserted and removed according to the first-in first-out (FIFO) principle. An excellent example of a queue is a line of students in the food court. New additions to a line made to the back of the queue, while removal (or serving) happens in the front. In the queue only two operations are allowed enqueue and dequeue. Enqueue means to insert an item into the back of the queue, dequeue means removing the front item. The picture demonstrates the FIFO access.

Explain operations of Queue

The queue is a linear data structure that permits insertion of a new element at one end and deletion of an element at the other end.
-- The end at which insertion of a new element can take place is called ‘ rear ‘ and the end at which deletion of an element take place is called ‘ front ‘.
-- The first element that gets added into the queue is the first one to get removed from the list, Hence Queue is also referred to as First-In-First-Out ( FIFO ) list.
-- Queue must be created as empty.
-- Whenever an element is inserted into the queue, it must be checked whether the queue is full or not.
-- Whenever an element is deleted from the queue, it must be checked whether the queue is empty or not.
-- We can implement the queue ADT either with an array or linked list.

The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

Queue is also an abstract data type or a linear data structure, just like stack data structure, in which the first element is inserted from one end called the REAR(also called tail), and the removal of existing element takes place from the other end called as FRONT(also called head). This makes queue as FIFO(First in First Out) data structure, which means that element inserted first will be removed first.

Operations on Queue:

Mainly the following four basic operations are performed on queue:

Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
Front: Get the front item from queue.
Rear: Get the last item from queue.

Basic features of Queue

1. Like a stack, the queue is also an ordered list of elements of similar data types.
2. The queue is a FIFO( First in First Out ) structure.
3. Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.
4. peek( ) function is often used to return the value of the first element without dequeuing it.

Steps for ENQUEUE operation

1. Check if the queue is full or not.
2. If the queue is full, then print overflow error and exit the program.
3. If the queue is not full, then increment the tail and add the element.

Steps for DEQUEUE operation

1. Check if the queue is empty or not.
2. If the queue is empty, then print underflow error and exit the program.
3. If the queue is not empty, then print the element at the head and increment the head.

Types of Queue

1. Normal queue
2. Circular queue
3. Priority queue

Applications of Queue

Queue, as the name suggests is used whenever we need to manage any group of objects in an order in which the first one coming in, also gets out first while the others wait for their turn, like in the following scenarios:

1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
2. In real life scenario, Call Center phone systems use Queues to hold people calling them in an order, until a service representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive i.e First come first served.

Another application:

1. Execution of Threads
2. Job Scheduling
3. Event queuing
4. Message Queuing

---