Transcript Chapter 1

Chapter 8
Queues
Data Structures Using C++
1
Chapter 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
Data Structures Using C++
2
Chapter Objectives
• Discover queue applications
• Examine the STL class queue
• Discover priority queues
Data Structures Using C++
3
Queues
• Definition: data structure in which the
elements are added at one end, called the
rear, and deleted from the other end, called
the front or first
• First In First Out (LIFO) data structure
Data Structures Using C++
4
Basic Operations on a Queue
• initializeQueue: Initializes the queue to an
empty state
• destroyQueue: Removes all the elements
from the queue, leaving the queue empty
• isEmptyQueue: Checks whether the queue
is empty. If the queue is empty, it returns the
value true; otherwise, it returns the value
false
Data Structures Using C++
5
Basic Operations on a queue
• isFullQueue: Checks whether the queue is
full. If the queue is full, it returns the value
true; otherwise, it returns the value false
• front: Returns the front (first) element of
the queue; the queue must exist
• back: Returns the front (first) element of
the queue; the queue must exist
Data Structures Using C++
6
Basic Operations on a queue
• addQueue: Adds a new element to the rear
of the queue; the queue must exist and must
not be full
• deleteQueue: Removes the front element of
the queue; the queue must exist and must
not be empty
Data Structures Using C++
7
Queues as Arrays
Data Structures Using C++
8
Queues as Arrays
Data Structures Using C++
9
Circle Queue
Data Structures Using C++
10
Queues as Arrays
Data Structures Using C++
11
Queues as Arrays
Data Structures Using C++
12
Queues as Arrays
Data Structures Using C++
13
Queues as Arrays
Data Structures Using C++
14
Queues as Arrays
Data Structures Using C++
15
Queues as Arrays
Data Structures Using C++
16
Queues as Arrays
Data Structures Using C++
17
UML Diagram of the
class queueType
Data Structures Using C++
18
Initialize Queue
Definition of the function initializeQueue:
template<class Type>
void queueType<Type>::initializeQueue()
{
queueFront = 0;
queueRear = maxQueueSize - 1;
count = 0;
}
Data Structures Using C++
19
Empty Queue and Full Queue
template<class Type>
bool queueType<Type>::isEmptyQueue()
{
return (count == 0);
}
template<class Type>
bool queueType<Type>::isFullQueue()
{
return (count == maxQueueSize);
}
Data Structures Using C++
20
Destroy Queue
template<class Type>
void queueType<Type>::destroyQueue()
{
queueFront = 0;
queueRear = maxQueueSize - 1;
count = 0;
}
Data Structures Using C++
21
front and back
template<class Type>
Type queueType<Type>::front()
{
assert(!isEmptyQueue());
return list[queueFront];
}
template<class Type>
Type queueType<Type>::back()
{
assert(!isEmptyQueue());
return list[queueRear];
}
Data Structures Using C++
22
Add Queue
template<class Type>
void queueType<Type>::addQueue(const Type& newElement)
{
if(!isFullQueue())
{
queueRear = (queueRear + 1) % maxQueueSize; //use the mod
//operator to advance queueRear
//because the array is circular
count++;
list[queueRear] = newElement;
}
else
cerr<<"Cannot add to a full queue."<<endl;
}
Data Structures Using C++
23
Delete Queue
template<class Type>
void queueType<Type>::deleteQueue()
{
if(!isEmptyQueue())
{
count--;
queueFront = (queueFront + 1) % maxQueueSize; //use the mod
//operator to advance queueFront
//because the array is circular
}
else
cerr<<"Cannot remove from an empty queue."<<endl;
}
Data Structures Using C++
24
Constructor and Destructor
• Constructor
– Creates an array of the size specified by the user
– Default value is 100
– Initializes queueFront queueRear to indicate that the queue is
empty
• Destructor
– When queue object goes out of scope, destructor reallocates
memory occupied by the array that stores the queue elements
Data Structures Using C++
25
Linked Queue as an ADT
Data Structures Using C++
26
Empty, Full, and Destroy Queue
• Queue is empty if queueFront is NULL
• Queue is full only if we run out of memory
• Destroy queue removes all elements of the queue
Data Structures Using C++
27
addQueue
• Adds a new element to the end of the queue
• Access the pointer queueRear to implement
addQueue
Data Structures Using C++
28
Front, Back, and Delete Queue
• If queue is nonempty:
– operation front returns the first element of the queue
– operation back returns the last element of the queue
– operation deleteQueue removes the first element of the queue
• If queue is empty:
– function front terminates the program
– function back terminates the program
Data Structures Using C++
29
STL class queue (Queue
Container Adapter)
Data Structures Using C++
30
Priority Queue
• FIFO rules of a queue are relaxed
• Customers or jobs with higher priority are
pushed to front of queue
• To implement:
– use an ordinary linked list, which keeps the
items in order from the highest to lowest
priority
– use a treelike structure
Data Structures Using C++
31
Application of Queues
Data Structures Using C++
32
Application of Queues
Data Structures Using C++
33
Application of Queues
Data Structures Using C++
34
Application of Queues:
waitingCustomerQueueType
Data Structures Using C++
35
Poisson Distribution
Data Structures Using C++
36
Chapter Summary
• Queue Data Structure
– Restricted Version of arrays and linked
list
– Basic operations
• First In First Out (FIFO)
• Queues Implemented as Arrays
Data Structures Using C++
37
Chapter Summary
•
•
•
•
Queues Implemented as Linked Lists
STL class queue
Priority Queues
Application of Queues
Data Structures Using C++
38