IT T33 / DATA STRUCTURES UNIT 2
QUEUES
Queues: Queue abstract data type - Array implementation – circular queue - linked list implementation
of queues – priority queues – double ended queues – multiple stacks and queues - application.
2.1 QUEUE
Queue is an ordered collection of elements in which insertion are made at one end and deletion
are made at another end. The end at which insertion are made is referred as rear end. The end
from which deletion are made is referred as front end. In a queue the first element is to be
deleted, so that queue is known as “first in first out”.
The primary operation that can be done on a queue are:
1. Enqueue (Insert)
2. Dequeue(Delete)
An enqueue operation adds a new element in the queue, this process is carried out by
incrementing the rear end and adding the new element in the rear position.
A dequeuer operation delete an element from the queue, this process is carried out by
incrementing the front end and deleting the element a front end position.
Types of queue
1. Linear Queue
2. Circular Queue
3. Double ended queue
(i) Linear queue
Linear queue is an ordered collection of elements in which insertion are made at one end and
deletion are made at another end. The end at which insertion are made is referred as rear end.
The end from which deletion are made is referred as front end.
In a queue the first element is to be deleted, so that queue is known as “first in first out”.
(ii) Circular Queue
Circular Queue is the form of linear queue in which last position is connected to the first
position of the queue. Circular queue also has two ends:- 1. Front 2. Rear
The front end is where we delete element and the rear end is where we insert element. The next
position of the rear is front, then the queue is said to be fully occupied.
1
IT T33 / DATA STRUCTURES UNIT 2
(iii) Double Ended Queue
In double ended queue, insertion and deletion are made at both rear and front end of the queue.
They are two variations of deque.
1. Input restricted deque
2. Output restricted deque
In input restricted deque, insertion is restricted at one end only (it can be either front or rear
end). In output restricted deque, the deletion is restricted to one end only (it can be either front or
rear end).
Types of deque
1. Linear deque
2. Circular deque
Linear Deque
It is similar to the linear queue except the following conditions:
If the front pointer is in the first position (zeroth position), we can’t insert data at front end.
If the rear is in the last position (queuesize-1) we can’t insert data at rear end.
Circular Deque
Circular deque is similar to circular queue except the following conditions:
Insertion and deletion are made at front and rear end of the queue. Irrespective of the position of
the front and rear we can insert and delete.
2.1.1 STATIC IMPLEMENTATION (REPRESENTATION) OF LINEAR QUEUE
A queue is logically a first in first out (FIFO or first come first serve) linear data structure. The
concept of queue can be understood by our real life problems.
For example a customer come and join in a queue to take the train ticket at the end (rear) and the
ticket is issued from the front end of queue.
That is, the customer who arrived first will receive the ticket first. It means the customers are
serviced in the order in which they arrive at the service centre.
Representation of linear queue
The representation of queue can be done in two ways. They are
1. Array representation of queue [Static implementation of queue]
2
IT T33 / DATA STRUCTURES UNIT 2
2. Linked list representation of queue [Dynamic implementation of queue]
Array representation of queue:
One of the simplest ways of representing a queue is by means of single dimensional array. Both
queue & array are the ordered collection of elements but queue & array are different things.
Basic operations
1. Enqueue
2. Dequeue
3. Display
The rear pointer is in the last position (queue size-1) then queue is said to be fully occupied.
Initially the front end and the rear end are at the same position (-1). When you insert elements,
rear pointer moves one by one until the last position is reached.
When we delete elements, the front pointer moves one by one until the rear pointer is reached.
The next position of rear is front, for only circular queue, then the queue is said to be fully
occupied. Beyond this we can’t insert the data, irrespective of position of front pointer; this is a
main disadvantage of linear queue which is overcome by circular queue.
The sample queue diagram is shown below.
Three states of queue with representation are given below.
1. Queue is empty.
i. FRONT=0
ii. REAR =0
2. Queue is full. :
i. REAR=N
ii. FRONT=1
3. Queue contain element _> 1
i. FRONT _< REAR
ii. Number of element =REAR-FRONT+1
ALGORITHM ENQUEUE /* using array*/
1. If (REAR = N) then
2. Print “Queue is full”
3. Exit
3
IT T33 / DATA STRUCTURES UNIT 2
4. Else
5. If (REAR = 0) and (FRONT = 0) then
6. FRONT=1
7. Endif
8. REAR = REAR+1
9. Q[REAR] = ITEM
10. Endif
11. Stop.
ALGORITHM DEQUEUE /* using array */
1. If (FRONT=0) then
2. Print “queue is empty”
3. Exit
4. Else
5. Item= Q [FRONT] // get the element
6. IF (FRONT=REAR) // queue contain single element.
7. REAR=0
8. FRONT=0
9. Else
10. FRONT=FRONT+1
11. Endif
12. Endif
13. Stop.
2.1.2 DYNAMIC IMPLEMENTATION (REPRESENTATION) OF LINEAR QUEUE
Another method of implementation of queue is linked list. In this queue enqueue operation is
performed at end of the list. Dequeue operation is performed at the front of the list.
Basic operations:
a. Enqueue
b. Dequeue
c. Display
Enqueue:
struct node
{
int data;
struct node link;
} front=NULL; rear=NULL;
Algorithm enqueue (struct node *front, struct node *rear)
{
struct node *newnode;
newnode=new node;
read rollno;
4
IT T33 / DATA STRUCTURES UNIT 2
newnode->data=rollno;
newnode->link=NULL;
if front=NULL and rear=NULL
{
front=newnode;
rear=newnode;
}
else
{
rear->link=newnode;
rear=newnode;
}
return;
}
Dequeue:
Algorithm enqueue(struct node *front, struct node *rear)
{
struct node *temp;
if front=NULL and rear=NULL
{
write "Queue is in underflow condition. Dequeue operaation is not possible.";
return;
}
if front=rear
{
front=rear=NULL;
}
else
{
front=front->link;
}
delete temp;
return;
}
Display:
Algorithm enqueue (struct node *front, struct node *rear)
{
struct node *temp;
if front=NULL and rear=NULL
{
write "Queue is in underflow condition. Dequeue operaation is not possible.";
return;
}
temp=front;
while(temp!=front)
{
5
IT T33 / DATA STRUCTURES UNIT 2
write temp->data;
temp=temp->link;
}
return;
}
2.2 CIRCULAR QUEUE
Circular Queue is another form of linear queue in which last position is connected to the first
position of the queue.
Circular queue also has two ends:-
Front
Rear
The front end is where we delete element and the rear end is where we insert element. The next
position of the rear is front, then the queue is said to be fully occupied.
Example linear queue and its equivalent circular queue diagram is shown below
From the above figure we have to delete the element 10, 20, 30. The front pointer is shifted
ahead.
From the figure even though free spaces are available still we can’t insert any element because
the queue is full.
To overcome this problem by using circular queue. Consider the circular queue contain the
elements 10, 20, 30, 40, 50.Consider the elements are going to delete are 10, 20, 30.
There is a formula which has to be applied for setting the front and rear pointers for a circular
queue.
6
IT T33 / DATA STRUCTURES UNIT 2
Rear = (Rear +1) % Size
Front= (Front +1) % Size
From the figure the front link points q[0] and rear links points q[4]
From the above figure we are deleting the element 10 present in the location q[0] now the front
pointer points to the location q[1] based on the formula
From the fig we are deleting the element 20 present in the location q[1] and now the front
pointers points to element 30 present in the location q[2].
From the fig we are inserting the element 60, now the rear pointer moves from the location 50
q[4] to 60 q[0]
7
IT T33 / DATA STRUCTURES UNIT 2
Algorithm Enqueue:
The enqueue operation is inserting element in the queue.
1. If (FRONT =0), then //when the queue is empty
2. FRONT = 1
3. REAR =1
4. CQ[FRONT] = ITEM
5. Else
6. Next = (REAR +1)%SIZE
7. If(Next != FRONT), then //If the queue is not full
8. REAR = Next
9. CQ[REAR] = ITEM
10. Else
11. Print “Queue is full”
12. Endif
13. Endif
14. Stop
Algorithm Dequeue:
Dequeue is the process of deleting element in the queue
1. If (FRONT = 0 ) then
2. Print “Queue is empty”
3. Exit
4. Else
5. ITEM = CQ[FRONT]
6. If (FRONT = REAR), then //If queue contains single element
7. FRONT = 0
8. REAR = 0
9. Else
10. FRONT = ((FRONT +1)SIZE)
11. Endif
12. Endif
13. Stop
Example:
Consider the circular queue of length = 4, perform the following operations
1. Encqueue (A) 2. Encqueue (B)
3. Encqueue(C) 4. Encqueue (D)
5. Decque 6. Encqueue (E)
8
IT T33 / DATA STRUCTURES UNIT 2
2.3 DOUBLE ENDED QUEUE (DEQUE)
A deque is a homogeneous list in which elements can be added or inserted (called push
operation) and deleted or removed from both the ends (which is called pop operation). ie; we can
add a new element at the rear or front end and also we can remove an element from both front
and rear end. Hence it is called Double Ended Queue.
There are two types of deque depending upon the restriction to perform insertion or deletion
operations at the two ends. They are
1. Input restricted deque
2. Output restricted deque
An input restricted deque is a deque, which allows insertion at only 1 end, rear end, but allows
deletion at both ends, rear and front end of the lists.
An output-restricted deque is a deque, which allows deletion at only one end, front end, but
allows insertion at both ends, rear and front ends, of the lists.
Basic operations
Enqueue - Front
9
IT T33 / DATA STRUCTURES UNIT 2
Algorithm enqueue (queue, front,rear,queuesize)
{
if front=0
{
write "Queue is in overflow condition. Enqueue is not possible."; return;
}
if front=-1 and rear=-1
{
front=rear=queuesize-1;
}
else
{
front=front-1;
}
read rollno;
queue[front]=rollno;
return;
}
Enqueue – rear
Algorithm enqueue (queue, front,rear,queuesize)
{
if front=0
{
write "Queue is in overflow condition. Enqueue is not possible.";
return;
}
if front=-1 and rear=-1
{
front=rear=0;
}
else
{
rear=rear+1;
}
read rollno;
queue[rear]=rollno;
return;
}
Dequeue – front
Algorithm dequeue(queue,front,rear)
{
if rear=-1 and front=-1
{
write "Queue is in underflow condition. Dequeue is not possible.";
10
IT T33 / DATA STRUCTURES UNIT 2
return;
}
write "Element to be deleted",queue[front];
if front=rear
{
front=rear=-1;
}
else
{
front=front+1;
}
return;
}
Dequeue – rear
Algorithm dequeue(queue,front,rear)
{
if rear=-1 and front=-1
{
write "Queue is in underflow condition. Dequeue is not possible.";
return;
}
write "Element to be deleted",queue[front];
if front=rear
{
front=rear=-1;
}
else
{
rear=rear-1;
}
return;
}
Example:
If we wish to insert any elements from front end, then have to shift all elements to right
11
IT T33 / DATA STRUCTURES UNIT 2
Insert 60and 70 in the queue front end:
Deletion of 40 and 50 from the rear end:
2.4 PRIORITY QUEUE
A priority queue is another variation of queue structure.
12
IT T33 / DATA STRUCTURES UNIT 2
In priority queue each element has been assigned a value called priority of value.
In priority queue element can be inserted or deleted not only at end and also any position.
Element of X of priority P, will be deleted before the element which is at Front.
Insertion of an element also based on priority, Instead of adding after the rear, it may be inserted
within the intermediate position based on priority value.
A priority queue does not follow the basic principle of priority queue as follows
An element of higher priority processed before any element of lower priority.
Two elements of same priority are processed according to the order in which they were
added to the queue
They are of two types:
1. Ascending Priority Queue
2. Descending Priority Queue
Ascending Priority Queue
It is a collection of elements in which the insertion of element can be any order, but only the
smallest element can be removed.
Descending Priority Queue
It is a collection of elements in which the insertion of element can be any order, but only the
largest element can be removed.
The priority queue elements are arranged in any order and out of which only the smallest or
largest element allowed to be deleted each time. The implementation of priority can be done by
using array and linked list. The data structure heap is used to implement priority queue
efficiently.
Basic Operations
Enqueue
Dequeue
Enqueue
13
IT T33 / DATA STRUCTURES UNIT 2
Algorithm enqueue(queue,front,rear,queuesize)
{
if rear=queuesize-1;
{
write "Queue is in overflow condition. Enqueue is not possible.";
return;
}
read rollno;
if front=-1 and rear=-1
{
front=rear=0;
}
else
{
i=rear;
while(i>=0)and (rollno<queue[i])
{
queue[i+1]=queue[i];
i=i-1;
}
queue[i+1]=rollno;
rear=rear+1;
return;
}
}
Dequeue
Algorithm dequeue(queue,front,rear)
{
if front=-1 and rear=-1
{
write "Queue is in underflow condition. Dequeue operation is not possible.";
return;
}
write "Element to be deleted", queue[front];
if front=rear
{
front=rear=-1;
}
else
{
front=front+1;
}
return;
}
An array can be maintained to hold the item and its priority value
14
IT T33 / DATA STRUCTURES UNIT 2
The element will be inserted at the rear end as usual
Deletion operation will be performed in either of two following ways
Starting from the FRONT pointer, have the array of highest priority
I. Delete this element form the queue.
Shift its entire trailing element after the deleted element one stroke each to fill up the vacant
position.
This implementation is very in efficient because searching the queue for highest priority element
and shifting the trailing elements after deletion.
II. Efficient implementation compared to the first one.
Add the elements at the REAR end as earlier.
Using a stable sorting algorithm.
Sort the elements of the queue so that highest priority will come first (FRONT).
Second implementation is comparatively better than first one.
Here only the burden is to sort the elements.
2.5 MULTIPLE STACKS AND QUEUES
Multiple Stacks:
None fixed size of the stacks:
15
IT T33 / DATA STRUCTURES UNIT 2
Stack 1 expands from the 0th element to the right
Stack 2 expands from the 12th element to the left
As long as the value of Top1 and Top2 are not next to each other, it has free elements for
input the data in the array
When both Stacks are full, Top1 and Top 2 will be next to each other
There is no fixed boundary between Stack 1 and Stack 2 o Elements –1 and –2 are using to
store the information needed to manipulate the stack (subscript for Top 1 and Top 2)
Fixed size of the stacks:
Stack 1 expands from the 0th element to the right
Stack 2 expands from the 6th element to the left
As long as the value of Top 1 is less than 6 and greater than 0, Stack 1 has free elements to
input the data in the array o As long as the value of Top 2 is less than 11 and greater than 5,
Stack 2 has free elements to input the data in the array
When the value of Top 1 is 5, Stack 1 is full
When the value of Top 2 is 10, stack 2 is full
Elements –1 and –2 are using to store the size of Stack 1 and the subscript of the array for
Top 1 needed to manipulate Stack 1
Elements –3 and –4 are using to store the size of Stack 2 and the subscript of the array for
Top 2 needed to manipulate Stack 2
Multiple Queues:
None fixed size of the queues:
Queue 1 expands from the 0th element to the right and circular back to the 0th element
Queue 2 expands from the 8th element to the left and circular back to the 8th element
Temporary boundary between the Queue 1 and the Queue 2; as long as there has free
elements in the array and boundary would be shift
Free elements could be anywhere in the Queue such as before the front, after the rear, and
between front and rear in the Queue
Queue 1‟s and Queue 2 „s size could be change if it is necessary. When the Queue 1 is full
and the Queue 2 has free space; the Queue 1 can increase the size to use that free space from
the Queue 2. Same way for the Queue 2
Elements –1, –2, and –3 are using to store the size of the Queue 1, the front of the Queue 1,
and the data count for the Queue 1 needed to manipulate the Queue 1
16
IT T33 / DATA STRUCTURES UNIT 2
Elements –4, –5, and –6 are using to store the size of the Queue 2, the front of the Queue 2,
and the data count for the Queue 2 needed to manipulate the Queue 2
Inserts data to the Queue 1, Q1Rear = (Q1Front + Q1count) % Q1Size
Inserts data to the Queue 2, Q2Rear = (Q2Front + Q2count) % Q2Size + Q1Size
Deletes data from the Queue 1, Q1Front = (Q1Front + 1) % Q1Size
Deletes data from the Queue 2, Q2Front = (Q2Front + 1) % Q2Size + Q1Size
Fixed size of the queue:
Queue 1 expands from the 0th element to the 4th element and circular back to 0th element
Queue 2 expands from the 8th element to the 5th element and circular back to 8th element
The boundary is fixed between the Queue 1 and the Queue 2
Free elements could be anywhere in the Queue such as before the front, after the rear, and
between front and rear in the Queue
Elements –1, –2, and –3 are using to store the size of the Queue 1, the front of the Queue 1,
and the data count for the Queue 1 needed to manipulate the Queue 1
Elements –4, –5, and –6 are using to store the size of the Queue 2, the front of the Queue 2,
and the data count for the Queue 2 needed to manipulate the Queue 2
Inserts data to the Queue 1, Q1Rear = (Q1Front + Q1count) % Q1Size
Inserts data to the Queue 2, Q2Rear = (Q2Front + Q2count) % Q2Size + Q1Size
Deletes data from the Queue 1, Q1Front = (Q1Front + 1) % Q1Size
Deletes data from the Queue 2, Q2Front = (Q2Front + 1) % Q2Size + Q1Size
2.6 APPLICATIONS OF QUEUE
The main applications of queue are.
Batch processing in an operating system
To implement priority Queues.
Priority queues can be used to sort the elements using Heap Sort.
17
IT T33 / DATA STRUCTURES UNIT 2
Simulation.
Mathematics user Queuing theory.
Computer networks where the server takes jobs of the client as per the queue strategy
There are several algorithms that use queues to give efficient running times.
When jobs are submitted to a printer, they are arranged in order of arrival. Thus, essentially, jobs
sent to a line printer are placed on a queue we say essentially a queue, because jobs can be
killed. This amounts to a deletion from the middle of the queue, which is a violation of the strict
definition.
Virtually every real-life line is (supposed to be) a queue. For instance, lines at ticket counters are
queues, because service is first-come first-served.
Another example concerns computer networks. There are many network setups of personal
computers in which the disk is attached to one machine, known as the file server. Users on other
machines are given access to files on a first-come first-served basis, so the data structure is a
queue.
Calls to large companies are generally placed on a queue when all operators are busy.
In large universities, where resources are limited, students must sign a waiting list if all
terminals are occupied. The student who has been at a terminal the longest is forced off first, and
the student who has been waiting the longest is the next user to be allowed on.
A whole branch of mathematics, known as queueing theory, deals with computing,
probabilistically, how long users expect to wait on a line, how long the line gets, and other such
questions. The answer depends on how frequently users arrive to the line and how long it takes
to process a user once the user is served. Both of these parameters are given as probability
distribution functions. In simple cases, an answer can be computed analytically.
An example of an easy case would be a phone line with one operator. If the operator is busy,
callers are placed on a waiting line (up to some maximum limit). This problem is important for
businesses, because studies have shown that people are quick to hang up the phone.
18
