UNIT – II CHAPTER

Queue 5
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.

Enqueue
(Insertion)

Dequeue Front Rear

(Deletion)

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.
128 Data Structures

Complexity

Data Time Complexity Space

Structure Compleity
Average Worst Worst
Access Search Insertion Deletion Access Search Insertion Deletion
Queue (n) (n) (1) (1) O(n) O(n) O(1) O(1) O(n)

IMPLEMENTATION OF QUEUE
There are two ways of implementing the Queue:
o Sequential allocation: The sequential allocation in a Queue can be
implemented using an array.
For more details, click on the below link:
[Link]
o Linked list allocation: The linked list allocation in a Queue can be
implemented using a linked list.
For more details, click on the below link:
[Link]

What are the use cases of Queue?

Here, we will see the real–world scenarios where we can use the Queue data
structure. The Queue data structure is mainly used where there is a shared
resource that has to serve the multiple requests but can serve a single request at
a time. In such cases, we need to use the Queue data structure for queuing up the
requests. The request that arrives first in the queue will be served first. The
following are the real–world scenarios in which the Queue concept is used:
o Suppose we have a printer shared between various machines in a
network, and any machine or computer in a network can send a print
request to the printer. But, the printer can serve a single request at a
time, i.e., a printer can print a single document at a time. When any
print request comes from the network, and if the printer is busy, the
printer’s program will put the print request in a queue.
o . If the requests are available in the Queue, the printer takes a request
from the front of the queue, and serves it.
Queues 129

o The processor in a computer is also used as a shared resource. There are

multiple requests that the processor must execute, but the processor can
serve a single request or execute a single process at a time. Therefore,
the processes are kept in a Queue for execution.

Types of Queue
There are four types of Queues:
o 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 linear Queue can be represented, as shown
in the below figure:

10 20 30

front rear
The above figure shows that the elements are inserted from the rear end,
and if we insert more elements in a Queue, then the rear value gets incremented
on every insertion. If we want to show the deletion, then it can be represented as:

20 30

front rear
In the above figure, we can observe that the front pointer points to the next
element, and the element which was previously pointed by the front pointer was
deleted.
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.
130 Data Structures

o 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 circular queue can be represented as:

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.
To know more about circular queue, click on the below link: https://
[Link]/circular–queue
o Priority Queue
A priority queue is another special type of Queue data structure in which
each element has some priority associated with it. Based on the priority of the
element, the elements are arranged in a priority queue. If the elements occur with
the same priority, then they are served according to the FIFO principle.
Queues 131

In priority Queue, the insertion takes place based on the arrival while the
deletion occurs based on the priority. The priority Queue can be shown as:
The above figure shows that the highest priority element comes first and the
elements of the same priority are arranged based on FIFO structure.
o Deque
Both the Linear Queue and Deque are different as the linear queue follows
the FIFO principle whereas, deque does not follow the FIFO principle. In Deque,
the insertion and deletion can occur from both ends.

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.

H E L L O
0 1 2 3 4 5

front rear
0 4
Queue

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.
132 Data Structures

H E L L O G
0 1 2 3 4 5

front rear
0 5
Queue after inserting an element

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

however, the queue will look something like following.

E L L O G
0 1 2 3 4 5

front rear
1 5

Queue after deleting an element

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.
20.4M
463
Exception Handling in Java – Javatpoint
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.
Queues 133

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

C Function
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. }
134 Data Structures

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

C Function
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.
Queues 135

18. }
19. return y;
20. }
21. }

Menu driven program to implement queue using array

