Queues

1. Concepts of queue
2. Queue by array
3. Queue by circular array
4. Queue by linked list
5. Deques
6. Priority queue
7. Applications of queues

© Oxford University Press 2014. All rights reserved.

 1. Concept of queue
• Queue is a data structure which stores its elements in an
linearly ordered manner. Inserting element at one end
(rear) and deleting element from another end (front).
• A queue is a FIFO (First-In, First-Out) data structure in
which the element that is inserted first is the first one to
be taken out.
• The term queue comes from the analogy that people are
in queue waiting for services. First come, First served
(FCFS)
© Oxford University Press 2014. All rights reserved.
 Queue operations
• Inserting element --- enqueue
• Deleting element --- dequeue
• Need know the positions of rare and front for efficient
operations

Queue implementations
• using an array
• using a linked list

© Oxford University Press 2014. All rights reserved.

Queue operations

© Oxford University Press 2014. All rights reserved.

Queue operations

© Oxford University Press 2014. All rights reserved.

2. Array Representation of Queues

© Oxford University Press 2014. All rights reserved.

 2. Array Representation of Queues
• Queues can be easily represented using arrays.
• Every queue has front and rear variables that point to the position
from where deletions and insertions can be done, respectively.
• Consider the queue shown in figure
12 9 7 18 14 36 REAR
FRONT
0 1 2 3 4 5 6 7 8 9

• Here, front = 0 and rear = 5.

• If we want to add one more value in the list say with value 45, then
rear would be incremented by 1 and the value would be stored at
the position pointed by rear.

12 9 7 18 14 36 45
FRONT REAR
0 1 2 3 4 5 6 7 8 9

© Oxford University Press 2014. All rights reserved.

 Array Representation of Queues
• Now, front = 0 and rear = 6. Every time a new element has to be
added, we will repeat the same procedure.

• Now, if we want to delete an element from the queue, then the

value of front will be incremented. Deletions are done from only
this end of the queue.

9 7 18 14 36 45
FRONT REAR
0 1 2 3 4 5 6 7 8 9

• Now, front = 1 and rear = 6.

© Oxford University Press 2014. All rights reserved.

 Array Representation of Queues
• Before inserting an element in the queue we must check for
overflow conditions.
• An overflow occurs when we try to insert an element into a queue
that is already full, i.e. when rear = MAX – 1, where MAX specifies
the maximum number of elements that the queue can hold.
• Similarly, before deleting an element from the queue, we must
check for underflow condition.
• An underflow occurs when we try to delete an element from a
queue that is already empty. If front = -1 and rear = -1, this means
there is no element in the queue.

© Oxford University Press 2014. All rights reserved.

Algorithm for Insertion Operation
Algorithm to insert an element in a queue
Step 1: IF REAR=MAX-1, then;
Write OVERFLOW
Goto Step 4
[END OF IF]
Step 2: IF FRONT == -1 and REAR = -1, then
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = NUM
Step 4: Exit

Time complexity: O(1)

© Oxford University Press 2014. All rights reserved.

Algorithm for Deletion Operation
Algorithm to delete an element from a queue
Step 1: IF FRONT = -1 OR FRONT > REAR, then
Write UNDERFLOW
Goto Step 2
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1
[END OF IF]
Step 2: Exit

Time complexity: O(1)

© Oxford University Press 2014. All rights reserved.

© Oxford University Press 2013. All rights
reserved.
© Oxford University Press 2013. All rights
reserved.
© Oxford University Press 2013. All rights
reserved.
 4. Circular Queues
7 18 14 36 45 21 99 72

0 1 2 3 4 5 6 7 8 9

• We will explain the concept of circular queues using an example.

• In this queue, front = 2 and rear = 9.
• Now, if you want to insert a new element, it cannot be done
because the space is available only at the left of the queue.
• If rear = MAX – 1, then OVERFLOW condition exists.
• This is the major drawback of an array queue. Even if space is
available, no insertions can be done once rear is equal to MAX – 1.
• This leads to wastage of space. In order to overcome this problem,
we use circular queues.
• In a circular queue, the first index comes right after the last index.
• A circular queue is full, only when front=0 and rear = Max – 1.
© Oxford University Press 2014. All rights reserved.
Example: Consider the following circular queue with N = 5.
1. Initially, Rear = 0, Front = 0. 4. Insert 20, Rear = 3, Front =1.
Front

