Fundamentals of Data Structures

[210242]

Prof. K. S. Patil
Professor
Dept. Of Computer Enginerring,
SKNSITS, Lonavala

Kspatil.sknsits@sinhgad.edu

1
Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala
 Unit-VI: QUEUE

Contents: Basic concept, stack Abstract Data Type, Representation of Stacks Using Sequential Organization,
stack operations, Multiple Stacks, Applications of Stack- Expression Evaluation and Conversion, Polish notation
and expression conversion, Need for prefix and postfix expressions, Postfix expression evaluation, Linked Stack
and Operations.
Recursion- concept, variants of recursion- direct, indirect, tail and tree, backtracking algorithmic strategy, use of
stack in backtracking.

Unit Objectives and outcomes: On completion the students will be able to:
1. Understand the queue
2. Understand the Recursion

Unit outcomes : On completion the students will be able to

1. Understand Basic concept queue.
2. Understand Recursion.

Outcome Mapping:
PEOs: POs: COs: PSOs:
Books used
•T1: Horowitz and Sahani, “Fundamentals of Data Structures in C++”, University Press, ISBN 10: 0716782928 ISBN
13: 9780716782926.
•T2: Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser, “Data Structures and
•Algorithms in Python”, Wiley Publication, ISBN: 978-1-118-29027-9.
Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala
 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

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 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

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 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

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Array representation and
implementation of queue

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Array representation and
implementation of queue

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Array representation and
implementation of queue

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Operation on queue
implementedusing array

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Operation on queue
implementedusing array

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Operation on queue
implemented using array

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Operation on queue
implementedusing array

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Operation on queue
implementedusing array

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 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

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Queue as an ADT

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Queue as an ADT

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Queue as an ADT

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

STACK VS QUEUE

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Queue Example

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Queue Example

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Queue Example

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Queue Example

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Operation on queue
implemente
d using
Linked list

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Operation on queue
implemente
d using
Linked list

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Operation on queue
implemente
d using
Linked list

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Operation on queue
implemente
d using
Linked list

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Operation on queue
implemente
d using
Linked list

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Operation on queue
implemente
d using
Linked list

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Circular Queue

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 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
Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala
 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
Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala
 Implementation of a
Queue

3 2 3
1 4
front queue 5
cq 0
8 5 n 6
rear count - 7
1
n-3
n 8
- 9
10

.
2

.
6-31
Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala
 A Queue Straddling
the End of a Circular
98
Array 2 3
1 4
front queue 5
cq 0
2 4 99 6
rear count 98 7
97 8
9
10

.
.
6-32
Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala
 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
Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala
 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
Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala
 Example: array of length 4
What happens?
0 1 2 3

cq front
queue 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
cq
2
queue 4
rear count
6-35
Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala
 Need to expand
capacity… 0 1 2 3
We can’t just double the
2
size of the array and copy
values to the same
cq front
queue 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
cq
2
queue 4
These locations should
rear count be in use
6-36
Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala
 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
Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala
 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
Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala
 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
Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala
 Circular Queue

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Circular Queue

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Circular Queue

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Circular Queue

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Circular Queue

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 DeQueue

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 DeQueue

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

DeQueue as an ADT

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Implementation of DeQueue using linked list

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

C function for deque using circular array

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

C function for deque using circular array

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

 Priority Queue

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Priority Queue as an ADT

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Priority Queue as an ADT

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Multiple Queue using array

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Application of Queue

Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala

Thank
You Prof. K. S. Patil. Department of Computer Engg, SKNSITS, Lonavala