1

@ McGraw-Hill Education

Copyrighted Material -Additional resource material supplied with the book Data Structures and Algorithms : Concepts, Techniques and Applications authored by G.A.V. Pai and published by
Tata McGraw Hill. This resource material is for Instructor's use only.

Queues
(Chapter 5)

PROPRIETARY MATERIAL. 2008 The McGraw-Hill Companies, Inc. All rights reserved. No part of this PowerPoint slide may be displayed, reproduced or distributed
in any form or by any means, without the prior written permission of the publisher, or used beyond the limited distribution to teachers and educators permitted by McGraw-Hill
for their individual course preparation. If you are a student using this PowerPoint slide, you are using it without permission.

Outline of Chapter
1. Introduction
- Definition
- Operations on queues
2. Linear Queue implementation
- Using array as a queue
- Implementation of insert and delete operations on a queue
- Limitations of linear queues
3. Circular queues
- Operations on circular queues
- Implementation of insert and delete operations on a circular queue

4. Other types of queues

- Priority queues
- Deques

5. Applications
6. ADT for queues

1. INTRODUCTION

Definition: What is Queue?

A Queue is a linear list in which all insertions are

made at one end of the list known as rear or tail of

the queue and all deletions are made at the other
end known as front or head of the queue.
Front

a
Front

c
Rear

A queue
Rear

What is Queue (2) ?

Assume that we have a queue Q
An insertion operation is also
referred to as enqueuing a
queue

A deletion operation is referred

to as dequeuing a queue.

A queue data structure obeys

the principle of first in first out

(FIFO) or first come first served
(FCFS)

Front
Rear
(a) A queue Q
a

b
d

Front
Rear
(b) Insert d into Q
b

Front
Rear
(c) Delete from Q

Operations on Queue?
The queue data

structure supports
two operations viz.,
Insertion (or addition
or enqueue) of
elements to a queue
Deletion (or removal
or dequeue) of
elements from a
queue

Front
Rear
(a) A queue Q
a

b
d

Front
Rear
(b) Insert d into Q
b

Front
Rear
(c) Delete from Q

Different Types of Queues

Linear queue
Priority queue

Deque

Conceptual View
rear
front
H

Circular queue

C
E

2. LINEAR QUEUES
IMPLEMENTATION

Implementing Queue Data

2 ways:
Objects

A common method of implementing a queue data

structure is to use another sequential data structure
viz, arrays (Chapter 3).

The Front and Rear variables contain indices of Front and Rear

Queues have also been implemented using a linked

data structure (Chapter 6)

the array implementation puts a limitation on the capacity of

the queue

R S

Front
Rear
A queue Q

Fron 0
Rear 4
t
R S V G
[1] [2] [3] [4] [5] [6]
[7]
Array representation
of Q[1:7]

10

Implementing Queue Data Objects

(2)
2 ways:

A common method of implementing a queue data

structure is to use another sequential data structure
viz, arrays (Chapter 3).

The Front and Rear variables contain indices of Front and Rear

Queues have also been implemented using a linked

data structure (Chapter 6)

the array implementation puts a limitation on the capacity of

the queue

R
R S

G
S

Front
Rear
A queue Q

G
Linked List

11

Queue Operations - Insertion

Every insertion (or enqueue) of an element

into the queue will increment the value of Rear.

Front
R

Rear

0
V

[1] [2] [3] [4] [5] [6] [7]

Array representation of
Q[1:7]
Front
R

Rear

0
V

7
A

[1] [2] [3] [4] [5] [6] [7]

Array representation of
Q[1:7]

12

Queue Operations Insertion