1. #include<stdio.h>
2. #include<stdlib.h>
3. #define maxsize 5
4. void insert();
5. void delete();
6. void display();
7. int front = –1, rear = –1;
8. int queue[maxsize];
9. void main ()
10. {
11. int choice;
12. while(choice != 4)
13. {
14. printf(“\n*************************Main Menu*********
********************\n”);
15. printf(“\n================================
=================================\n”);
16. printf(“\[Link] an element\[Link] an element\n3.
Display the queue\[Link]\n”);
17. printf(“\nEnter your choice ?”);
18. scanf(“%d”,&choice);
19. switch(choice)
20. {
21. case 1:
22. insert();
23. break;
24. case 2:
25. delete();
136 Data Structures

26. break;
27. case 3:
28. display();
29. break;
30. case 4:
31. exit(0);
32. break;
33. default:
34. printf(“\nEnter valid choice??\n”);
35. }
36. }
37. }
38. void insert()
39. {
40. int item;
41. printf(“\nEnter the element\n”);
42. scanf(“\n%d”,&item);
43. if(rear == maxsize–1)
44. {
45. printf(“\nOVERFLOW\n”);
46. return;
47. }
48. if(front == –1 && rear == –1)
49. {
50. front = 0;
51. rear = 0;
52. }
53. else
54. {
55. rear = rear+1;
56. }
57. queue[rear] = item;
Queues 137

58. printf(“\nValue inserted ”);

59.
60. }
61. void delete()
62. {
63. int item;
64. if (front == –1 || front > rear)
65. {
66. printf(“\nUNDERFLOW\n”);
67. return;
68.
69. }
70. else
71. {
72. item = queue[front];
73. if(front == rear)
74. {
75. front = –1;
76. rear = –1 ;
77. }
78. else
79. {
80. front = front + 1;
81. }
82. printf(“\nvalue deleted ”);
83. }
84.
85.
86. }
87.
88. void display()
89. {
138 Data Structures

90. int i;
91. if(rear == –1)
92. {
93. printf(“\nEmpty queue\n”);
94. }
95. else
96. { printf(“\nprinting values .....\n”);
97. for(i=front;i<=rear;i++)
98. {
99. printf(“\n%d\n”,queue[i]);
100. }
101. }
102. }

Output:
*************Main Menu**************
==============================================
1. insert an element
2. Delete an element
3. Display the queue
4. Exit
Enter your choice ?1
Enter the element
123
Value inserted
*************Main Menu**************
==============================================
1. insert an element
2. Delete an element
3. Display the queue
4. Exit
Enter your choice ?1
Queues 139

Enter the element

90
Value inserted
*************Main Menu**************
===================================
1. insert an element
2. Delete an element
3. Display the queue
4. Exit
Enter your choice ?2
value deleted
*************Main Menu**************
==============================================
1. insert an element
2. Delete an element
3. Display the queue
4. Exit
Enter your choice ?3
printing values .....
90
*************Main Menu**************
==============================================
1. insert an element
2. Delete an element
3. Display the queue
4. Exit
Enter your choice ?4
*************Main Menu**************
================================================================================
Display the queue
4. Exit
Enter your choice ?4
140 Data Structures

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.

deleted deleted deleted deleted deleted 10 20 30

0 1 2 3 4 5 6 7 8 9

front rear
Limitation of array representation of queue

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.
Queues 141

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.
17.3M
386
OOPs Concepts in Java
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.

9 1 7 4

front rear

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.
142 Data Structures

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
Queues 143

C Function
1. void insert(struct node *ptr, int item; )

2. {

3.

4.

5. ptr = (struct node *) malloc (sizeof(struct node));

6. if(ptr == NULL)

7. {

8. printf(“\nOVERFLOW\n”);

9. return;

10. }

11. else

12. {

13. ptr –> data = item;

14. if(front == NULL)

15. {

16. front = ptr;

17. rear = ptr;

18. front –> next = NULL;

19. rear –> next = NULL;

20. }

21. else

22. {

23. rear –> next = ptr;

24. rear = ptr;

25. rear–>next = NULL;

26. }

27. }

28. }
144 Data Structures

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

C Function
1. void delete (struct node *ptr)
2. {
3. if(front == NULL)
4. {
5. printf(“\nUNDERFLOW\n”);
6. return;
7. }
8. else
Queues 145

9. {
10. ptr = front;
11. front = front –> next;
12. free(ptr);
13. }
14. }

Menu–Driven Program implementing all the operations on Linked

