TMF1434

DATA STRUCTURE AND ALGORITHMS

Semester 2, 2017/2018
Instructor: Dr Mohammad B Hossin
hmohamma@unimas.my
+6082583728
2
LEC07
Queues
3 Acknowledgement
 The following slides were drawn or copied from your textbook

“Data Structures Using C++” by D. S. Malik

4 Learning Objectives

 Learn about queues

 Examine various queue operations
 Learn how to implement a queue as an array
 Learn how to implement a queue as a linked list
 Discover queue applications
 Become aware of the STL class queue
5 Real Life Example of Queues

 The first person to join a line is the first person to be served, or leave
the line
 New person is added to a queue at the back
 A person leaves a queue from the front
6 Queue Concept
 A queue is a data structure

 Elements are added at one end, called the rear (enqueue

operation) and elements are removed from other end,
called the front (dequeue operation)

 Middle elements of queues are inaccessible

 Queues are first-in, first-out (FIFO) structures

Elements may be added at any time, but only the
element which has been in the queue the longest may
be removed
7 Stack vs Queue
8 Basic Queue Operations

 Create an empty queue (initializeQueue)

 Destroy a queue
 Determine whether a queue is empty (isEmptyQueue)
 Determine whether a queue is full (isFullQueue)
 Add a new element to the rear of the queue (enqueue) (addQueue)
 Removes the front element from the queue (dequeue)
(deleteQueue)
 Returns the front, that is, the first element of the queue (front)
 Returns the last element of the queue (back)
9
Implementing a Queue as an Array
10 Implementation of Queue as Arrays
In applications where a fixed-sixe queue
does not present a problem, an array is a
simple solution

What are needed?

Array to store queue elements
Variable to represent the front (queueFront)
Variable to represent the back (queueRear)
Variable to specify the maximum size of the
queue (maxQueueSize)
11 Design Decision: Use of queueFront
and QueueRear
 How do queueFront and queueRear indicate that the queue is empty or full?

 Suppose
To summarise,
 queueFront gives the index of the first element of the
queue
 queueRear gives the index of the last element of the  queueFront changes
queue after each
deleteQueue
operation
 To add an element to the queue:
1. Advance queueRear to the next array position
2. Add the element to the position that queueRear is  queueRear changes
after each addQueue
pointing to operation

 To delete an element from the queue:

1. Retrieve the element that queueFront is pointing to
2. Advance queueFront to the next element of the
queue
12 Illustrating the idea
Initially, the queue is empty.

The queue after the operation:

addQueue(Queue,'A');

The queue after these operations:

addQueue(Queue,'B');
addQueue(Queue,'C');

The queue after the operation:

deleteQueue();
13 Problem with this Naïve
Implementation of Queues as Arrays
 Suppose
 A stands for adding an element to the queue (i.e., addQueue)
 D stands for deleting an element from the queue (i.e., deleteQueue)

 Consider the sequence of

operations:
AAADADADADADADADA...

 Eventually index queueRear points

to last array position

 Looks like a full queue (queueRear Queue after the sequence

= maxQueueSize-1) of operations
AAADADADADADA...
 Reality: queue has two or three
elements, array empty in the front
14 Solutions to the Problem
 SOLUTION 1 [0] [1] [2] [3] […] [19]

 Upon queue overflow to the rear C D …. X

 Check value of queueFront queueFront = 0 queueRear = 17
19
2
 If room in front: slide all queue elements
toward first array position
 Works if queue size very small

 SOLUTION 2: Assume that the array is circular

 Advance the queue index queueFront (to
delete an item)
 Advance the queue index queueRear (to
insert an item)

Circular queue
15 Implementation of Queues as Circular
Arrays (cont’d)
 To insert an item
 Advance the queue index queueRear
 queueRear = (queueRear + 1) % maxQueueSize;

queueRear = (99 + 1) % 100

= 0
17 Implementation of Queues as Circular
Arrays (cont’d)
 If queueRear < maxQueueSize – 1 //has empty space
 Then queueRear + 1 <= maxQueueSize – 1
 So (queueRear + 1) % maxQueueSize = queueRear + 1

 If queueRear == maxQueueSize – 1 //that is, queueRear

//points to the last array position
 Then queueRear + 1 == maxQueueSize
 So (queueRear + 1) % maxQueueSize = 0
In this case, queueRear is set to zero, which is the first array position
18 Problem: Detecting Empty Queue and
Full Queue Conditions
Figure (b) represents an empty queue

In the two
cases:
queueFront
and
Figure (b) represents a full queue queueRear
have same
values
19 Solution 1: Use variable count

 Keep a variable count to count the number of items in the queue

 Increment the value of count when new element added

 Decrement the value of count when element removed

 The functions initializeQueue and destroyQueue initialise count

to zero

 This solution is very useful if the user of the queue frequently needs to
know the number of elements in the queue
20 Solution 2
 Let queueFront indicates the index of array position preceding first
element of the queue
 Rather than the index of the (actual) first element itself
 Assume queueRear still indicates the index of last element
 Queue is empty if queueFront == queueRear

 Slot indicated by the index

queueFront is reserved
 Queue is full
 If next available space
represents special reserved slot

Array to store the queue elements

with a reserved slot
21 class queueADT

See code on pp. 459-460

It implements Solution 1 (using count)
 Implementing a Queue as a Linked
22
List
23 Problem with Implementation of
Queues as Arrays
Array has fixed size
 Finite number of queue elements

 Requires special array treatment with the values of

the indices queueFront, queueRear

 Queue never full

Queue expands or shrinks with each enqueue or
dequeue operation
24 Implementation of Queues as Linked
Lists
 One method is to maintain two external pointers
 One pointer to point to the front
 One pointer to point to the back

 Insertion at the back and deletion from the front are

straightforward when using two separate pointers
 Deleting from the front is simpler than insertion at the back
 (See code on pp. 464-465)
 Standard Template Library class
25
queue
26 STL class queue
 Provides a container class
queue to implement queues
in a program

 The choice of member names

is a bit confusing:
 queue
 Name of class defining the
queue
 Name of header defining
class queue
27
Priority Queues
28 Priority Queues
 Queue structure ensures items processed in the order received (FIFO)
 There are certain situations when FIFO rule needs to be relaxed
 e.g., in a hospital environment, patients are, usually, seen in the order they arrive. But
if a patient arrives with severe or life-threatening symptoms, she/he is treated first.

 Priority queues
 Customers (jobs) with higher priority pushed to the front of the queue
 Implementation
 Ordinary linked list
 Keeps items in order from the highest to lowest priority
 Treelike structure
 Very effective
 (To be studied during “Sorting Algorithms”)
29 STL class priority_queue

 class template priority_queue<elemType>

 Queue element data type specified by elemType
 Contained in the STL header file queue

 Specifying element priority

 Default priority criteria for the queue elements
 Less-than operator (<)

 Overloading the less-than operator (<)

 Compare the elements

 Defining a comparison function to specify the priority

30 Quick Review

1. What does FIFO mean?

2. When an element is removed from a
queue, where is it removed from?
3. When an element is added to a queue,
where is it added?
4. Describe two operations that all queues
perform.
31

Any
Question?