IMC12203

CHAPTER 5
QUEUE
 ◦ Introduction

◦ Operations on queues
◦ Queue implementation
◦ Implementation of insert and delete operations on a queue
◦ Limitations of linear queues

◦ Circular queues

Outline ◦ Operations on circular queues

◦ Implementation of insert and delete operations on a circular queue
◦ Other types of queues

◦ Priority queues
◦ Deques
◦ Applications

◦ ADT for queues

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
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
 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)
OPERATIONS ON QUEUES
• The queue data structure supports two operations eg.,
Insertion or addition of elements to a queue
Deletion or removal of elements from a queue

FRONT
Q[1:7] 1
R S V G REAR
4
[1] [2] [3] [4] [5] [6] [7]

FRONT REAR
Array implementation of a queue
 OPERATIONS ON QUEUES

• A common method of implementing a queue data structure is

to use another sequential data structure eg, arrays.
• the array implementation puts a limitation on the capacity of
the queue(n) eg. Q[1:n]
• every insertion of an element into the queue has to necessarily
test for a QUEUE-FULL condition before executing the
insertion operation.
• Again, each deletion 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.
Algorithm 5.1: Implementation of an insert operation on a queue
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

- Addition of every new element into the queue, increments

the rear variable
- Before insertion the condition whether the queue is full
(QUEUE_FULL) is checked so no overflow of elements
Algorithm 5.2: Implementation of a delete operation on a
queue
procedure DELETEQ (Q, FRONT, REAR, ITEM )

if (FRONT =REAR) then QUEUE_EMPTY;

FRONT = FRONT +1;
ITEM = Q[FRONT]; - Deletion operation automatically deletes the front
end DELETEQ. element of queue
- Variable ITEM is used as an output variable to
store and display value of removed element.
- If Queue not empty, FRONT is incremented by 1
- FRONT = REAR ensure queue is empty
- REAR = n maximum capacity of queue
Example
Let BIRDS[1:3] be a queue.

[1] [2] [3]

1. Insert ‘DOVE’ into BIRDS

2. Insert ‘PEACOCK’ into BIRDS
3. Insert ‘PIGEON’ into BIRDS
4. Insert ‘SWAN’ into BIRDS
5. Delete twice from BIRDS
6. Insert ‘SWAN’ into BIRDS
7. Delete twice from BIRDS
 [Link] ‘DOVE’ into BIRDS [1:3]

BIRDS[1:3] BIRDS[1:3]
DOV Insert ‘DOVE’ successful
E
procedure INSERTQ (Q, n, ITEM, REAR)
[1] [2] [3] [1] [2] [3] /*insert item ITEM into Q with
capacity n */
FRONT 0 REAR 0 FRONT 0 REAR 1
if (REAR = n) then QUEUE_FULL;
REAR = REAR + 1; /* Increment REAR*/
Q[REAR] = ITEM; /* Insert ITEM as the
rear element*/
[Link] ‘PEACOCK’ into BIRDS [1:3] end INSERTQ

BIRDS[1:3] BIRDS[1:3]
DOV DOV PEACOC
K Insert ‘PEACOCK’
E E successful

[1] [2] [3] [1] [2] [3]

FRONT 0 REAR 1 FRONT 0 REAR 2
 [Link] ‘PIGEON’ into BIRDS [1:3]

BIRDS[1:3] BIRDS[1:3]
DOV PEACOC
K DOV PEACOC
K
PIGEON Insert ‘PIGEON’
E E successful

[1] [2] [3] [1] [2] [3]

FRONT 0 REAR 2 FRONT 0 REAR 3

[Link] ‘SWAN’ into BIRDS [1:3]

BIRDS[1:3] BIRDS[1:3]
DOV PEACOC
K
PIGEON
DOV PEACOC
K
PIGEON
Insert ‘SWAN’ failure,
E E QUEUE_FULL condition
invoked
[1] [2] [3] [1] [2] [3]
FRONT 0 REAR 3 FRONT 0 REAR 3
 [Link]

BIRDS[1:3] BIRDS[1:3]
DOV PEACOC
K
PIGEON PEACOC
K
PIGEON
Delete successful
E ITEM = DOVE

[1] [2] [3] [1] [2] [3] procedure DELETEQ (Q, FRONT, REAR, ITEM )

FRONT 0 REAR 3 FRONT 1 REAR 3 if (FRONT =REAR) then QUEUE_EMPTY;

FRONT = FRONT +1;
ITEM = Q[FRONT];
end DELETEQ.

[Link]

BIRDS[1:3] BIRDS[1:3]
PEACOC
K
PIGEON PIGEON
Delete successful
ITEM = PEACOCK

[1] [2] [3] [1] [2] [3]

FRONT 1 REAR 3 FRONT 2 REAR 3
 [Link] ‘SWAN’ into BIRDS[1:3]

BIRDS[1:3] BIRDS[1:3]
PIGEON
PIGEON
Insert ‘SWAN’ failure,
QUEUE_FULL condition
invoked
[1] [2] [3] [1] [2] [3]
FRONT 2 REAR 3 FRONT 2 REAR 3

[Link]

BIRDS[1:3] BIRDS[1:3]
PIGEON
Delete successful
ITEM = PIGEON

[1] [2] [3] [1] [2] [3]

FRONT 2 REAR 3 FRONT 3 REAR 3
 [Link]

BIRDS[1:3] BIRDS[1:3]
QUEUE_EMPTY
condition invoked

[1] [2] [3] [1] [2] [3]

FRONT 3 REAR 3 FRONT 3 REAR 3
 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.
 The rectification of this limitation leads to what are known as
