Transcript Chapter 18-3

C++ Programming:
Program Design Including
Data Structures, Fourth Edition
Chapter 18: Stacks and Queues
(part 3)
Queues
• Queue: list of homogeneous elements
• Elements are:
− Added at one end (the back or rear)
− Deleted from the other end (the front)
• First In First Out (FIFO) data structure
− Middle elements are inaccessible
• Example:
− Waiting line in a bank
C++ Programming: Program Design Including Data Structures, Fourth Edition
2
Queue Operations
• Some of the queue operations are:
− initializeQueue
− isEmptyQueue
− isFullQueue
− front
− back
− addQueue
− deleteQueue
• Abstract class queueADT defines these
operations
C++ Programming: Program Design Including Data Structures, Fourth Edition
3
Implementation of Queues as
Arrays
• You need at least four (member) variables:
− An array to store the queue elements
− queueFront and queueRear
• To keep track of first and last elements
− maxQueueSize
• To specify the maximum size of the queue
C++ Programming: Program Design Including Data Structures, Fourth Edition
6
Implementation of Queues as
Arrays (continued)
• To add an element to the queue:
− Advance queueRear to next array position
− Add element to position pointed by queueRear
• Example: array size is 100; originally empty
C++ Programming: Program Design Including Data Structures, Fourth Edition
7
Implementation of Queues as
Arrays (continued)
• To delete an element from the queue:
− Retrieve element pointed to by queueFront
− Advance queueFront to next queue element
C++ Programming: Program Design Including Data Structures, Fourth Edition
8
Implementation of Queues as
Arrays (continued)
• Will this queue design work?
− Suppose A stands for adding an element to
the queue
− And D stands for deleting an element from the
queue
− Consider the following sequence of
operations:
• AAADADADADADADADA...
C++ Programming: Program Design Including Data Structures, Fourth Edition
9
Implementation of Queues as
Arrays (continued)
• The sequence AAADADADADADADADA...
would eventually set queueRear to point to
the last array position
− Giving the impression that the queue is full
C++ Programming: Program Design Including Data Structures, Fourth Edition
10
Implementation of Queues as
Arrays (continued)
• Solution 1:
− When the queue overflows to the rear (i.e.,
queueRear points to the last array position):
• Check value of queueFront
• If value of queueFront indicates that there is
room in the front of the array, slide all of the
queue elements toward the first array position
• Problem: too slow for large queues
• Solution 2: assume that the array is circular
C++ Programming: Program Design Including Data Structures, Fourth Edition
11
Implementation of Queues as
Arrays (continued)
• To advance the index in a (logically) circular
array:
C++ Programming: Program Design Including Data Structures, Fourth Edition
12
Implementation of Queues as
Arrays (continued)
C++ Programming: Program Design Including Data Structures, Fourth Edition
13
Implementation of Queues as
Arrays (continued)
• Case 1:
C++ Programming: Program Design Including Data Structures, Fourth Edition
14
Implementation of Queues as
Arrays (continued)
• Case 2:
C++ Programming: Program Design Including Data Structures, Fourth Edition
15
Implementation of Queues as
Arrays (continued)
• Problem:
− Figures 18-47 and 18-49 have identical values
for queueFront and queueRear
− However, the former represents an empty
queue, whereas the latter shows a full queue
• Solution?
C++ Programming: Program Design Including Data Structures, Fourth Edition
16
Implementation of Queues as
Arrays (continued)
• Solution 1: keep a count
− Incremented when a new element is added to
the queue
− Decremented when an element is removed
− Initially, set to 0
− Very useful if user (of queue) frequently needs
to know the number of elements in the queue
• We will implement this solution
C++ Programming: Program Design Including Data Structures, Fourth Edition
17
Implementation of Queues as
Arrays (continued)
• Solution 2: let queueFront indicate index of
the array position preceding the first element
− queueRear still indicates index of last one
− Queue empty if:
• queueFront == queueRear
− Slot indicated by queueFront is reserved
• Queue can hold 99 (not 100) elements
− Queue full if the next available space is the
reserved slot indicated by queueFront
C++ Programming: Program Design Including Data Structures, Fourth Edition
18
Implementation of Queues as
Arrays (continued)
C++ Programming: Program Design Including Data Structures, Fourth Edition
19
Empty Queue and Full Queue
C++ Programming: Program Design Including Data Structures, Fourth Edition
22
Initialize Queue
C++ Programming: Program Design Including Data Structures, Fourth Edition
23
Front
• Returns the first element of the queue
C++ Programming: Program Design Including Data Structures, Fourth Edition
24
Back
• Returns the last element of the queue
C++ Programming: Program Design Including Data Structures, Fourth Edition
25
addQueue
C++ Programming: Program Design Including Data Structures, Fourth Edition
26
deleteQueue
C++ Programming: Program Design Including Data Structures, Fourth Edition
27
Constructors and Destructors
C++ Programming: Program Design Including Data Structures, Fourth Edition
28
Constructors and Destructors
(continued)
• The array to store the queue elements is
created dynamically
− When the queue object goes out of scope, the
destructor simply deallocates the memory
occupied by the array
C++ Programming: Program Design Including Data Structures, Fourth Edition
29
Linked Implementation of Queues
• Array size is fixed: only a finite number of
queue elements can be stored in it
• The array implementation of the queue
requires array to be treated in a special way
− Together with queueFront and queueRear
• The linked implementation of a queue
simplifies many of the special cases of the
array implementation
− In addition, the queue is never full
C++ Programming: Program Design Including Data Structures, Fourth Edition
30
Linked Implementation of Queues
(continued)
• Elements are added at one end and removed
from the other
− We need to know the front of the queue and
the rear of the queue
• Two pointers: queueFront and queueRear
C++ Programming: Program Design Including Data Structures, Fourth Edition
31
Empty and Full Queue
• The queue is empty if queueFront is NULL
• The queue is never full
C++ Programming: Program Design Including Data Structures, Fourth Edition
34
Initialize Queue
• Initializes queue to an empty state
− Must remove all the elements, if any
C++ Programming: Program Design Including Data Structures, Fourth Edition
35
addQueue
C++ Programming: Program Design Including Data Structures, Fourth Edition
36
front and back Operations
C++ Programming: Program Design Including Data Structures, Fourth Edition
37
deleteQueue
C++ Programming: Program Design Including Data Structures, Fourth Edition
38
Default Constructor
C++ Programming: Program Design Including Data Structures, Fourth Edition
39
Queue Derived from the class
unorderedLinkedListType
• The linked implementation of a queue is
similar to the implementation of a linked list
created in a forward manner
− addQueue is similar to insertFirst
− initializeQueue is like initializeList
− isEmptyQueue is similar to isEmptyList
− deleteQueue can be implemented as before
− queueFront is the same as first
− queueRear is the same as last
C++ Programming: Program Design Including Data Structures, Fourth Edition
41
Queue Derived from unordered
LinkedListType (continued)
• We can derive the class to implement the
queue from linkedListType
− Abstract class: does not implement all the
operations
• However, unorderedLinkedListType is
derived from linkedListType
− Provides the definitions of the abstract
functions of the linkedListType
− Therefore, we can derive linkedQueueType
from unorderedLinkedListType
C++ Programming: Program Design Including Data Structures, Fourth Edition
42
Application of Queues: Simulation
• Simulation: a technique in which one system
models the behavior of another system
• Computer simulations using queues as the
data structure are called queuing systems
C++ Programming: Program Design Including Data Structures, Fourth Edition
43
Designing a Queuing System
• Server: the object that provides the service
• Customer: the object receiving the service
• Transaction time: service time, or the time it
takes to serve a customer
• Model: system that consists of a list of
servers and a waiting queue holding the
customers to be served
− Customer at front of queue waits for the
next available server
C++ Programming: Program Design Including Data Structures, Fourth Edition
44
Designing a Queuing System
(continued)
• We need to know:
− Number of servers
− Expected arrival time of a customer
− Time between the arrivals of customers
− Number of events affecting the system
• Performance of system depends on:
− How many servers are available
− How long it takes to serve a customer
− How often a customer arrives
C++ Programming: Program Design Including Data Structures, Fourth Edition
45
Designing a Queuing System
(continued)
• If it takes too long to serve a customer and
customers arrive frequently, then more
servers are needed
• System can be modeled as a time-driven
simulation
• Time-driven simulation: the clock is a counter
− The passage of, say, one minute can be
implemented by incrementing the counter by 1
− Simulation is run for a fixed amount of time
C++ Programming: Program Design Including Data Structures, Fourth Edition
46
Customer
C++ Programming: Program Design Including Data Structures, Fourth Edition
47
Server
C++ Programming: Program Design Including Data Structures, Fourth Edition
48
Server List
• A server list is a set of servers
− At a given time, a server is either free or busy
C++ Programming: Program Design Including Data Structures, Fourth Edition
49
Waiting Customers Queue
• When a customer arrives, he/she goes to the
end of the queue
• When a server becomes available, the
customer at front of queue leaves to conduct
the transaction
• After each time unit, the waiting time of each
customer in the queue is incremented by 1
• We can use queueType but must add the
operation of incrementing the waiting time
C++ Programming: Program Design Including Data Structures, Fourth Edition
50
Waiting Customers Queue
(continued)
C++ Programming: Program Design Including Data Structures, Fourth Edition
51
Main Program
• Algorithm:
− Declare and initialize the variables
− Main loop (see next slide)
− Print results
C++ Programming: Program Design Including Data Structures, Fourth Edition
52
Main Program (continued)
C++ Programming: Program Design Including Data Structures, Fourth Edition
53
Summary
• Stack: items are added/deleted from one end
− Last In First Out (LIFO) data structure
− Operations: push, pop, initialize, destroy,
check for empty/full stack
− Can be implemented as array or linked list
− Middle elements should not be accessed
• Postfix notation: operators are written after
the operands (no parentheses needed)
C++ Programming: Program Design Including Data Structures, Fourth Edition
54
Summary (continued)
• Queue: items are added at one end and
removed from the other end
− First In First Out (FIFO) data structure
− Operations: add, remove, initialize, destroy,
check if queue is empty/full
− Can be implemented as array or linked list
− Middle elements should not be accessed
− Restricted versions of arrays and linked lists
C++ Programming: Program Design Including Data Structures, Fourth Edition
55