Queue

1. A queue can be defined as an ordered list which enables insert

operations to be performed at one end called REAR and delete operations
to be performed at another end called FRONT.

2. Queue is referred to be as First In First Out list.

3. For example, people waiting in line for a rail ticket form a queue.

Applications of Queue
Due to the fact that queue performs actions on first in first out basis which
is quite fair for the ordering of actions. There are various applications of
queues discussed as below.

1. Queues are widely used as waiting lists for a single shared resource like
printer, disk, CPU.
2. Queues are used in asynchronous transfer of data (where data is not being
transferred at the same rate between two processes) for eg. pipes, file IO,
sockets.
3. Queues are used as buffers in most of the applications like MP3 media
player, CD player, etc.
4. Queue are used to maintain the play list in media players in order to add
and remove the songs from the play-list.
5. Queues are used in operating systems for handling interrupts.
Types of Queue
In this article, we will discuss the types of queue. But before moving
towards the types, we should first discuss the brief introduction of the
queue.

What is a Queue?
Queue is the data structure that is similar to the queue in the real world. A
queue is a data structure in which whatever comes first will go out first,
and it follows the FIFO (First-In-First-Out) policy. Queue can also be
defined as the list or collection in which the insertion is done from one end
known as the rear end or the tail of the queue, whereas the deletion is
done from another end known as the front end or the head of the queue.

The real-world example of a queue is the ticket queue outside a cinema

hall, where the person who enters first in the queue gets the ticket first,
and the last person enters in the queue gets the ticket at last. Similar
approach is followed in the queue in data structure.

The representation of the queue is shown in the below image -

Now, let's move towards the types of queue.

Types of Queue
There are four different types of queue that are listed as follows -
 o Simple Queue or Linear Queue
o Circular Queue
o Priority Queue
o Double Ended Queue (or Deque)

Let's discuss each of the type of queue.

Simple Queue or Linear Queue

In Linear Queue, an insertion takes place from one end while the deletion
occurs from another end. The end at which the insertion takes place is
known as the rear end, and the end at which the deletion takes place is
known as front end. It strictly follows the FIFO rule.

The major drawback of using a linear Queue is that insertion is done only
from the rear end. If the first three elements are deleted from the Queue,
we cannot insert more elements even though the space is available in a
Linear Queue. In this case, the linear Queue shows the overflow condition
as the rear is pointing to the last element of the Queue.
To know more about the queue in data structure, you can click the link
- https://www.javatpoint.com/data-structure-queue

Circular Queue
In Circular Queue, all the nodes are represented as circular. It is similar to
the linear Queue except that the last element of the queue is connected
to the first element. It is also known as Ring Buffer, as all the ends are
connected to another end. The representation of circular queue is shown
in the below image -

The drawback that occurs in a linear queue is overcome by using the

circular queue. If the empty space is available in a circular queue, the new
element can be added in an empty space by simply incrementing the
value of rear. The main advantage of using the circular queue is better
memory utilization.

To know more about the circular queue, you can click the link
- https://www.javatpoint.com/circular-queue

Priority Queue
It is a special type of queue in which the elements are arranged based on
the priority. It is a special type of queue data structure in which every
element has a priority associated with it. Suppose some elements occur
with the same priority, they will be arranged according to the FIFO
principle. The representation of priority queue is shown in the below
image -
Insertion in priority queue takes place based on the arrival, while deletion
in the priority queue occurs based on the priority. Priority queue is mainly
used to implement the CPU scheduling algorithms.

There are two types of priority queue that are discussed as follows -

o Ascending priority queue - In ascending priority queue, elements can

be inserted in arbitrary order, but only smallest can be deleted first.
Suppose an array with elements 7, 5, and 3 in the same order, so,
insertion can be done with the same sequence, but the order of deleting
the elements is 3, 5, 7.
o Descending priority queue - In descending priority queue, elements
can be inserted in arbitrary order, but only the largest element can be
deleted first. Suppose an array with elements 7, 3, and 5 in the same
order, so, insertion can be done with the same sequence, but the order of
deleting the elements is 7, 5, 3.