Queue
1. #include<stdio.h>
2. #include<stdlib.h>
3. struct node
4. {
5. int data;
6. struct node *next;
7. };
8. struct node *front;
9. struct node *rear;
10. void insert();
11. void delete();
12. void display();
13. void main ()
14. {
15. int choice;
16. while(choice != 4)
17. {
18. printf(“\n*************************Main Menu*******
**********************\n”);
19. printf(“\n==================================
===============================\n”);
20. printf(“\[Link] an element\[Link] an element
\[Link] the queue\[Link]\n”);
21. printf(“\nEnter your choice ?”);
146 Data Structures

22. scanf(“%d”,& choice);

23. switch(choice)
24. {
25. case 1:
26. insert();
27. break;
28. case 2:
29. delete();
30. break;
31. case 3:
32. display();
33. break;
34. case 4:
35. exit(0);
36. break;
37. default:
38. printf(“\nEnter valid choice??\n”);
39. }
40. }
41. }
42. void insert()
43. {
44. struct node *ptr;
45. int item;
46.
47. ptr = (struct node *) malloc (sizeof(struct node));
48. if(ptr == NULL)
49. {
50. printf(“\nOVERFLOW\n”);
51. return;
52. }
53. else
Queues 147

54. {
55. printf(“\nEnter value?\n”);
56. scanf(“%d”,&item);
57. ptr –> data = item;
58. if(front == NULL)
59. {
60. front = ptr;
61. rear = ptr;
62. front –> next = NULL;
63. rear –> next = NULL;
64. }
65. else
66. {
67. rear –> next = ptr;
68. rear = ptr;
69. rear–>next = NULL;
70. }
71. }
72. }
73. void delete ()
74. {
75. struct node *ptr;
76. if(front == NULL)
77. {
78. printf(“\nUNDERFLOW\n”);
79. return;
80. }
81. else
82. {
83. ptr = front;
84. front = front –> next;
85. free(ptr);
148 Data Structures

86. }
87. }
88. void display()
89. {
90. struct node *ptr;
91. ptr = front;
92. if(front == NULL)
93. {
94. printf(“\nEmpty queue\n”);
95. }
96. else
97. { printf(“\nprinting values .....\n”);
98. while(ptr != NULL)
99. {
100. printf(“\n%d\n”,ptr –> data);
101. ptr = ptr –> next;
102. }
103. }
104. }

Output:
***********Main Menu**********
==============================
1. insert an element
2. Delete an element
3. Display the queue
4. Exit
Enter your choice ?1
Enter value?
123
***********Main Menu**********
==============================
Queues 149

1. insert an element
2. Delete an element
3. Display the queue
4. Exit
Enter your choice ?1
Enter value?
90
***********Main Menu**********
==============================
1. insert an element
2. Delete an element
3. Display the queue
4. Exit
Enter your choice ?3
printing values .....
123
90
***********Main Menu**********
==============================
1. insert an element
2. Delete an element
3. Display the queue
4. Exit
Enter your choice ?2
***********Main Menu**********
==============================
1. insert an element
2. Delete an element
3. Display the queue
4. Exit
Enter your choice ?3
printing values .....
150 Data Structures

90
***********Main Menu**********
==============================
1. insert an element
2. Delete an element
3. Display the queue
4. Exit
Enter your choice ?4

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.

Front = 3 Rear = 4

1 2

0 1 2 3 4

Circular Queue Representation

4
2
1

1
3
2
Queues 151

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 0th 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:
15.3M
311
Java Try Catch
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.
152 Data Structures

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
Queues 153

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.
154 Data Structures

0 1 2 3 4
Front = –1
Rear = –1

10
0 1 2 3 4
Front = 0
Rear = 0

10 20 30

Front = 0 Rear = 0

10 20 30 40

0 1 2 3 4

Front = 0 Rear = 3

10 20 30 40 50

0 1 2 3 4

Front = 0 Rear = 4

30 40 50

0 1 2 3 4
dequeue

Front = 2 Rear = 4
Queues 155

60 30 40 50

0 1 2 3 4

Rear Front

60 70 30 40 50

0 1 2 3 4

Rear Front

Implementation of circular queue using Array

1. #include <stdio.h>
2.
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. }
156 Data Structures

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)
Queues 157

51. {
52. printf(“\n Queue is empty..”);
53. }
54. else
55. {
56. printf(“\nElements in a Queue are :”);
57. while(i<=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);
158 Data Structures

83. enqueue(x);
84. break;
85. case 2:
86. dequeue();
87. break;
88. case 3:
89. display();
90. }
91. }
92. return 0;
93. }

Output :
Press 1 : Insert an element
Press 2 : Delete an element
Press 3 : Display the element
Enter your choice
1
Enter the element which is to be inserted
10

Press 1 : Insert an element

Press 2 : Delete an element
Press 3 : Display the element
Enter you choice
1
Enter the element which is to be inserted
20

