Transcript Fundamentals of Python: From First Programs Through Data

Fundamentals of Python:
From First Programs Through Data
Structures
Chapter 15
Linear Collections: Queues
Objectives
After completing this chapter, you will be able to:
• Describe the behavior of a queue from a user’s
perspective
• Explain how a queue can be used to support a
simulation
• Describe the use of a queue in scheduling
processes for computational resources
Fundamentals of Python: From First Programs Through Data Structures
2
Objectives (continued)
• Explain the difference between a queue and a
priority queue
• Describe a case where a queue would be used
rather than a priority queue
• Analyze the performance trade-offs between an
array-based implementation of a queue and a
linked implementation of a queue
Fundamentals of Python: From First Programs Through Data Structures
3
Overview of Queues
Fundamentals of Python: From First Programs Through Data Structures
4
Overview of Queues (continued)
•
•
•
•
•
Insertions are restricted to one end (rear)
Removals are restricted to one end (front)
Queues supports a first-in first-out (FIFO) protocol
Fundamental operations: enqueue and dequeue
Item dequeued, or served next, is always the item
that has been waiting the longest
• Priority queue: Higher-priority items are dequeued
first; equal priority items dequeued in FIFO order
• Most queues in CS involve scheduling access to
shared resources: CPU/Disk/Printer access
Fundamentals of Python: From First Programs Through Data Structures
5
The Queue Interface and Its Use
• You can use a Python list to emulate a queue
– Use append to add an element to rear of queue
– Use pop to remove an element from front of queue
– Drawback: Queue can be manipulated by all of the
other list operations as well
• Violate spirit of queue as ADT
• We define a more restricted interface, or set of
operations, for any queue implementation and
show how these operations are used
Fundamentals of Python: From First Programs Through Data Structures
6
The Queue Interface and Its Use
(continued)
Fundamentals of Python: From First Programs Through Data Structures
7
The Queue Interface and Its Use
(continued)
• Assume that any queue class that implements this
interface will also have a constructor that allows its
user to create a new queue instance
• Later, we’ll consider two different implementations:
– ArrayQueue and LinkedQueue
q1 = ArrayQueue()
q2 = LinkedQueue()
Fundamentals of Python: From First Programs Through Data Structures
8
Two Applications of Queues
• We now look briefly at two applications of queues:
– One involving computer simulations
– The other involving round-robin CPU scheduling
Fundamentals of Python: From First Programs Through Data Structures
9
Simulations
• Computer simulations are used to study behavior of
real-world systems, especially if it is impractical or
dangerous to experiment with these systems directly
– Example: Mimic traffic flow on a busy highway
• Another example: Manager of supermarket wants to
determine number of checkout cashiers to schedule
at various times of the day and must consider:
–
–
–
–
Frequency with which new customers arrive
Number of checkout cashiers available
Number of items in a customer’s shopping cart
Period of time considered
Fundamentals of Python: From First Programs Through Data Structures
10
Simulations (continued)
• Simulations avoid need for formulas by imitating
actual situation and collecting pertinent statistics
• Simple technique to mimic variability:
– Suppose new customers are expected to arrive on
average once every four minutes
– During each minute of simulated time, a program
can generate a random number between 0 and 1
– If number is less than 1/4, program adds a new
customer to a checkout line; otherwise, it does not
• Probability distribution functions produce more
realistic results
Fundamentals of Python: From First Programs Through Data Structures
11
Simulations (continued)
• Examples presented involve service providers and
service consumers
– We associate each service provider with a queue of
service consumers
• Simulations operate by manipulating these queues
– At each tick of an imaginary clock, add consumer(s)
to the queues and give consumers at the head of
each queue another unit of service
• OO methods can be used to implement simulations
Fundamentals of Python: From First Programs Through Data Structures
12
Simulations (continued)
• Example: Supermarket simulation
– A Customer object keeps track of when the
customer starts standing in line, when service is first
received, and how much service is required
– A Cashier object has a queue of customer objects
– A simulator object coordinates customer/cashier
activities by doing the following at each clock tick:
• Generates new customer objects as appropriate
• Assigns customers to cashiers
• Tells each cashier to provide one unit of service to the
customer at the head of the queue
Fundamentals of Python: From First Programs Through Data Structures
13
Round-Robin CPU Scheduling
• Each process on the ready queue is dequeued in
turn and given a slice of CPU time
• Improvement: Can use a priority queue
Fundamentals of Python: From First Programs Through Data Structures
14
Implementations of Queues
• Our approach to the implementation of queues is
similar to the one we used for stacks
• The structure of a queue lends itself to either an
array implementation or a linked implementation
– The linked implementation is somewhat more
straight-forward
Fundamentals of Python: From First Programs Through Data Structures
15
A Linked Implementation
• enqueue adds a node at the end
– For fast access to both ends of a queue’s linked
structure, provide external pointers to both ends
• Instance variables front and rear of
LinkedQueue are given an initial value of None
• size tracks number of elements currently in queue
Fundamentals of Python: From First Programs Through Data Structures
16
A Linked Implementation (continued)
Fundamentals of Python: From First Programs Through Data Structures
17
An Array Implementation
• Array implementations of stacks and queues have
less in common than the linked implementations
• Array implementation of a queue must access
items at the logical beginning and the logical end
– Doing this in computationally effective manner is
complex
– We approach problem in a sequence of three
attempts
Fundamentals of Python: From First Programs Through Data Structures
18
A First Attempt
• Fixes front of queue at position 0
• rear variable points to last item at position n – 1
– n is the number of items in queue
• Analysis:
– enqueue is efficient
– dequeue entails shifting all but first item  O(n)
Fundamentals of Python: From First Programs Through Data Structures
19
A Second Attempt
• Maintain a second index (front) that points to
item at front of queue
– Starts at 0 and advances as items are dequeued
• Analysis:
– dequeue is O(1)
– Maximum running time of enqueue is O(n)
Fundamentals of Python: From First Programs Through Data Structures
20
A Third Attempt
• Use a circular array implementation
– rear starts at –1; front starts at 0
– front chases rear pointer through the array
– When a pointer is about to run off the end of the
array, it is reset to 0
• Running times of enqueue and dequeue are O(1)
Fundamentals of Python: From First Programs Through Data Structures
21
A Third Attempt (continued)
• What happens when the queue becomes full?
– Maintain a count of the items in the queue
– When this count equals the size of the array: Resize
– After resizing, we would like queue to occupy initial
segment of array, with front pointer set to 0
• If front pointer is less than rear pointer
– Copy positions 0 through size-1 in new array
• If rear pointer is less than front pointer
– Copy positions 0 through size-front and size
– front + 1 through size-1 in new array
– Resizing process is linear
Fundamentals of Python: From First Programs Through Data Structures
22
Time and Space Analysis for the Two
Implementations
• Linked implementation:
– Running time: __str__ is O(n); all other are O(1)
– Space requirement: 2n + 3, n: size of queue
• Circular array implementation:
– Static array: Maximum running time of all methods
other than __str__ is O(1)
– Dynamic array: enqueue/dequeue are O(n) when
array is resized, but are O(1) on average
– Space utilization: For load factors above 1⁄2, array
implementation makes more efficient use of memory
than a linked implementation
Fundamentals of Python: From First Programs Through Data Structures
23
Case Study: Simulating a Supermarket
Checkout Line
• Request:
– Write program that allows user to predict behavior of
supermarket checkout line under various conditions
• Analysis:
Fundamentals of Python: From First Programs Through Data Structures
24
Case Study: Simulating a Supermarket
Checkout Line (continued)
• The Interface:
• Classes and responsibilities:
– We divide the system into a main function and
several model classes
Fundamentals of Python: From First Programs Through Data Structures
25
Case Study: Simulating a Supermarket
Checkout Line (continued)
Fundamentals of Python: From First Programs Through Data Structures
26
Case Study: Simulating a Supermarket
Checkout Line (continued)
Fundamentals of Python: From First Programs Through Data Structures
27
Case Study: Simulating a Supermarket
Checkout Line (continued)
Fundamentals of Python: From First Programs Through Data Structures
28
Priority Queues
• A priority queue is a specialized type of queue
– Items added to queue are assigned an order of rank
– Items of higher priority are removed before those of
lower priority
– Items of equal priority are removed in FIFO order
– Item A has a higher priority than item B if A < B
– Objects that recognize the comparison operators
can be ordered in priority queues
• If not, object can be wrapped with a priority number in
another object that does recognize these operators
Fundamentals of Python: From First Programs Through Data Structures
29
Priority Queues (continued)
Fundamentals of Python: From First Programs Through Data Structures
30
Priority Queues (continued)
• Wrapper class used to build a comparable item
from one that is not already comparable:
Fundamentals of Python: From First Programs Through Data Structures
31
Priority Queues (continued)
• During insertions, a priority queue does not know
whether it is comparing items in wrappers or just
items
• When a wrapped item is accessed (e.g., with peek
or dequeue), it must be unwrapped with the
method getItem before processing
• Two implementations: Sorted linked list or heap
Fundamentals of Python: From First Programs Through Data Structures
32
Priority Queues (continued)
Search is linear, so
enqueue is now
O(n)
Fundamentals of Python: From First Programs Through Data Structures
33
Case Study: An Emergency Room
Scheduler
• Request:
– Write a program that allows a supervisor to schedule
treatments for patients coming into emergency room
– Patients are assigned a priority when admitted
• Higher priority patients receive attention first
• Analysis:
– Patient priorities: critical, serious, and fair
Fundamentals of Python: From First Programs Through Data Structures
34
Case Study: An Emergency Room
Scheduler (continued)
Fundamentals of Python: From First Programs Through Data Structures
35
Case Study: An Emergency Room
Scheduler (continued)
Fundamentals of Python: From First Programs Through Data Structures
36
Case Study: An Emergency Room
Scheduler (continued)
• Classes:
• Design and Implementation:
– Patient and Condition classes maintain a
patient’s name and condition
– Patients can be compared (according to their
conditions) and viewed as strings
Fundamentals of Python: From First Programs Through Data Structures
37
Case Study: An Emergency Room
Scheduler (continued)
Fundamentals of Python: From First Programs Through Data Structures
38
Summary
• A queue is a linear collection that adds elements to
the “rear” and removes them from the “front”
• Queues are used in applications that manage data
items in a first-in, first-out order (FIFO)
– Example: Scheduling items for processing or access
to resources
• Arrays and singly linked structures support simple
implementations of queues
• Priority queues schedule their elements using a
rating scheme as well as a FIFO order
Fundamentals of Python: From First Programs Through Data Structures
39