To learn more about the priority queue, you can click the link
- https://www.javatpoint.com/ds-priority-queue

Deque (or, Double Ended Queue)

In Deque or Double Ended Queue, insertion and deletion can be done from
both ends of the queue either from the front or rear. It means that we can
insert and delete elements from both front and rear ends of the queue.
Deque can be used as a palindrome checker means that if we read the
string from both ends, then the string would be the same.

Deque can be used both as stack and queue as it allows the insertion and
deletion operations on both ends. Deque can be considered as stack
because stack follows the LIFO (Last In First Out) principle in which
insertion and deletion both can be performed only from one end. And in
deque, it is possible to perform both insertion and deletion from one end,
and Deque does not follow the FIFO principle.

The representation of the deque is shown in the below image -

To know more about the deque, you can click the link
- https://www.javatpoint.com/ds-deque

There are two types of deque that are discussed as follows -

o Input restricted deque - As the name implies, in input restricted queue,

insertion operation can be performed at only one end, while deletion can
be performed from both ends.

o Output restricted deque - As the name implies, in output restricted

queue, deletion operation can be performed at only one end, while
insertion can be performed from both ends.

Now, let's see the operations performed on the queue.

Operations performed on queue
The fundamental operations that can be performed on queue are listed as
follows -

o Enqueue: The Enqueue operation is used to insert the element at the rear
end of the queue. It returns void.
o Dequeue: It performs the deletion from the front-end of the queue. It also
returns the element which has been removed from the front-end. It
returns an integer value.
o Peek: This is the third operation that returns the element, which is
pointed by the front pointer in the queue but does not delete it.
o Queue overflow (isfull): It shows the overflow condition when the queue
is completely full.
o Queue underflow (isempty): It shows the underflow condition when the
Queue is empty, i.e., no elements are in the Queue.

Now, let's see the ways to implement the queue.

Ways to implement the queue

There are two ways of implementing the Queue:

o Implementation using array: The sequential allocation in a Queue can

be implemented using an array. For more details, click on the below
link: https://www.javatpoint.com/array-representation-of-queue
o Implementation using Linked list: The linked list allocation in a Queue
can be implemented using a linked list. For more details, click on the
below link: https://www.javatpoint.com/linked-list-implementation-of-
queue

Array representation of Queue

We can easily represent queue by using linear arrays. There are two
variables i.e. front and rear, that are implemented in the case of every
queue. Front and rear variables point to the position from where insertions
and deletions are performed in a queue. Initially, the value of front and
queue is -1 which represents an empty queue. Array representation of a
queue containing 5 elements along with the respective values of front and
rear, is shown in the following figure.
The above figure shows the queue of characters forming the English
word "HELLO". Since, No deletion is performed in the queue till now,
therefore the value of front remains -1 . However, the value of rear
increases by one every time an insertion is performed in the queue. After
inserting an element into the queue shown in the above figure, the queue
will look something like following. The value of rear will become 5 while
the value of front remains same.

After deleting an element, the value of front will increase from -1 to 0.

however, the queue will look something like following.
Algorithm to insert any element in a queue
Check if the queue is already full by comparing rear to max - 1. if so, then
return an overflow error.

If the item is to be inserted as the first element in the list, in that case set
the value of front and rear to 0 and insert the element at the rear end.

Otherwise keep increasing the value of rear and insert each element one
by one having rear as the index.

Algorithm

o Step 1: IF REAR = MAX - 1

Write OVERFLOW
Go to step
[END OF IF]
o Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
o Step 3: Set QUEUE[REAR] = NUM
o Step 4: EXIT

Algorithm to delete an element from the queue

If, the value of front is -1 or value of front is greater than rear , write an
underflow message and exit.

Otherwise, keep increasing the value of front and return the item stored
at the front end of the queue at each time.

Algorithm

o Step 1: IF FRONT = -1 or FRONT > REAR

Write UNDERFLOW
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
o Step 2: EXIT

Drawback of array implementation

Although, the technique of creating a queue is easy, but there are some
drawbacks of using this technique to implement a queue.

o Memory wastage : The space of the array, which is used to store

queue elements, can never be reused to store the elements of that
queue because the elements can only be inserted at front end and
the value of front might be so high so that, all the space before that,
can never be filled.

The above figure shows how the memory space is wasted in the array
representation of queue. In the above figure, a queue of size 10 having 3
elements, is shown. The value of the front variable is 5, therefore, we can
not reinsert the values in the place of already deleted element before the
position of front. That much space of the array is wasted and can not be
used in the future (for this queue).

o Deciding the array size

On of the most common problem with array implementation is the size of

the array which requires to be declared in advance. Due to the fact that,
the queue can be extended at runtime depending upon the problem, the
extension in the array size is a time taking process and almost impossible
to be performed at runtime since a lot of reallocations take place. Due to
this reason, we can declare the array large enough so that we can store
queue elements as enough as possible but the main problem with this
declaration is that, most of the array slots (nearly half) can never be
reused. It will again lead to memory wastage.

Linked List implementation of Queue

Due to the drawbacks discussed in the previous section of this tutorial, the
array implementation can not be used for the large scale applications
where the queues are implemented. One of the alternative of array
implementation is linked list implementation of queue.

The storage requirement of linked representation of a queue with n

elements is o(n) while the time requirement for operations is o(1).

In a linked queue, each node of the queue consists of two parts i.e. data
part and the link part. Each element of the queue points to its immediate
next element in the memory.

In the linked queue, there are two pointers maintained in the memory i.e.
front pointer and rear pointer. The front pointer contains the address of
the starting element of the queue while the rear pointer contains the
address of the last element of the queue.

Insertion and deletions are performed at rear and front end respectively. If
front and rear both are NULL, it indicates that the queue is empty.

The linked representation of queue is shown in the following figure.

Operation on Linked Queue
There are two basic operations which can be implemented on the linked
queues. The operations are Insertion and Deletion.

Insert operation
The insert operation append the queue by adding an element to the end
of the queue. The new element will be the last element of the queue.

Firstly, allocate the memory for the new node ptr by using the following
statement.

1. Ptr = (struct node *) malloc (sizeof(struct node));

There can be the two scenario of inserting this new node ptr into the
linked queue.

In the first scenario, we insert element into an empty queue. In this case,
the condition front = NULL becomes true. Now, the new element will be
added as the only element of the queue and the next pointer of front and
rear pointer both, will point to NULL.

1. ptr -> data = item;

2. if(front == NULL)
3. {
4. front = ptr;
5. rear = ptr;
6. front -> next = NULL;
7. rear -> next = NULL;
8. }

In the second case, the queue contains more than one element. The
condition front = NULL becomes false. In this scenario, we need to update
the end pointer rear so that the next pointer of rear will point to the new
node ptr. Since, this is a linked queue, hence we also need to make the
rear pointer point to the newly added node ptr. We also need to make the
next pointer of rear point to NULL.

1. rear -> next = ptr;

2. rear = ptr;
3. rear->next = NULL;

In this way, the element is inserted into the queue. The algorithm and the
C implementation is given as follows.

Algorithm
o Step 1: Allocate the space for the new node PTR
o Step 2: SET PTR -> DATA = VAL
o Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
o Step 4: END

Deletion
Deletion operation removes the element that is first inserted among all
the queue elements. Firstly, we need to check either the list is empty or
not. The condition front == NULL becomes true if the list is empty, in this
case , we simply write underflow on the console and make exit.

Otherwise, we will delete the element that is pointed by the pointer front.
For this purpose, copy the node pointed by the front pointer into the
pointer ptr. Now, shift the front pointer, point to its next node and free the
node pointed by the node ptr. This is done by using the following
statements.

1. ptr = front;
2. front = front -> next;
3. free(ptr);
The algorithm and C function is given as follows.

Algorithm
o Step 1: IF FRONT = NULL
Write " Underflow "
Go to Step 5
[END OF IF]
o Step 2: SET PTR = FRONT
o Step 3: SET FRONT = FRONT -> NEXT
o Step 4: FREE PTR
o Step 5: END

Circular Queue
Why was the concept of the circular queue introduced?
There was one limitation in the array implementation of Queue. If the rear
reaches to the end position of the Queue then there might be possibility
that some vacant spaces are left in the beginning which cannot be
utilized. So, to overcome such limitations, the concept of the circular
queue was introduced.
As we can see in the above image, the rear is at the last position of the
Queue and front is pointing somewhere rather than the 0 th position. In the
above array, there are only two elements and other three positions are
empty. The rear is at the last position of the Queue; if we try to insert the
element then it will show that there are no empty spaces in the Queue.
There is one solution to avoid such wastage of memory space by shifting
both the elements at the left and adjust the front and rear end
accordingly. It is not a practically good approach because shifting all the
elements will consume lots of time. The efficient approach to avoid the
wastage of the memory is to use the circular queue data structure.

What is a Circular Queue?

A circular queue is similar to a linear queue as it is also based on the FIFO
(First In First Out) principle except that the last position is connected to
the first position in a circular queue that forms a circle. It is also known as
a Ring Buffer.
Operations on Circular Queue
The following are the operations that can be performed on a circular
queue:

o Front: It is used to get the front element from the Queue.

o Rear: It is used to get the rear element from the Queue.
o enQueue(value): This function is used to insert the new value in the
Queue. The new element is always inserted from the rear end.
o deQueue(): This function deletes an element from the Queue. The
deletion in a Queue always takes place from the front end.

Applications of Circular Queue

The circular Queue can be used in the following scenarios:

o Memory management: The circular queue provides memory

management. As we have already seen that in linear queue, the memory
is not managed very efficiently. But in case of a circular queue, the
memory is managed efficiently by placing the elements in a location which
is unused.
o CPU Scheduling: The operating system also uses the circular queue to
insert the processes and then execute them.
o Traffic system: In a computer-control traffic system, traffic light is one of
the best examples of the circular queue. Each light of traffic light gets ON
one by one after every jinterval of time. Like red light gets ON for one
minute then yellow light for one minute and then green light. After green
light, the red light gets ON.

Enqueue operation
The steps of enqueue operation are given below:

o First, we will check whether the Queue is full or not.

o Initially the front and rear are set to -1. When we insert the first element in
a Queue, front and rear both are set to 0.
o When we insert a new element, the rear gets incremented,
i.e., rear=rear+1.
Scenarios for inserting an element
There are two scenarios in which queue is not full:

o If rear != max - 1, then rear will be incremented to mod(maxsize) and

the new value will be inserted at the rear end of the queue.
o If front != 0 and rear = max - 1, it means that queue is not full, then
set the value of rear to 0 and insert the new element there.

There are two cases in which the element cannot be inserted:

o When front ==0 && rear = max-1, which means that front is at the first
position of the Queue and rear is at the last position of the Queue.
o front== rear + 1;

Algorithm to insert an element in a circular queue

Step 1: IF (REAR+1)%MAX = FRONT

Write " OVERFLOW "
Goto step 4
[End OF IF]

Step 2: IF FRONT = -1 and REAR = -1

SET FRONT = REAR = 0
ELSE IF REAR = MAX - 1 and FRONT ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]

Step 3: SET QUEUE[REAR] = VAL

Step 4: EXIT

Dequeue Operation
The steps of dequeue operation are given below:

o First, we check whether the Queue is empty or not. If the queue is empty,
we cannot perform the dequeue operation.
o When the element is deleted, the value of front gets decremented by 1.
o If there is only one element left which is to be deleted, then the front and
rear are reset to -1.
Algorithm to delete an element from the circular queue

Step 1: IF FRONT = -1
Write " UNDERFLOW "
Goto Step 4
[END of IF]

Step 2: SET VAL = QUEUE[FRONT]

Step 3: IF FRONT = REAR

SET FRONT = REAR = -1
ELSE
IF FRONT = MAX -1
SET FRONT = 0
ELSE
SET FRONT = FRONT + 1
[END of IF]
[END OF IF]

Step 4: EXIT

Let's understand the enqueue and dequeue operation through the

diagrammatic representation.
Implementation of circular queue using linked list
As we know that linked list is a linear data structure that stores two parts,
i.e., data part and the address part where address part contains the
address of the next node. Here, linked list is used to implement the
circular queue; therefore, the linked list follows the properties of the
Queue. When we are implementing the circular queue using linked list
then both the enqueue and dequeue operations take O(1) time.

o
Deletion at front
o Deletion at rear

We can also perform peek operations in the deque along with the
operations listed above. Through peek operation, we can get the deque's
front and rear elements of the deque. So, in addition to the above
operations, following operations are also supported in deque -

o Get the front item from the deque

o Get the rear item from the deque
o Check whether the deque is full or not
o Checks whether the deque is empty or not

Now, let's understand the operation performed on deque using an

example.

Insertion at the front end

In this operation, the element is inserted from the front end of the queue.
Before implementing the operation, we first have to check whether the
queue is full or not. If the queue is not full, then the element can be
inserted from the front end by using the below conditions -

o If the queue is empty, both rear and front are initialized with 0. Now,
both will point to the first element.
o Otherwise, check the position of the front if the front is less than 1
(front < 1), then reinitialize it by front = n - 1, i.e., the last index of
the array.

Insertion at the rear end

In this operation, the element is inserted from the rear end of the queue.
Before implementing the operation, we first have to check again whether
the queue is full or not. If the queue is not full, then the element can be
inserted from the rear end by using the below conditions -

o If the queue is empty, both rear and front are initialized with 0. Now,
both will point to the first element.
o Otherwise, increment the rear by 1. If the rear is at last index (or
size - 1), then instead of increasing it by 1, we have to make it equal
to 0.

Deletion at the front end

In this operation, the element is deleted from the front end of the queue.
Before implementing the operation, we first have to check whether the
queue is empty or not.

If the queue is empty, i.e., front = -1, it is the underflow condition, and we
cannot perform the deletion. If the queue is not full, then the element can
be inserted from the front end by using the below conditions -

If the deque has only one element, set rear = -1 and front = -1.

Else if front is at end (that means front = size - 1), set front = 0.

Else increment the front by 1, (i.e., front = front + 1).

Deletion at the rear end

In this operation, the element is deleted from the rear end of the queue.
Before implementing the operation, we first have to check whether the
queue is empty or not.

If the queue is empty, i.e., front = -1, it is the underflow condition, and we
cannot perform the deletion.

If the deque has only one element, set rear = -1 and front = -1.

If rear = 0 (rear is at front), then set rear = n - 1.

Else, decrement the rear by 1 (or, rear = rear -1).

Check empty

This operation is performed to check whether the deque is empty or not. If

front = -1, it means that the deque is empty.
Check full

This operation is performed to check whether the deque is full or not. If

front = rear + 1, or front = 0 and rear = n - 1 it means that the deque is
full.

The time complexity of all of the above operations of the deque is O(1),
i.e., constant.

Applications of deque
o Deque can be used as both stack and queue, as it supports both
operations.
o Deque can be used as a palindrome checker means that if we read
the string from both ends, the string would be the same.