Rear

2. Insert 10, Rear = 1, Front = 1. 5. Insert 70, Rear = 4, Front = 1.

Rear Front
Front

Rear
3. Insert 50, Rear = 2, Front = 1. 6. Delete front, Rear = 4, Front = 2.
Front Rear Front

Rear

09/10/08 17
7. Insert 100, Rear = 5, Front = 2. 10. Delete front, Rear = 1, Front = 3.
Front Rear

Front

Rear

8. Insert 40, Rear = 1, Front = 2. 11. Delete front, Rear = 1, Front = 4.

Rear
Rear Front

Front

9. Insert 140, Rear = 1, Front = 2. 12. Delete front, Rear = 1, Front = 5.

As Front = Rear + 1, so Queue overflow. Rear

Rear Front

Front

09/10/08 18
Inserting an Element in a Circular Queue
• For insertion we check for three conditions which are as follows:
▪ If front=0 and rear= MAX – 1, then the circular queue is full.
90 49 7 18 14 36 45 21 99 72

front=0 1 2 3 4 5 6 7 8 rear = 9

▪ If rear != MAX – 1, then the rear will be incremented and value will
be inserted
90 49 7 18 14 36 45 21 99

front=0 1 2 3 4 5 6 7 rear= 8 9

• If front!=0 and rear=MAX -1, then it means that the queue is

not full. So, set rear = 0 and insert the new element.

49 7 18 14 36 45 21 99 72

front=1 2 3 4 5 6 7 8 rear= 9

© Oxford University Press 2014. All rights reserved.

Inserting an Element in a Circular Queue

• rear = front -1 overflow

9 10 7 18 14 36 45 21 99 72

rear=1 front=2 3 4 5 6 7 8 9

© Oxford University Press 2014. All rights reserved.

Algorithm to Insert an Element in a Circular Queue

Step 1: IF FRONT=0 and REAR=MAX–1, or REAR = FRONT – 1 then

Write “OVERFLOW”
Goto Step 4
[END OF IF]

Step 2: IF FRONT = -1 and REAR = -1, then;

SET FRONT = REAR = 0
ELSE IF REAR = MAX – 1 and FRONT != 0
SET REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Step 4: Exit

© Oxford University Press 2014. All rights reserved.

 Deleting an Element from a Circular Queue
• To delete an element again we will check for three conditions:
▪ If front = -1, then it means there are no elements in the queue. So
an underflow condition will be reported.

0 1 2 3 4 5 6 7 8 9

▪ If the queue is not empty and after returning the value on front, if
front = rear, then it means now the queue has become empty and
so front and rear are set to -1.
Delete this element and set
81 rear = front = -1

0 1 2 3 4 5 6 7 8 front=rear= 9

▪ If the queue is not empty and after returning the value on front, if
front = MAX -1, then front is set to 0.
72 63 9 18 27 39 81

0 1 2 3 4 rear= 5 6 7 8 front= 9

© Oxford University Press 2014. All rights reserved.

© Oxford University Press 2014. All rights reserved.
Algorithm to Delete an Element from a Circular Queue
Step 1: IF FRONT = -1, then
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

© Oxford University Press 2014. All rights reserved.

 4. Queue by Linked List
• Using a singly linked list to hold queue elements,
Using FRONT pointer pointing the start element,
Using REAR pointer pointing to the last element.

• Insertions is done at the rear end using REAR pointer

Deletions is done at the front end using FRONT pointer

• If FRONT = REAR = NULL, then the queue is empty.

1 7 3 4 2 6 5 X

FRONT REAR

© Oxford University Press 2014. All rights reserved.

Inserting an Element in a Linked Queue
Algorithm to insert an element in a linked queue

Step 1: Allocate memory for the new node and

name the pointer as PTR
Step 2: SET PTR->DATA = VAL
Step 3: IF FRONT = NULL, then
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]
Step 4: END

Time complexity: O(1)

© Oxford University Press 2014. All rights reserved.

Deleting an Element from a Linked Queue

Algorithm to delete an element from a

linked queue

Step 1: IF FRONT = NULL, then

Write “Underflow”
Go to Step 5
[END OF IF]
Step 2: SET PTR = FRONT
Step 3: FRONT = FRONT->NEXT
Step 4: FREE PTR
Step 5: END

