1
This unit covers
Unit 3: Queue Introduction, Queue as an ADT,
Primitive operations in Queue,
Linear and Circular Queue and their applications,
Enqueue and Dequeue, Priority Queue.
2
We will focus on this questions
• Define Queue. Explain Queue as an Abstract Data
Type.
• Describe the primitive operations in Queue.
• Classify the Queue.
• Implement the Linear Queue.
• Implement the Circular Queue.
• List out applications of different types of Queue.
• Explain the Priority Queue with its operations and
Applications.
3
Unit III
Queue
A queue is a linear non-primitive data structure in which the
information are organized in FIFO (First In First Out) sequence.
Since the first element inserted into a queue is the first element
to be removed, a queue is also called a FIFO (first-in, first-out)
list.
In queue, the new elements are added to the queue from one
end, called REAR end and the elements are removed from other
end, called FRONT end.
Queue can also be implemented in two ways
1) Using Arrays (static implementation)
2) Using Pointers (dynamic implementation)
A line at a bank or at a bus stop or a waiting list of students are real
life examples of a queue
4
Operations on Queue
The basic operations that can be performed on queue are
1) To insert an element in a queue.
2) To delete an element from the queue.
Inserting an element in a queue
Consider the following examples
R= -1 and F= -1
0 1 2 3 4 5
FR
Fig (a) Empty queue
5
Inserting an element in a queue Contd..
R=0 and F=0
20
0 1 2 3 4 5
FR
Fig (b): Queue with one element
R=1 and F=0
20 30
0 1 2 3 4 5
F R
Fig (c): Queue with two element
6
Inserting an element in a queue Contd..
R=2 and F=0
20 30 40
1 2 3 4 5
F 0 R
Fig(d): Queue with three elements
From above Figures, it is clear that
1) Whenever we insert an element in the queue, the Value of
Rear (R) is incremented by one.
2) During the first insertion of first element in the queue, the
value of front is incremented by one. Afterward the value of
front is not changed during the entire addition operation.
7
Delete an element from the queue
R=2 and F=0
20 30 40
1 2 3 4 5
F 0 R
Fig: Queue with three elements
R=2 and F=1
30 40
0 1
F R 2 3 4 5
Fig: One element(20) is deleted from queue
8
Delete an element from the queue
R=2 and F=2
40
0 1 2 3 4 5
F R
Fig: Two elements (20& 30) are deleted from queue
From above figure, it is clear that
1) Whenever we delete or remove element from the
queue, the value of Front(F) is incremented by one.
9
Algorithm for insertion in a queue
(Using arrays)
QINSERT(queue[maxsize],item)
This algorithm inserts an item at the rear off the queue.
Step 1: Initialization
set Front=-1 and
set Rear=-1.
Step 2: Repeat step 3 to 5 until Rear < maxsize-1
Step 3: Read item.
Step 4: If Front== -1 then
Front=0
Rear=0
else
rear=rear+1
Step 5: Set queue[Rear]=item.
Step 6: Print, queue overflow.
10
Algorithm for deletion in a queue
(Using arrays)
QDELETE(queue[maxsize],item)
This algorithm deletes an item at the front of the queue.
Step 1: Repeat step 2 to 4 until Front >=0
Step 2: Set item=queue[Front]
Step 3: If Front== Real
set Front=-1
set Rear=-1
else
Front= Front+1
Step 4: Print, the number deleted is, item.
Step 5: Print, queue is empty.
11
Limitations of Simple Queue
Consider an example of simple queue Q[3], which is
initially empty.
Consider the following series of insertion and
deletion operations performed on the queue.
R=-1 and F=-1
FR (a) Initial queue
R=0 and F=0
10
FR (a) Queue with one element
12
Limitation of Simple Queue Contd..
R=1 and F=0
10 20
F R
© Queue with two elements
R=2 and F=0
10 20 30
(d) Queue with three elements
R=2 and F=1
20 30
(e) After deleting one element
13
Limitation of Simple Queue Contd..
R=2 and F=2
30
(e) After deleting element
R=2 and F=3
(f) After deleting element
Now if we attempt to add more elements, the
elements cannot be inserted, because in a queue the
new elements are always added from the rear end, and
here rear end indicates the last location.
14
Limitation of Simple Queue Contd..
Hence, though the space is there in the queue we are
not able to insert elements.
To solve this problem, one solution is: when an
element is deleted, shift all afterward elements to the
left by one position. But if the queue is too large then it
will be a difficult job to do and also takes too much
time.
Hence, to remove this queue we use circular queue.
15
Implementation of queue
A queue can be implemented in two ways
1) Using Arrays (Static Implementation)
2) Using Pointers (Dynamic Implementation)
16
Queue as an ADT
Abstract data type is a collection of data items and set
of operations performed on those data item. While
using queue as an ADT the following functions are
defined
insert(int x) insert data item x in to the queue.
delete() Delete the data element from the queue.
display() Display the value in a queue.
Note: Write program to implement queue as an ADT
yourself.
17
Queue program
/*Program of queue using array*/ printf("Enter your choice : ");
# include<stdio.h>
# define MAX 5 scanf("%d",&choice);
int queue_arr[MAX]; switch(choice)
int rear = -1; {
int front = -1; case 1 :
main() insert();
{ break;
int choice; case 2 :
while(1) del();
{ break;
case 3:
printf("1.Insert\n"); display();
break;
printf("2.Delete\n"); case 4:
exit(1);
printf("3.Display\n"); default:
printf("Wrong choice\n");
printf("4.Quit\n"); }/*End of switch*/
}/*End of while*/
}/*End of main()*/
18
insert() del()
{ {
int added_item; if (front == -1 || front > rear)
if (rear==MAX-1) {
printf("Queue Overflow\n"); printf("Queue Underflow\n");
else return ;
{ }
if (front==-1) /*If queue is initially else
empty */ {
front=0; printf("Element deleted from queue
printf("Input the element for adding is : %d\n", queue_arr[front]);
in queue : "); front=front+1;
scanf("%d", &added_item); }
rear=rear+1; return ;
queue_arr[rear] = added_item ; }/*End of del() */
}
return;
}/*End of insert()*/
19
display()
{
int i;
if (front == -1)
printf("Queue is empty\n");
else
{
printf("Queue is :\n");
for(i=front;i<= rear;i++)
printf("%d ",queue_arr[i]);
printf("\n");
}
return;
}/*End of display() */
20
Circular Queue
A circular queue is a queue in which the insertion of a new
element is done at the very first location of the queue, if the
last location of the queue is full and the first location is
empty.
In other words, if we have a queue q of size say N, then after
inserting an element to the (N-1)th location of the array, then
next element will be inserted at the very first location (i.e.
location with subscript 0) of the array, only if the first
location is empty.
Advantage: A circular queue overcomes the problem of
unutilized space in linear queue using array.
21
Circular Queue Contd…
22
Main module of circular queue
/* Program of circular queue using scanf("%d",&choice);
array*/ switch(choice)
# include<stdio.h> {
# define MAX 5 case 1 :
int cqueue_arr[MAX]; insert();
int front = -1; break;
int rear = -1; case 2 :
main() del();
{ break;
int choice; case 3:
while(1) display();
{ break;
printf("1.Insert\n"); case 4:
printf("2.Delete\n"); exit(1);
printf("3.Display\n"); default:
printf("4.Quit\n"); printf("Wrong choice\n");
printf("Enter your choice : "); }/*End of switch*/
}/*End of while */
}/*End of main()*/
23
Insertion in circular queue
insert() else
{ if(rear == MAX-1)/*rear is at
int added_item; last position of queue */
if((front == 0 && rear == MAX-1) || rear = 0;
(front == rear+1)) else
{ rear = rear+1;
printf("Queue Overflow printf("Input the element for
\n"); insertion in queue : ");
return; scanf("%d", &added_item);
} cqueue_arr[rear] = added_item ;
if (front == -1) /*If queue is empty */ }/*End of insert()*/
{
front = 0;
rear = 0;
}
24
Deletion on circular queue
del() {
{ front = -1;
if (front == -1) rear=-1;
{ }
printf("Queue Underflow\n"); else
return ; if(front == MAX-1)
} front = 0;
printf("Element deleted from queue else
is : %d\n",cqueue_arr[front]); front = front+1;
if(front == rear) /* queue has only }/*End of del() */
one element */
25
Display in circular queue
display() while(front_pos <= MAX-1)
{ {
int front_pos = front,rear_pos = rear; printf("%d ",cqueue_arr[front_pos]);
if(front == -1)
{ front_pos++;
printf("Queue is empty\n"); }
return; front_pos = 0;
} while(front_pos <= rear_pos)
printf("Queue elements :\n"); {
if( front_pos <= rear_pos ) printf("%d ",cqueue_arr[front_pos]);
while(front_pos <= rear_pos)
{ front_pos++;
printf("%d ",cqueue_arr[front_pos]); }
}/*End of else */
front_pos++; printf("\n");
} }/*End of display() */
else
{
26
Linear and circular queue
27
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.
28
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.
29
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.
30
31
Descending order 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.
32
33
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.
34
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.
35
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.
36
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 node; if it is found out of order, elements
are swapped. This process continues until the element is
placed in a correct position
37
38
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.
39
Applications of Priority queue
The following are the applications of the priority
queue:
It is used in the Dijkstra's shortest path algorithm.
It is used in prim's algorithm
It is used in data compression techniques like Huffman
code.
It is used in heap sort.
It is also used in operating system like priority
scheduling, load balancing and interrupt handling.
40
Dequeue and enqueue
The dequeue stands for Double Ended Queue. In the
queue, the insertion takes place from one end while
the deletion takes place from another end. The end at
which the insertion occurs is known as the rear
end whereas the end at which the deletion occurs is
known as front end.
Deque is a linear data structure in which the insertion
and deletion operations are performed from both
ends. We can say that deque is a generalized version of
the queue.
41
Dequeue
42
Let's look at some properties of
deque.
Deque can be used both as stack and queue as it
allows the insertion and deletion operations on both
ends.
In deque, the insertion and deletion operation can be
performed from one side. The stack follows the LIFO
rule in which both the insertion and deletion can be
performed only from one end; therefore, we conclude
that deque can be considered as a stack.
43
In deque, the insertion can be performed on one end, and the
deletion can be done on another end. The queue follows the FIFO
rule in which the element is inserted on one end and deleted from
another end. Therefore, we conclude that the deque can also be
considered as the queue.
44
There are two types of Queues, Input-restricted
queue, and output-restricted queue.
Input-restricted queue: The input-restricted queue
means that some restrictions are applied to the
insertion. In input-restricted queue, the insertion is
applied to one end while the deletion is applied from
both the ends.
45
Output-restricted queue: The output-restricted
queue means that some restrictions are applied to the
deletion operation. In an output-restricted queue, the
deletion can be applied only from one end, whereas
the insertion is possible from both ends.
46
Applications of Queues
All types of customer service (like railway/airplane
ticket reservation) center software's are designed using
queues to store customer’s information.
Round robin technique for processor scheduling is
implemented using queues.
Printer server (a dedicated computer to which a printer
is attached) routines are designed using queues. A
number of users (computers) share a printer using
printer server, the printer server then spools all the
jobs from all the users, to the server’s hard disk in a
queue. From here, jobs are printed one-by-one
according to their number in the queue.
47
End of Unit: 3
48