enqueue) of an element
Every insertion (or (2)
into the queue has to necessarily test for a
QUEUE-FULL condition before executing the
insertion operation.
Fron 0
Rear 7
t
R S V G P A
Y
[1] [2] [3] [4] [5] [6]
[7]
Array representation
of Q[1:7]
N=7

Queue-Full
When
Rear=N
Where
N=size of
queue

13

Queue Operations - Deletion

Every deletion (or dequeue) of an element from

the queue will increment the value of Front.

Front
R

Rear

7
A

[1] [2] [3] [4] [5] [6] [7]

Array representation of
Q[1:7]
Front
Deque R

Rear

1
V

7
A

[1] [2] [3] [4] [5] [6] [7]

Array representation of
Q[1:7]

14

Queue Operations - Deletion

Each deletion (or dequeue) has to ensure that it

is not attempted on a queue which is already empty
calling for the need to test for a QUEUE-EMPTY
condition before executing the deletion operation.

Fron 0
t

Rear 0

[1] [2] [3] [4] [5] [6]

[7]
Array representation
of Q[1:7]

QueueEmpty
When
Rear=Front

15

Queue: Insert Algorithm

Algorithm 5.1:
a queue

Implementation of an insert operation on

procedure INSERTQ (Q, n, ITEM, REAR)

/* insert item ITEM into Q with
capacity n */
if (REAR = n) then QUEUE_FULL;
REAR = REAR + 1;
/* Increment REAR*/
Q[REAR] = ITEM;
/* Insert ITEM as
the rear element*/
end INSERTQ
Insert Data into
Queue, if OK

Checking for
Queue-Full

16

Queue: Delete Algorithm

Algorithm 5.2:
queue

Implementation of a delete operation on a

procedure DELETEQ (Q, FRONT, REAR, ITEM )

/* delete ITEM from FRONT
of Q */
if (FRONT =REAR) then QUEUE_EMPTY;
FRONT = FRONT +1;
ITEM = Q[FRONT];
end DELETEQ.
Delete Data
from Queue, if
OK

Checking for
Queue-Empty

17

Limitation of Linear Queues?

Queues whose insert / delete operations follow
the procedures implemented in Algorithms 5.1
and 5.2, are known as linear queues

Limitations of Linear Queues?

When a QUEUE_FULL condition is invoked it

does not necessarily imply that the queue is

physically full.
This leads to the limitation of rejecting insertions
despite the space available to accommodate them.

SOLUTION? The rectification of this limitation

leads to what are known as circular queues.

18

3. CIRCULAR QUEUES

19

Circular Queues?
As the name indicates a

circular queue is not linear

in structure but instead
circular.
In other words, the FRONT
and REAR variables which
displayed a linear (left to
right) movement over a
queue, display a circular
movement (clock wise) over
the queue data structure.
Implementation: Use array
Question? How do we
determine the next location
in circular manner?
Answer? Use mod operator

Conceptual View
rear
front
H

C
E

0 1 2 3

4 5

7
A B C D E F G

front

rear

6
H

20

Circular Queue: Insert

Algorithm 5.3: Implementation
of insert operation on a circular
Algorithm
queue (with 5 parameters)

procedure INSERT_CIRCQ(CIRC_Q, FRONT,REAR, n,

ITEM)
If
(FRONT
=(REAR
+
1)
mod
n)
then
CIRCQ_FULL; /* Here CIRCQ_FULL tests for the
queue full
condition and if so,
retracts
REAR
to
its
previous
value*/
REAR=(REAR + 1) mod n;
CIRC_Q [REAR]= ITEM; // if OK, insert ITEM
end INSERT_CIRCQ.

21

Circular Queue: Delete

Algorithm

Algorithm 5.4:
circular queue.

Implementation of a delete operation on a

Procedure DELETE_CIRCQ(CIRC_Q, FRONT,REAR, n,

ITEM)
If (FRONT = REAR) then CIRCQ_EMPTY;
/* CIRC_Q is physically empty*/
FRONT = (FRONT+1) mod n; // find location
ITEM = CIRC_Q [FRONT]; // get @ remove value
end DELETE_CIRCQ
Eg: FRONT=0; n=8
Then FRONT=(FRONT + 1) mod n = 1 mod 8 = 1
Eg: FRONT=5; n=8
Then FRONT=(FRONT + 1) mod n = 6 mod 8 = 6

22

4. OTHER TYPES OF QUEUES :

PRIORITY QUEUES & DEQUES

23

(I) Priority Queues

A priority queue is a queue in which insertion or

deletion of items from any position in the queue are

done based on some property (such as priority of task)
A common method of implementation of a priority queue
is to open as many queues as there are priority factors.
A low priority queue will be operated for deletion only when all
its high priority predecessors are empty.

Another method of implementation could be to sort the

elements in the queue according to the descending
order of priorities every time an insertion takes place.

The top priority element at the head of the queue is the one to
be deleted.

24

(I) Priority Queues

Implementations:
#1 - Multiple queues as there are priority factors.

A low priority queue will be operated for deletion only when all
its high priority predecessors are empty.

#2 - Single list with sorted elements in the queue

according to the descending order of priorities every

time an insertion takes place.

25

(II) Deques
A deque (double ended queue) is a linear list

in which all insertions and deletions are

made at the end of the list.
A deque is therefore more general than a
stack or queue and is a sort of FLIFLO (first in
last in or first out last out).
Thus while one speaks of the top or bottom
of a stack, or front or rear of a queue, one
refers to the right end or left end of a deque.

26

Deques (2)

A deque has two variants, viz., input

restricted deque and output restricted

deque.

An input restricted deque:

where insertions are allowed at one end only
while deletions are allowed at both ends.

An output restricted deque:

Allows insertions at both ends of the deque
but permits deletions only at one end.

A deque is commonly implemented as a

circular array with two variables LEFT
and RIGHT taking care of the active
ends of the deque

Conceptual
View
rear
front
H A
G

C
E

27

5. APPLICATION OF QUEUES

28

App#1: CPU TIME SHARING

SYSTEM
A CPU (processor) endowed
with
memory resources, is to be shared
by n number of computer users. The
sharing of the processor and memory
resources is done by allotting a
definite time slice of the processors
attention on the users and in a
round-robin fashion.

Job leaves
CPU

In a system such as this the users are

unaware of the presence of other
users and are led to believe that their
job receives the undivided attention
of the CPU.

However, to keep track of the jobs

initiated by the users, the processor

relies on a queue data structure
recording the active user-ids.

New job
enters (with
user-id)

29

Application of Priority Queues

Assume a CPU time sharing system in which job

requests by users are of different categories. Some

requests
may be real time,
the others online and
the last may be batch processing requests.

It is known that

real time job requests carry the highest priority,

followed by online processing and
batch processing in that order.

In such a situation the job scheduler needs to maintain a

priority queue to execute the job requests based on
there priorities.

30

App#2: ATM Simulation

Bank ATM System

31

6. ADT FOR QUEUES

32

ADT for Queue?

Data objects:
A finite set of elements of the same type
Operations:
Create an empty queue and initialize front and rear
variables of the queue
CREATE ( QUEUE, FRONT, REAR)
Check if queue QUEUE is empty
CHK_QUEUE_EMPTY (QUEUE ) (Boolean
function)
Check if queue QUEUE is full
CHK_QUEUE_FULL (QUEUE) (Boolean
function)
Insert ITEM into rear of queue QUEUE
ENQUEUE (QUEUE, ITEM)
Delete element from the front of queue QUEUE and output
the
element deleted in ITEM

33

7. CONCLUSION

34

Conclusion
A Queue is a linear list in which all insertions are
made at one end of the list known as rear or tail of
the queue and all deletions are made at the other end
known as front or head of the queue.
An insertion operation is also referred to as
enqueuing a queue and a deletion operation is
referred to as dequeuing a queue.
A queue data structure obeys the principle of first
in first out (FIFO) or first come first served (FCFS)
Different types of queues:
Linear queues
Circular queue
Deques (double ended queue)
Priority queues