circular queues.
 Circular queues
 A circular queue is not linear in structure but instead circular.
 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.
Circular movement of FRONT and REAR variables in a circular queue
Circular queues
Algorithm 5.3: Implementation of insert operation on a circular queue
procedure INSERT_CIRCQ(CIRC_Q, FRONT,REAR, n, ITEM)
REAR=(REAR + 1) mod n;
If (FRONT = REAR) then CIRCQ_FULL;
/* Here CIRCQ_FULL tests for the queue full condition
and if so, retracts REAR to its previous value*/

CIRC_Q [REAR]= ITEM;

end INSERT_CIRCQ.
Algorithm 5.4: Implementation of a delete operation on a circular queue.
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;
ITEM = CIRC_Q [FRONT];
end DELETE_CIRCQ
Example

Let COLOURS[0:3] be a circular queue.

[0] [1] [2] [3]

1. Insert ‘Orange’ into COLOURS

2. Insert ‘Blue’ into COLOURS
3. Insert ‘White’ into COLOURS
4. Insert ‘Red’ into COLOURS
5. Delete twice from COLOURS
6. Insert ‘Yellow’ into COLOURS
7. Insert ‘Violet’ into COLOURS
 procedure INSERT_CIRCQ(CIRC_Q,FRONT,REAR,n,ITEM)
REAR=(REAR + 1) mod n;
If (FRONT = REAR) then CIRCQ_FULL;
CIRC_Q [REAR]= ITEM;
[Link] ‘ORANGE’ into COLOURS [0:3] end INSERT_CIRCQ.

COLOURS[0:3] COLOURS[0:3]
ORANG
E
Insert ‘ORANGE’
successful

[0] [1] [2] [3] [0] [1] [2] [3]

FRONT 0 REAR 0 FRONT 0 REAR 1

Follow index number 0

[Link] ‘BLUE’ into COLOURS [0:3]

COLOURS[0:3] BIRDS[1:3]
ORANG
E
ORANG
E
BLUE Insert ‘BLUE’ successful

[0] [1] [2] [3] [0] [1] [2] [3]

FRONT 0 REAR 1 FRONT 0 REAR 2
 procedure INSERT_CIRCQ(CIRC_Q,FRONT,REAR,n,ITEM)
REAR=(REAR + 1) mod n;
If (FRONT = REAR) then CIRCQ_FULL;
CIRC_Q [REAR]= ITEM;
[Link] ‘WHITE’ into COLOURS [0:3] end INSERT_CIRCQ.

COLOURS[0:3] COLOURS[0:3]
ORANG
BLUE ORANG
BLUE WHITE Insert ‘WHITE’
E E
successful

[0] [1] [2] [3] [0] [1] [2] [3]

FRONT 0 REAR 2 FRONT 0 REAR 3
Follow index number 0

[Link] ‘RED’ into COLOURS [0:3]

COLOURS[0:3] BIRDS[1:3]
ORANG
E
BLUE WHITE ORANG
E
BLUE WHITE CIRQ_FULL condition is
invoked. Insert ‘RED’ failure.
Note: REAR retracts
to its previous value of 3
[0] [1] [2] [3] [0] [1] [2] [3]
FRONT 0 REAR 3 FRONT 0 REAR 3
 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;
5,[Link] twice from COLOURS [0:3] ITEM = CIRC_Q [FRONT];
end DELETE_CIRCQ
COLOURS[0:3] COLOURS[0:3]
ORANG
BLUE WHITE WHITE DELETE operation
E
successful
ITEM=ORANGE
[0] [1] [2] [3] [0] [1] [2] [3] ITEM=BLUE

FRONT 0 REAR 3 FRONT 2 REAR 3

[Link] ‘YELLOW’ into COLOURS [0:3]

COLOURS[0:3] BIRDS[1:3]
WHITE YELLOW WHITE Insert ‘YELLOW’
successful

[0] [1] [2] [3] [0] [1] [2] [3]

FRONT 2 REAR 3 FRONT 2 REAR 0
 [Link] ‘VIOLET’ into COLOURS [0:3]

COLOURS[0:3] BIRDS[1:3]
YELLOW WHITE YELLOW VIOLET WHITE Insert ‘VIOLET’
successful

[0] [1] [2] [3] [0] [1] [2] [3]

FRONT 2 REAR 0 FRONT 2 REAR 1
 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.
 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.
 A deque has two variants, eg., input restricted
deque and output restricted deque.
 An input restricted deque is one where
insertions are allowed at one end only while
deletions are allowed at both ends.
 On the other hand, 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
 Applications
 Application Of A Linear Queue : A 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
processor’s attention on the users and in a round- robin fashion.

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.
 Application of priority queues
Assume a time sharing system in which job requests by users are
of different categories.

For example, 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.
 ADT for Queues

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
DEQUEUE (QUEUE , ITEM)
 Exercise 1
Let INITIALISE (Q) be an operation which initializes a linear queue Q to be empty. Let ENQUEUE (Q, ITEM) insert an ITEM
into Q and DEQUEUE (Q, ITEM) delete an element from Q through ITEM. EMPTY_QUEUE (Q) is a Boolean function which
is true if Q is empty and false other wise, and PRINT (ITEM) is a function which displays the value of ITEM.
What is the output of the following pseudo code?
 Exercise 2
Given Q to be a circular queue implemented as an array Q[0:4]. What is the output of the following code? [Note: The
procedures ENQUEUE (Q, X) and DEQUEUE (Q, X) may be assumed to be implementation of Algorithms 5.3, 5.4]

Remove one element

Remove the element then print in loop