Press 1 : Insert an element

Press 2 : Delete an element
Press 3 : Display the element
Enter you choice
1
Queues 159

Enter the element which is to be inserted

30

Press 1 : Insert an element

Press 2 : Delete an element
Press 3 : Display the element
Enter you choice
3

Elements in a queue are : 10, 20, 30

Press 1 : Insert an element
Press 2 : Delete an element
Press 3 : Display the element
Enter you choice
2

The dequeued element is 10.

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.

1. #include <stdio.h>
2. // Declaration of struct type node
3. struct node
4. {
5. int data;
6. struct node *next;
7. };
8. struct node *front=-1;
9. struct node *rear=-1;
160 Data Structures

10. // function to insert the element in the Queue

11. void enqueue(int x)
12. {
13. struct node *newnode; // declaration of pointer of struct node type.
14. newnode=(struct node *)malloc(sizeof(struct node));
// allocating the memory to the newnode
15. newnode->data=x;
16. newnode->next=0;
17. if(rear==-1) // checking whether the Queue is empty or not.
18. {
19. front=rear=newnode;
20. rear->next=front;
21. }
22. else
23. {
24. rear->next=newnode;
25. rear=newnode;
26. rear->next=front;
27. }
28. }
29.
30. // function to delete the element from the queue
31. void dequeue()
32. {
33. struct node *temp; // declaration of pointer of node type
34. temp=front;
35. if((front==-1)&&(rear==-1))
// checking whether the queue is empty or not
36. {
37. printf(“\nQueue is empty”);
38. }
39. else if(front==rear) // checking whether the single
element is left in the queue
Queues 161

40. {
41. front=rear=-1;
42. free(temp);
43. }
44. else
45. {
46. front=front->next;
47. rear->next=front;
48. free(temp);
49. }
50. }
51.
52. // function to get the front of the queue
53. int peek()
54. {
55. if((front==-1) &&(rear==-1))
56. {
57. printf(“\nQueue is empty”);
58. }
59. else
60. {
61. printf(“\nThe front element is %d”, front->data);
62. }
63. }
64.
65. // function to display all the elements of the queue
66. void display()
67. {
68. struct node *temp;
69. temp=front;
70. printf(“\n The elements in a Queue are : ”);
71. if((front==-1) && (rear==-1))
72. {
162 Data Structures

73. printf(“Queue is empty”);

74. }
75.
76. else
77. {
78. while(temp->next!=front)
79. {
80. printf(“%d,”, temp->data);
81. temp=temp->next;
82. }
83. printf(“%d”, temp->data);
84. }
85. }
86.
87. void main()

88. {

89. enqueue(34);

90. enqueue(10);

91. enqueue(23);

92. display();

93. dequeue();

94. peek();

95. }

Output:

The elements in a Queue are : 34, 10, 23

The front element is 10

....Program finished with exit code 24

Press Enter to exit console.

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
Queues 163

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

20.4M
464
Exception Handling in Java - Javatpoint
A priority queue is an extension of a queue that contains the following
characteristics:
o Every element in a priority queue has some priority associated with it.
o An element with the higher priority will be deleted before the deletion of
the lesser priority.
o If two elements in a priority queue have the same priority, they will be
arranged using the FIFO principle.

Let’s understand the priority queue through an example.

We have a priority queue that contains the following values:
1, 3, 4, 8, 14, 22
All the values are arranged in ascending order. Now, we will observe how
the priority queue will look after performing the following operations:
o poll(): This function will remove the highest priority element from the
priority queue. In the above priority queue, the ‘1’ element has the
highest priority, so it will be removed from the priority queue.
o add(2): This function will insert ‘2’ element in a priority queue. As 2 is
164 Data Structures

the smallest element among all the numbers so it will obtain the highest
priority.
o poll(): It will remove ‘2’ element from the priority queue as it has the
highest priority queue.
o add(5): It will insert 5 element after 4 as 5 is larger than 4 and lesser
than 8, so it will obtain the third highest priority in a priority queue.

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.

element with the lowest priority

2 6 7 10 11

element with the highest priority

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

element with the lowest priority

10 9 8 7 6

element with the highest priority

Queues 165

REPRESENTATION OF PRIORITY QUEUE

