Pune Vidyarthi Griha’s

COLLEGE OF ENGINEERING, NASHIK – 3.

“QUEUE”
By
Prof. Anand N. Gharu
(Assistant Professor)
PVGCOE Computer Dept.

01 August 2019
.
 Introduction of Queue
➢ “A queue is an ordered list in which all insertions are
done at one end, called rear and deletions at another end
called front“

➢ Queue when implemented using arrays has some

drawbacks which can be avoided by circular queue
➢ Queue is used in many applications such as as simulation,

priority queue, job queue etc

 Introduction of Queue
➢ One of the most common data processing structures

➢ Frequently used in most of the system software's like

operating systems, Network and Database
implementations and in many more other areas

➢ Very useful in time-sharing and distributed computer

systems where many widely distributed users share the

system simultaneously
 Array representation and
implementation of queue
➢ An array representation of queue require three entities :

1. An array to hold queue element

2. A variable to hold index of the front element

3. A variable to hold index of the rear element

Array representation and
implementation of queue
Array representation and
implementation of queue
Array representation and
implementation of queue
 Operation on queue
implemented using array
 Operation on queue
implemented using array
 Operation on queue
implemented using array
 Operation on queue
implemented using array
 Operation on queue
implemented using array
 Queue as an ADT
➢ Create : Create creates an empty queue, Q

➢ Add (i,Q) : Add adds the element i to the rear end of queue,
Q and returns the new queue
➢ Delete (Q) : Delete takes out an element i from the

➢ front end of queue and returns the resulting queue

➢ Front(Q) : Front returns the element i which is at the front
position of queue
➢ Is_Empty_Q(Q) : Is_Empty_Q returns true if queue is

➢ empty otherwise returns false

Queue as an ADT
Queue as an ADT
Queue as an ADT
STACK VS QUEUE
Queue Example
Queue Example
Queue Example
Queue Example
Operation on queue implemented using
Linked list
Operation on queue implemented using
Linked list
Operation on queue implemented using
Linked list
Operation on queue implemented using
Linked list
Operation on queue implemented using
Linked list
Operation on queue implemented using
Linked list
Circular Queue
 Second Approach: Queue as a
Circular Array
• If we don't fix one end of the queue at
index 0, we won't have to shift elements
• Circular array is an array that conceptually
loops around on itself
o The last index is thought to “precede” index 0
o In an array whose last index is n, the location “before” index 0 is index n;
the location “after” index n is index 0

• Need to keep track of where the front as

well as the rear of the queue are at any
given time

6-29
 Conceptual Example of a Circular Queue
front
After 5
1 After 7 enqueues 1 dequeues
0 0
front
12 12
11 11
rear rear
10 10

rear
1
0
front
12
11
After 8 more enqueues
10
6-30
 Implementation of a
Queue

3 2 3
1 4
front queue 5
cq 0
8 5 n-1 6
rear count n-2 7
n-3 8
9
10
...
6-31
 A Queue Straddling the
End of a Circular Array
98 2 3
1 4
front queue 5
cq 0
2 4 99 6
rear count 98 7
97 8
9
10
...
6-32
 Circular Queue Drawn
Linearly Queue from previous slide

98
cq front queue
…
0 1 2 3 4 96 97 98 99
2 4
rear count

6-33
 Circular Array
Implementation
• When an element is enqueued, the value of rear is
incremented
• But it must take into account the need to loop back
to index 0:

rear = (rear+1) % queue.length;

• Can this array implementation also reach capacity?

6-34
 Example: array of length 4
What happens?
0 1 2 3
2
front queue
cq
Suppose we try to add one
1 3
more item to a queue
rear count implemented by an array of
length 4

0 1 2 3
2 The queue is now full. How
can you tell?
front queue
cq
2 4
rear count
6-35
 Need to expand
capacity…
0 1 2 3
We can’t just double the
2
size of the array and
front queue copy values to the same
cq
positions as before:
2 4
circular properties of the
rear count queue will be lost

0 1 2 3 4 5 6 7
2
front queue
cq
2 4
These locations
rear count should be in use
6-36
 We could build the new array, and copy the queue elements into
contiguous locations beginning at location front:

0 1 2 3 4 5 6 7
2
front queue
cq
6 4
rear count

6-37
 Better: copy the queue elements in order to the beginning of the
new array

0 1 2 3 4 5 6 7
0
front queue
cq
4 4
rear count

6-38
 New element is added at rear = (rear+1) % queue.length
See expandCapacity() in CircularArrayQueue.java

0 1 2 3 4 5 6 7
0
front queue
cq
5 5
rear count

6-39
Circular Queue
Circular Queue
Circular Queue
Circular Queue
Circular Queue
DeQueue
DeQueue
DeQueue as an ADT
Implementation of DeQueue using linked list
C function for deque using circular array
C function for deque using circular array
Priority Queue
Priority Queue as an ADT
Priority Queue as an ADT
Multiple Queue using array
Application of Queue