Time complexity: O(1)

© Oxford University Press 2014. All rights reserved.
 5. Deques
• A deque (double-ended queue) is a list in which
elements can be inserted or deleted at either end.
• Also known as a head-tail linked list because elements
can be added to or removed from the front (head) or
back (tail).
• A deque can be implemented either using a circular array
or a circular doubly linked list.
• In a deque, two pointers are maintained, LEFT and RIGHT
which point to either end of the deque.

© Oxford University Press 2014. All rights reserved.

 Deque variants
• There are two variants of deques:
– Input restricted deque: In this dequeue insertions can be
done only at one of the ends while deletions can be done
from both the ends.
– Output restricted deque: In this dequeue deletions can be
done only at one of the ends while insertions can be done
on both the ends.

29 37 45 54 63

0 1 2 LEFT = 3 4 5 6 RIGHT = 7 8 9

63 27 18
42

RIGHT = 0 1 2 3 4 5 6 LEFT = 7 8 9

© Oxford University Press 2014. All rights reserved.

© Oxford University Press 2013. All rights
reserved.
© Oxford University Press 2013. All rights
reserved.
© Oxford University Press 2013. All rights
reserved.
© Oxford University Press 2013. All rights
reserved.
 6. Priority Queues
• A priority queue is a queue in which each element is assigned a
priority.
• The priority of elements is used to determine the order in which
these elements will be processed.
• The general rule of processing elements of a priority queue can be
given as:
o An element with higher priority is processed before an element
with lower priority
o Two elements with same priority are processed on a first come
first served (FCFS) basis
• Priority queues are widely used in operating systems to execute the
highest priority process first.
• In computer’s memory priority queues can be represented using
arrays or linked lists.
© Oxford University Press 2014. All rights reserved.
 6. Priority Queues
Types of Priority Queue
1. Limited Set of Priorities
2. Element Priority

2.Limited Set Priority

Priorities =3
Elements 🡪 A B C D E F G H I J
Priorities 🡪 1 1 2 3 2 1 2 2 2 3
Priority Queues
P1

P2

P3
© Oxford University Press 2014. All rights reserved.
Linked List Representation of Priority Queues

• When a priority queue is implemented using a linked list, then

every node of the list contains three parts: (1) the information or
data part, (ii) the priority number of the element, (iii) and address
of the next element.
• If we are using a sorted linked list, then element having higher
priority will precede the element with lower priority.

A 1 B 2 C 3 D 3 E 4 X

Priority queue after insertion of a new node (F, 4)

A 1 B 2 C 3 D 3 E 4 F 4 X

© Oxford University Press 2014. All rights reserved.

Array Representation of Priority Queues
• When arrays are used to implement a priority queue, then a
separate queue for each priority number is maintained.
• Each of these queues will be implemented using circular arrays
or circular queues. Every individual queue will have its own
FRONT and REAR pointers.
• We can use a two-dimensional array for this purpose where each
queue will be allocated same amount of space.
• Given the front and rear values of each queue, a two
dimensional matrix can be formed.

© Oxford University Press 2014. All rights reserved.

 7. Applications of Queues
1. Queues are widely used as waiting lists for a single
shared resource like printer, disk, CPU.
2. Queues are used to transfer data asynchronously
e.g., pipes, file IO, sockets.
3. Queues are used as buffers on MP3 players and
portable CD players, iPod playlist.

© Oxford University Press 2014. All rights reserved.

 7. Applications of Queues
5. Queues are used in Playlist for jukebox to add songs to the
end, play from the front of the list.

6. Queues are used in OS for handling interrupts. When

programming a real-time system that can be interrupted,
for eg, by a mouse click, it is necessary to process the
interrupts immediately before proceeding with the current
job. If the interrupts have to be handled in the order of
arrival, then a FIFO queue is the appropriate data structure

© Oxford University Press 2014. All rights reserved.

 Josephus Problem
In Josephus problem, n people stand in a circle waiting to be
executed. The counting starts at some point in the circle and
proceeds in a specific direction around the circle. In each step,
a certain number of people are skipped and the next person is
executed (or eliminated). The elimination of people makes the
circle smaller and smaller. At the last step, only one person
remains who is declared the ‘winner’.

© Oxford University Press 2014. All rights reserved.