Now, we will see how to represent the priority queue through a one-way list.
We will create the priority queue by using the list given below in
which INFO list contains the data elements, PRN list contains the priority
numbers of each data element available in the INFO list, and LINK basically
contains the address of the next node.

INFO PNR LINK

0 200 2 4
1 400 4 2
2 500 4 6
3 300 1 0
4 100 2 5
5 600 3 1
6 700 4

Let’s create the priority queue step by step.

In the case of priority queue, lower priority number is considered the higher
priority, i.e., lower priority number = higher priority.
Step 1: In the list, lower priority number is 1, whose data value is 333, so
it will be inserted in the list as shown in the below diagram:
Step 2: After inserting 333, priority number 2 is having a higher priority,
and data values associated with this priority are 222 and 111. So,
this data will be inserted based on the FIFO principle; therefore
222 will be added first and then 111.
Step 3: After inserting the elements of priority 2, the next higher priority
number is 4 and data elements associated with 4 priority numbers
are 444, 555, 777. In this case, elements would be inserted based
on the FIFO principle; therefore, 444 will be added first, then 555,
and then 777.
Step 4: After inserting the elements of priority 4, the next higher priority
number is 5, and the value associated with priority 5 is 666, so it
will be inserted at the end of the queue.
166 Data Structures

300 1 200 2 100 2 400 2

Start

500 4 700 4 600 5

IMPLEMENTATION OF PRIORITY QUEUE

The priority queue can be implemented in four ways that include arrays,
linked list, heap data structure and binary search tree. The heap data structure is
the most efficient way of implementing the priority queue, so we will implement
the priority queue using a heap data structure in this topic. Now, first we
understand the reason why heap is the most efficient way among all the other
data structures.
Analysis of complexities using different implementations

Implementation add Remove peek

Linked list O(1) O(n) O(n)

Binary heap O(logn) O(logn) O(1)

Binary search tree O(logn) O(logn) O(1)

What is Heap?
A heap is a tree-based data structure that forms a complete binary tree, and
satisfies the heap property. If A is a parent node of B, then A is ordered with
respect to the node B for all nodes A and B in a heap. It means that the value of
the parent node could be more than or equal to the value of the child node, or the
value of the parent node could be less than or equal to the value of the child node.
Therefore, we can say that there are two types of heaps:
Max heap: The max heap is a heap in which the value of the parent node is
greater than the value of the child nodes.
Queues 167

Max heap

45

30 40

20 10 35 15

o Min heap: The min heap is a heap in which the value of the parent node
is less than the value of the child nodes.

Min heap

6 7

8 9 14 20

Both the heaps are the binary heap, as each has exactly two child nodes.

Priority Queue Operations

The common operations that we can perform on a priority queue are
insertion, deletion and peek. Let’s see how we can maintain the heap data
structure.

Inserting the element in a priority queue (max heap)

If we insert an element in a priority queue, it will move to the empty slot by
looking from top to bottom and left to right.
If the element is not in a correct place then it is compared with the parent
168 Data Structures

node; if it is found out of order, elements are swapped. This process continues
until the element is placed in a correct position.

20

1 2
17 16
New Element
3 4 5 6
15 14 13 18

Heapify
0
20

1 2
17 18

3 4 5 6
15 14 13 16

Removing the minimum element from the priority queue

As we know that in a max heap, the maximum element is the root node.
When we remove the root node, it creates an empty slot. The last inserted
element will be added in this empty slot. Then, this element is compared with the
child nodes, i.e., left-child and right child, and swap with the smaller of the two.
It keeps moving down the tree until the heap property is restored.

Applications of Priority queue

The following are the applications of the priority queue:
o It is used in the Dijkstra’s shortest path algorithm.
o It is used in prim’s algorithm
o It is used in data compression techniques like Huffman code.
Queues 169

o It is used in heap sort.

o It is also used in operating system like priority scheduling, load
balancing and interrupt handling.

Program to create the priority queue using the binary max heap.
1. #include <stdio.h>
2. #include <stdio.h>
3. int heap[40];
4. int size=-1;
5.
6. // retrieving the parent node of the child node
7. int parent(int i)
8. {
9.
10. return (i - 1) / 2;
11. }
12.
13. // retrieving the left child of the parent node.
14. int left_child(int i)
15. {
16. return i+1;
17. }
18. // retrieving the right child of the parent
19. int right_child(int i)
20. {
21. return i+2;
22. }
23. // Returning the element having the highest priority
24. int get_Max()
25. {
26. return heap[0];
27. }
170 Data Structures

