Class Notes (834,818)
Canada (508,737)
CS 234 (31)
Lecture

notes11a.pdf

4 Pages
52 Views
Unlock Document

Department
Computer Science
Course
CS 234
Professor
Robert Sproule
Semester
Summer

Description
June 11, 2013 Last Class  We covered: o Stacks – LIFO o Queues – FIFO Queue  Linear collection of items  FIFO protocol: First In First Out o Items are removed from the queue (i.e. dequeue) from the front, and items are entered into the queue (i.e. enqueue) from the back Priority Queue  Some applications require the use of a queue in which items are assigned a priority, p >= 0 o Higher priority items are dequeued first o Items with equal priority still follow the FIFO protocol, and are dequeued in the order they were entered Example: Printer queue Back of Queue pdf | 9 txt | 3 jpg | 3 docx | 5 Front of Queue  Calling dequeue will search the queue for the highest priority and remove the first instance of that item. In this example, dequeue will remove the pdf with priority 9 Two Types (of Priority Queues): 1. Bounded – limited range of priorities a. 0 <= p <= m, such that m > 0 2. Unbounded – unlimited range of priorities a. No bounds on p ADT Priority Queue  Data: linear collection of items  Operations: o PriorityQueue() – create an empty, unbounded priority queue o BPriorityQueue(maxLevels) – create an empty priority queue where items have priorities less than maxLevels o isEmpty() – returns True if the queue is empty and False otherwise o length() – returns the number of items in queue o enqueue(item, priority) – add item to queue o dequeue() – returns and removes the highest priority item June 11, 2013 Using the Priority Queue Python code L = [10, 12, 4, 1, 9, 13] PQ = PriorityQueue() for x in L: PQ.enqueue(x, x) pos = 0 while not PQ.isEmpty(): L[pos] = PQ.dequeue() pos += 1 Analysis of the above code PQ at the end of the “for” loop: Back of Queue 13 | 13 9 | 9 1 | 1 4 | 4 12 | 12 10 | 10 Front of Queue L after the “while” loop: L = [13, 12, 10, 9, 4, 1] Priority Queue Implementation Unbounded Priority Queue Two approaches:  Python List  Linked Lists Python List 1. Store items in FIFO order Ex. 12, 5, 7, 13 Back of PQ | 13 | 7 | 5 | 12 Front of PQ Operations: a. Enqueue – add to back of PQ (the front of the Python list) O(n) b. Dequeue – find the max priority and remove the first item with that priority O(n) 2. Store in increasing sorted order Ex. 12, 5, 7, 13 Back of PQ | 5 | 7 | 12 | 13 Front of PQ Operations: a. Enqueue – adds the item to its sorted position O(n) b. Dequeue – remove from the front of the queue O(1) June 11, 2013 Linked List 1. FIFO Order Back of PQ | 13 | | 7 | | 5 | | 12 | Front of PQ a. Enqueue O(1)
More Less

Related notes for CS 234

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit