Unit – 05- Queue

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.
6. Job scheduling tasks of CPU.
7. Printer’s Buffer to store printing commands initiated by a user.
8. Input commands sent to CPU by devices like Keyboard and Mouse.
9. Document downloading from internet.
10. User Requests for call center services.
11. Order Queue for Online Food Delivery Chains.
 12. Online Cab Booking applications.

Basic Operations on Queue:

Some of the basic operations for Queue in Data Structure are:

( Queue as Abstract Data Type)

• enqueue() – Insertion of elements to the queue.
• dequeue() – Removal of elements from the queue.
• peek() or front()- Acquires the data element available at the front node of the queue without
deleting it.
• rear() – This operation returns the element at the rear end without removing it.
• isFull() – Validates if the queue is full.
• isEmpty() – Checks if the queue is empty.
• size(): This operation returns the size of the queue i.e. the total number of elements it contains.

Queue Data Structure

Operation 1: enqueue()
Inserts an element at the end of the queue i.e. at the rear end.

The following steps should be taken to enqueue (insert) data into a queue:

n success.
Memory Representation 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 rear 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.

Using the Non-Contiguous Memory like a Linked List

In this representation the queue is implemented using the dynamic data structure Linked List. Using
linked list for creating a queue makes it flexible in terms of size and storage. You don’t have to
define the maximum number of elements in the queue.
Pointers (links) to store addresses of nodes for defining a queue are.
• FRONT- address of the first element of the Linked list storing the Queue.
• REAR- address of the last element of the Linked list storing the Queue.

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 to insert(Enqueue) an element in the queue

• Step 1:
IF REAR = = MAX - 1
Write OVERFLOW
Go to step 4
[END OF IF]
• Step 2:
IF FRONT = = -1 and REAR = = -1
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]

• Step 3:
Set QUEUE[REAR] = NUM
• Step 4: EXIT
C Function To perform insert ( Enqueue ) Operation on the Queue

1. void insert (int queue[], int max, int front, int rear, int item)
2. {
3. if (rear + 1 == max)
4. {
5. printf("overflow");
6. }
7. else
8. {
9. if(front == -1 && rear == -1)
10. {
11. front = 0;
12. rear = 0;
13. }
14. else
15. {
16. rear = rear + 1;
17. }
18. queue[rear]=item;
19. }
20. }

Algorithm to delete ( Dequeue ) an element from the queue

• Step 1:
IF FRONT = = -1 or FRONT > REAR
Write UNDERFLOW
ELSE
SET VAL = QUEUE[ FRONT ]
SET FRONT = FRONT + 1
[END OF IF]
• Step 2:
 EXIT

C Function To perform Delete ( Dequeue ) Operation on the Queue

1. int delete (int queue[], int max, int front, int rear)
2. {
3. int y;
4. if (front == -1 || front > rear)
5.
6. {
7. printf("underflow");
8. }
9. else
10. {
11. y = queue[front];
12. if(front == rear)
13. {
14. front = rear = -1;
15. else
16. front = front + 1;
17.
18. }
19. return y;
20. }
21. }

Types of Queue : -
1. Linear Queue
2. Circular Queue
3. Priority Queue
4. Double Ended Queue
1. Linear Queue-
..................................Explained in previous topic
2. Circular Queue : -
A circular queue is the extended version of a regular queue where the last element is connected to the
first element. Thus forming a circle-like structure.

Limitations of Linear Queue -

There was one limitation in the array implementation of Linear 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.
Here, indexes 0 and 1 can only be used after resetting the queue (deletion of all elements). This
reduces the actual size of the queue.
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:
• Front: It is used to get the front element from the Queue.
• Rear: It is used to get the rear element from the Queue.
• enQueue(value): This function is used to insert the new value in the Queue. The new element is
always inserted from the rear end.
• 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:
• 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.
• CPU Scheduling: The operating system also uses the circular queue to insert the processes and then
execute them.
• 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:
• First, we will check whether the Queue is full or not.
• 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.
 • 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:

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

• 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:

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

• 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:
• First, we check whether the Queue is empty or not. If the queue is empty, we cannot
perform the dequeue operation.
• When the element is deleted, the value of front gets decremented by 1.
• 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 Array
1. #include <stdio.h>
3. # define max 6
4. int queue[max]; // array declaration
5. int front=-1;
6. int rear=-1;
7. // function to insert an element in a circular queue
8. void enqueue(int element)
9. {
10. if(front==-1 && rear==-1) // condition to check queue is empty
11. {
12. front=0;
13. rear=0;
14. queue[rear]=element;
15. }
16. else if((rear+1)%max==front) // condition to check queue is full
17. {
18. printf("Queue is overflow..");
19. }
20. else
21. {
22. rear=(rear+1)%max; // rear is incremented
23. queue[rear]=element; // assigning a value to the queue at the rear position.
24. }
25. }
26.
27. // function to delete the element from the queue
28. int dequeue()
29. {
30. if((front==-1) && (rear==-1)) // condition to check queue is empty
31. {
32. printf("\nQueue is underflow..");
33. }
34. else if(front==rear)
35. {
36. printf("\nThe dequeued element is %d", queue[front]);
37. front=-1;
38. rear=-1;
39. }
40. else
41. {
42. printf("\nThe dequeued element is %d", queue[front]);
43. front=(front+1)%max;
44. }
45. }
46. // function to display the elements of a queue
47. void display()
48. {
49. int i=front;
50. if(front==-1 && rear==-1)
51. {
52. printf("\n Queue is empty..");
53. }
54. else
55. {
56. printf("\nElements in a Queue are :");
57. while(front!=rear)
58. {
59. printf("%d,", queue[i]);
60. i=(i+1)%max;
61. }
62. }
63. }
64. int main()
65. {
66. int choice=1,x; // variables declaration
67.
68. while(choice<4 && choice!=0) // while loop
69. {
70. printf("\n Press 1: Insert an element");
71. printf("\nPress 2: Delete an element");
72. printf("\nPress 3: Display the element");
73. printf("\nEnter your choice");
74. scanf("%d", &choice);
75.
76. switch(choice)
77. {
78.
79. case 1:
80.
81. printf("Enter the element which is to be inserted");
82. scanf("%d", &x);
83. enqueue(x);
84. break;
85. case 2:
86. dequeue();
87. break;
88. case 3:
89. display();
90.
91. }}
92. return 0;
93. }
Type of Queue -

3. Double-Ended Queue ( Deque ):-

What is a Deque (or double-ended queue)

The deque stands for Double Ended Queue. Deque is a linear data structure where the insertion and
deletion operations are performed from both ends. We can say that deque is a generalized version of
the queue.
Though the insertion and deletion in a deque can be performed on both ends, it does not follow the
FIFO rule. The representation of a deque is given as follows -

Types of deque
There are two types of deque -
• Input restricted queue
• Output restricted queue
Input restricted Queue
In input restricted queue, insertion operation can be performed at only one end, while deletion can be
performed from both ends.

Output restricted Queue

In output restricted queue, deletion operation can be performed at only one end, while insertion can be
performed from both ends.
Operations performed on deque
There are the following operations that can be applied on a deque -
• Insertion at front
• Insertion at rear
• Deletion at front
• 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 -
• Get the front item from the deque
• Get the rear item from the deque
• Check whether the deque is full or not
• Checks whether the deque is empty or not
Now, let's understand the operation performed on deque using an example.

Below is the circular array implementation of deque. In a circular array, if the array is full, we start
from the beginning.

But in a linear array implementation, if the array is full, no more elements can be inserted. In each of
the operations below, if the array is full, "overflow message" is thrown.

Before performing the following operations, these steps are followed.

1. Take an array (deque) of size n.

2. Set two pointers at the first position and set front = -1 and rear = 0.
Operations on a DEQueue

Below is the circular array implementation of DEQueue. In a circular array, if the array is full, we
start from the beginning.
But in a linear array implementation, if the array is full, no more elements can be inserted. In each
of the operations below, if the array is full, "overflow message" is thrown.

Before performing the following operations, these steps are followed.

1. Take an array (deque) of size n .

2. Set two pointers front = -1 and rear = 0 .

1. Insert at the Front

This operation adds an element at the front.

1. Check if the deque is full.

2. If the deque is full (i.e. (front == 0 && rear == n - 1) || (front == rear + 1) ), insertion
operation cannot be performed (overflow condition).
3. If the deque is empty, reinitialize front = 0 . And, add the new value into array[front] .

4. If front = 0 , reinitialize front = n-1 (last index).

5. Else, decrease front by 1.

6. Add the new key 5 into array[front] .

2. Insert at the Rear

This operation adds an element to the rear.

1. Check if the deque is full.

2. If the deque is full, insertion operation cannot be performed (overflow condition).

3. If the deque is empty, reinitialize rear = 0 . And, add the new key into array[rear] .

4. If rear = n - 1 , reinitialize real = 0 (first index).

5. Else, increase rear by 1.

6. Add the new key 5 into array[rear] .

3. Delete from the Front

The operation deletes an element from the front .

1. Check if the deque is empty.

2. If the deque is empty (i.e. front = -1 ), deletion cannot be performed (underflow condition).

3. If the deque has only one element (i.e. front = rear ), set front = -1 and rear = -1 .

4. Else if front is at the last index (i.e. front = n - 1 ), set front = 0 .

5. Else, front = front + 1 .

4. Delete from the Rear

This operation deletes an element from the rear.

1. Check if the deque is empty.

2. If the deque is empty (i.e. front = -1 ), deletion cannot be performed (underflow condition).

3. If the deque has only one element (i.e. front = rear ), set front = -1 and rear = -1 , else follow the
steps below.
4. If rear is at the first index (i.e. rear = 0 ), reinitialize rear = n - 1 .

5. Else, rear = rear - 1 .

5. Check Empty

This operation checks if the deque is empty. If front = -1 , the deque is empty.
6. Check Full

This operation checks if the deque is full. If front = 0 and rear = n - 1 OR front == rear + 1 , the
deque is full.

Applications of DEQueue Data Structure

1. In undo operations on software.
2. To store history in browsers.

Types Of Queue : -

4. Priority Queue : -

What is a priority queue?

A priority queue is an abstract data type that behaves similarly to the normal queue except that each
element has some priority, i.e., the element with the highest priority would come first in a priority
queue. The priority of the elements in a priority queue will determine the order in which elements are
removed from the priority queue.
The priority queue supports only comparable elements, which means that the elements are either
arranged in an ascending or descending order.
For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in a priority queue with an
ordering imposed on the values is from least to the greatest. Therefore, the 1 number would be having
the highest priority while 22 will be having the lowest priority.

Characteristics of a Priority queue

A priority queue is an extension of a queue that contains the following characteristics:

• Every element in a priority queue has some priority associated with it.
 • An element with the higher priority will be deleted before the deletion of the lesser priority.

• If two elements in a priority queue have the same priority, they will be arranged using the
FIFO principle.

Types of Priority Queue

There are two types of priority queue:

• Ascending order priority queue: In ascending order priority queue, a lower priority number
is given as a higher priority in a priority. For example, we take the numbers from 1 to 5 arranged
in an ascending order like 1,2,3,4,5; therefore, the smallest number, i.e., 1 is given as the highest
priority in a priority queue.

• Descending order priority queue: In descending order priority queue, a higher priority
number is given as a higher priority in a priority. For example, we take the numbers from 1 to 5
arranged in descending order like 5, 4, 3, 2, 1; therefore, the largest number, i.e., 5 is given as the
 highest priority in a priority queue.

Basic Operations
• insert / enqueue − add an item to the rear of the queue.
• remove / dequeue − remove an item from the front of the queue.

Priority Queue Representation

We're going to implement Queue using array in this article. There is few more operations supported
by queue which are following.

• Peek − get the element at front of the queue.

• isFull − check if queue is full.

• isEmpty − check if queue is empty.

Insert / Enqueue Operation

Whenever an element is inserted into queue, priority queue inserts the item according to its order.
Here we're assuming that data with high value has low priority.

Remove / Dequeue Operation

Whenever an element is to be removed from queue, queue get the element using item count. Once
element is removed. Item count is reduced by one.
Applications of Priority Queue:
• CPU Scheduling
• Graph algorithms like Dijkstra’s shortest path algorithm , Prim’s Minimum Spanning Tree , etc.
• Stack Implementation
• All queue applications where priority is involved.
• Data compression in Huffman code
• Event-driven simulation such as customers waiting in a queue.
• Finding Kth largest/smallest element.
Advantages of Priority Queue:
• It helps to access the elements in a faster way. This is because elements in a priority queue are
ordered by priority, one can easily retrieve the highest priority element without having to search
through the entire queue.
• The ordering of elements in a Priority Queue is done dynamically. Elements in a priority queue
can have their priority values updated, which allows the queue to dynamically reorder itself as
priorities change.
• Efficient algorithms can be implemented. Priority queues are used in many algorithms to
improve their efficiency, such as Dijkstra’s algorithm for finding the shortest path in a graph and
the A* search algorithm for pathfinding.
• Included in real-time systems. This is because priority queues allow you to quickly retrieve the
highest priority element, they are often used in real-time systems where time is of the essence.
Disadvantages of Priority Queue:
• High complexity. Priority queues are more complex than simple data structures like arrays and
linked lists, and may be more difficult to implement and maintain.
• High consumption of memory. Storing the priority value for each element in a priority queue
can take up additional memory, which may be a concern in systems with limited resources.
• It is not always the most efficient data structure. In some cases, other data structures like heaps
or binary search trees may be more efficient for certain operations, such as finding the minimum
or maximum element in the queue.
• At times it is less predictable:. This is because the order of elements in a priority queue is
determined by their priority values, the order in which elements are retrieved may be less
predictable than with other data structures like stacks or queues, which follow a first-in, first-out
(FIFO) or last-in, first-out (LIFO) order.

*** END of Unit – 05 – Queue ***