28. //Returning the element having the minimum priority

29. int get_Min()
30. {
31. return heap[size];
32. }
33. //
function to move the node up the tree in order to restore the heap property.
34. void moveUp(int i)
35. {
36. while (i > 0)
37. {
38. // swapping parent node with a child node
39. if(heap[parent(i)] < heap[i]) {
40.
41. int temp;
42. temp=heap[parent(i)];
43. heap[parent(i)]=heap[i];
44. heap[i]=temp;
45.
46.
47. }
48. // updating the value of i to i/2
49. i=i/2;
50. }
51. }
52.
53. // function to move the node down the tree in order to
restore the heap property.
54. void moveDown(int k)
55. {
56. int index = k;
57.
Queues 171

58. // getting the location of the Left Child

59. int left = left_child(k);
60.
61. if (left <= size && heap[left] > heap[index]) {
62. index = left;
63. }
64.
65. // getting the location of the Right Child
66. int right = right_child(k);
67.
68. if (right <= size && heap[right] > heap[index]) {
69. index = right;
70. }
71.
72. // If k is not equal to index
73. if (k != index) {
74. int temp;
75. temp=heap[index];
76. heap[index]=heap[k];
77. heap[k]=temp;
78. moveDown(index);
79. }
80. }
81.
82. // Removing the element of maximum priority
83. void removeMax()
84. {
85. int r= heap[0];
86. heap[0]=heap[size];
87. size=size-1;
88. moveDown(0);
89. }
172 Data Structures

90. //inserting the element in a priority queue

91. void insert(int p)
92. {
93. size = size + 1;
94. heap[size] = p;
95.
96. // move Up to maintain heap property
97. moveUp(size);
98. }
99.
100. //Removing the element from the priority queue at a given index i.
101. void delete(int i)
102. {
103. heap[i] = heap[0] + 1;
104.
105. // move the node stored at ith location is shifted to the root node
106. moveUp(i);
107.
108. // Removing the node having maximum priority
109. removeMax();
110. }
111. int main()
112. {
113. // Inserting the elements in a priority queue
114.
115. insert(20);
116. insert(19);
117. insert(21);
118. insert(18);
119. insert(12);
120. insert(17);
121. insert(15);
Queues 173

122. insert(16);
123. insert(14);
124. int i=0;
125.
126. printf(“Elements in a priority queue are : ”);

127. for(int i=0;i<=size;i++)

128. {

129. printf(“%d ”,heap[i]);

130. }

131. delete(2); // deleting the element whose index is 2.

132. printf(“\nElements in a priority queue

after deleting the element are : ”);

133. for(int i=0;i<=size;i++)

134. {

135. printf(“%d ”,heap[i]);

136. }

137. int max=get_Max();

138. printf(“\nThe element which is having the highest

priority is %d: ”,max);

139.

140.

141. int min=get_Min();

142. printf(“\nThe element which is having the minimum

priority is : %d”,min);

143. return 0;
144. }

In the above program, we have created the following functions:

o int parent(int i): This function returns the index of the parent node of a
child node, i.e., i.
o int left_child(int i): This function returns the index of the left child of a
given index, i.e., i.
174 Data Structures

o int right_child(int i): This function returns the index of the right child
of a given index, i.e., i.
o void moveUp(int i): This function will keep moving the node up the
tree until the heap property is restored.
o void moveDown(int i): This function will keep moving the node down
the tree until the heap property is restored.
o void removeMax(): This function removes the element which is having
the highest priority.
o void insert(int p): It inserts the element in a priority queue which is
passed as an argument in a function.
o void delete(int i): It deletes the element from a priority queue at a
given index.
o int get_Max(): It returns the element which is having the highest
priority, and we know that in max heap, the root node contains the
element which has the largest value, and highest priority.
o int get_Min(): It returns the element which is having the minimum
priority, and we know that in max heap, the last node contains the
element which has the smallest value, and lowest priority.
Output :
Elements in a priority queue are : 21 19 20 18 12 17 15 16 14
Elements in a priority queue after deleting the element are :
21 19 18 17 12 16 15 14
....Program finished with exit code 0
Press Enter to exit console.

QUEUE REPRESENTATION
As we now understand that in queue, we access both ends for different
reasons. The following diagram given below tries to explain queue representation
as data structure –
As in stacks, a queue can also be implemented using Arrays, Linked–lists,
Pointers and Structures. For the sake of simplicity, we shall implement queues
using one–dimensional array.
Queues 175

BASIC OPERATIONS
Queue operations may involve initializing or defining the queue, utilizing it,
and then completely erasing it from the memory. Here we shall try to understand
the basic operations associated with queues –
 enqueue() – add (store) an item to the queue.
 dequeue() – remove (access) an item from the queue.
Few more functions are required to make the above–mentioned queue
operation efficient. These are –
 peek() – Gets the element at the front of the queue without removing it.
 isfull() – Checks if the queue is full.
 isempty() – Checks if the queue is empty.
In queue, we always dequeue (or access) data, pointed by front pointer and
while enqueing (or storing) data in the queue we take help of rear pointer.
Let’s first learn about supportive functions of a queue –

peek()
This function helps to see the data at the front of the queue. The algorithm
of peek() function is as follows –

Algorithm
begin procedure peek
return queue[front]
end procedure
Implementation of peek() function in C programming language –

Example
int peek() {
return queue[front];
}
isfull()

As we are using single dimension array to implement queue, we just check

for the rear pointer to reach at MAXSIZE to determine that the queue is full. In
case we maintain the queue in a circular linked–list, the algorithm will differ.
Algorithm of isfull() function –
176 Data Structures

Algorithm
begin procedure isfull

if rear equals to MAXSIZE

return true

else

return false

endif

end procedure

Implementation of isfull() function in C programming language –

Example
bool isfull() {
if(rear == MAXSIZE – 1)

return true;

else
return false;
}
isempty()

Algorithm of isempty() function –

Algorithm
begin procedure isempty
if front is less than MIN OR front is greater than rear
return true
else

return false
endif

end procedure

If the value of front is less than MIN or 0, it tells that the queue is not yet
initialized, hence empty.
Here’s the C programming code –
Queues 177

Example
bool isempty() {
if(front < 0 || front > rear)
return true;
else
return false;
}

ENQUEUE OPERATION
Queues maintain two data pointers, front and rear. Therefore, its
operations are comparatively difficult to implement than that of stacks.
The following steps should be taken to enqueue (insert) data into a queue –
 Step 1 – Check if the queue is full.
 Step 2 – If the queue is full, produce overflow error and exit.
 Step 3 – If the queue is not full, increment rear pointer to point the
next empty space.
 Step 4 – Add data element to the queue location, where the rear is
pointing.
 Step 5 – return success
Sometimes, we also check to see if a queue is initialized or not, to handle
any unforeseen situations.

Algorithm for enqueue operation

procedure enqueue(data)
if queue is full
return overflow
endif
rear ? rear + 1
queue[rear] ? data
return true
end procedure

Implementation of enqueue() in C programming language –

178 Data Structures

Example
int enqueue(int data)
if(isfull())
return 0;

rear = rear + 1;
queue[rear] = data;

return 1;
end procedure

Dequeue Operation
Accessing data from the queue is a process of two tasks – access the data
where front is pointing and remove the data after access. The following steps are
taken to perform dequeue operation –
 Step 1 – Check if the queue is empty.
 Step 2 – If the queue is empty, produce underflow error and exit.
 Step 3 – If the queue is not empty, access the data where front is
pointing.
 Step 4 – Increment front pointer to point to the next available data
element.
 Step 5 – Return success.

Algorithm for dequeue operation

procedure dequeue

if queue is empty
return underflow
end if

data = queue[front]
front ? front + 1
return true

end procedure
Queues 179

Implementation of dequeue() in C programming language –

Example
int dequeue() {
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}

Tower of Hanoi, is a mathematical puzzle which consists of three towers

(pegs) and more than one rings is as depicted –
These rings are of different sizes and stacked upon in an ascending order,
i.e. the smaller one sits over the larger one. There are other variations of the
puzzle where the number of disks increase, but the tower count remains the
same.

Rules
The mission is to move all the disks to some another tower without violating
the sequence of arrangement. A few rules to be followed for Tower of Hanoi are –
 Only one disk can be moved among the towers at any given time.
 Only the “top” disk can be removed.
 No large disk can sit over a small disk.
Following is an animated representation of solving a Tower of Hanoi puzzle
with three disks.
Tower of Hanoi puzzle with n disks can be solved in minimum 2n–1 steps.
This presentation shows that a puzzle with 3 disks has taken 23 – 1 = 7 steps.

Algorithm
To write an algorithm for Tower of Hanoi, first we need to learn how to
solve this problem with lesser amount of disks, say  1 or 2. We mark three
towers with name, source, destination and aux (only to help moving the disks). If
we have only one disk, then it can easily be moved from source to destination peg.
If we have 2 disks –
180 Data Structures

 First, we move the smaller (top) disk to aux peg.

 Then, we move the larger (bottom) disk to destination peg.
 And finally, we move the smaller disk from aux to destination peg.
So now, we are in a position to design an algorithm for Tower of Hanoi with
more than two disks. We divide the stack of disks in two parts. The largest disk
(nth disk) is in one part and all other (n–1) disks are in the second part.
Our ultimate aim is to move disk n from source to destination and then put
all other (n1) disks onto it. We can imagine to apply the same in a recursive way
for all given set of disks.
The steps to follow are –
Step 1 – Move n–1 disks from source to aux
Step 2 – Move nth disk from source to dest
Step 3 – Move n–1 disks from aux to dest
A recursive algorithm for Tower of Hanoi can be driven as follows –
START
Procedure Hanoi(disk, source, dest, aux)
IF disk == 1, THEN
move disk from source to dest
ELSE
Hanoi(disk – 1, source, aux, dest) // Step 1
move disk from source to dest // Step 2
Hanoi(disk – 1, aux, dest, source) // Step 3
END IF
END Procedure
STOP

DATA STRUCTURE – RECURSION BASICS

Advertisements
Previous Page
Next Page
Some computer programming languages allow a module or function to call
Queues 181

itself. This technique is known as recursion. In recursion, a function  either calls

itself directly or calls a function  that in turn calls the original function . The
function  is called recursive function.
Example – a function calling itself.
int function(int value) {
if(value < 1)
return;
function(value – 1);
printf(“%d “,value);
}

Example – a function that calls another function which in turn calls it again.
int function1(int value1) {
if(value1 < 1)
return;
function2(value1 – 1);
printf(“%d “,value1);
}
int function2(int value2) {
function1(value2);
}

PROPERTIES
A recursive function can go infinite like a loop. To avoid infinite running of
recursive function, there are two properties that a recursive function must have –
 Base criteria – There must be at least one base criteria or condition,
such that, when this condition is met the function stops calling itself
recursively.
 Progressive approach – The recursive calls should progress in such a
way that each time a recursive call is made it comes closer to the base
criteria.

IMPLEMENTATION
Many programming languages implement recursion by means of stacks.
182 Data Structures

Generally, whenever a function (caller) calls another function (callee) or itself as

callee, the caller function transfers execution control to the callee. This transfer
process may also involve some data to be passed from the caller to the callee.
This implies, the caller function has to suspend its execution temporarily
and resume later when the execution control returns from the callee function.
Here, the caller function needs to start exactly from the point of execution where
it puts itself on hold. It also needs the exact same data values it was working on.
For this purpose, an activation record (or stack frame) is created for the caller
function.
This activation record keeps the information about local variables, formal
parameters, return address and all information passed to the caller function.

Analysis of Recursion
One may argue why to use recursion, as the same task can be done with
iteration. The first reason is, recursion makes a program more readable and
because of latest enhanced CPU systems, recursion is more efficient than
iterations.

Time Complexity
In case of iterations, we take number of iterations to count the time
complexity. Likewise, in case of recursion, assuming everything is constant, we
try to figure out the number of times a recursive call is being made. A call made
to a function is O(1), hence the (n) number of times a recursive call is made
makes the recursive function O(n).

Space Complexity
Space complexity is counted as what amount of extra space is required for a
module to execute. In case of iterations, the compiler hardly requires any extra
space. The compiler keeps updating the values of variables used in the iterations.
But in case of recursion, the system needs to store activation record each time a
recursive call is made. Hence, it is considered that space complexity of recursive
function may go higher than that of a function with iteration.

________